Al Zimmermann's Programming Contests

Normally I don't participate in programming challenges, but something about the latest of Al Zimmermann's Programming Contests caught my attention.

The idea is to submit sets of numbers so their combination by addition and subtraction generates the most distinct primes.  There are 12 problems, for sets of 3 to 14 numbers.

A pen and paper should be sufficient to find the optimal solution for 3 numbers.  Don't be fooled however, the solutions for 4+ require a program to search through the possibilities.

4 yields easily to a computer search with at least three optimal solutions waiting to be discovered.  Despite writing a program which tests 280,000 potential solutions per second, I haven't found the top solution for 5.

Currently I'm restricting the search space to one odd number, one multiple of 6 and the remaining numbers all multiples of 30.  Maybe this is too restrictive?

Here's the program I'm using.  Any suggestions how I can improve the speed?

n1 equ 1
n2 equ 6
n3 equ 30
n4 equ 90
n5 equ 270

i1 equ 600
i2 equ 600

vprime equ 7000

numb equ 5

; *** generate list of primes

mov si,prime+4
mov bx,5
nextpr:
mov di,prime+2
try:
mov ax,bx
xor dx,dx
div word[di]
or dx,dx
jz notpr
scasw
ja try
mov word[si],bx
cmpsw
notpr:
inc bx
inc bx
cmp si,prime+vprime
jne nextpr

; *** fill prime table with zero

xchg ax,bx
mov di,tabl
xchg ax,cx
xor ax,ax
rep stosb

; *** update values to test

testnew:
add word[xa],2
cmp word[xa],n1+i1+10
jc gogo
mov word[xa],n1

add word[xb],6
cmp word[xb],n2+i2+10
jc gogo
mov word[xb],n2

add word[xc],30
mov ax,word[xc]
cmp ax,word[xd]
jc gogo
mov word[xc],n3

add word[xd],30
mov ax,word[xd]
cmp ax,word[xe]
jc gogo
mov word[xd],n4

add word[xe],30

; *** mark primes in table

gogo:
mov ax,word[xa]
add ax,word[xe]
add ax,word[xd]
add ax,word[xc]
add ax,word[xb]
xchg dx,ax
mov si,prime
ptab:
lodsw
cmp dx,ax
jc fini
add ax,tabl
xchg bx,ax
mov byte[bx],1
cmp si,prime+vprime
jne ptab
fini:

; *** test

xor bp,bp
mov ax,word[xa]
mov bx,word[xe]
mov cx,word[xd]
mov dx,word[xc]
mov di,word[xb]

call x2

; *** if there's a new top score...

xchg ax,bp
cmp ax,word[xhigh]
jl next

; *** ... display the winning numbers

mov word[xhigh],ax
call printdec

mov dl,' '
call printchar
mov dl,'-'
call printchar

mov cx,numb
lea si,word[xa]
disp:
mov dl,' '
call printchar
lodsw
call printdec
loop disp

mov dl,0D
call printchar
mov dl,0A
call printchar

; *** and repeat

next:
mov ah,1
int 016h
jz redo
int 020h
redo:
jmp testnew


x2:
push ax
add ax,bx
call x3
pop ax
push ax
sub ax,bx
call x3
pop ax

x3:
push ax
add ax,cx
call x4
pop ax
push ax
sub ax,cx
call x4
pop ax

x4:
push ax
add ax,dx
call x5
pop ax
push ax
sub ax,dx
call x5
pop ax

x5:
push ax
add ax,di
call x6
pop ax
push ax
sub ax,di
call x6
pop ax

x6:
xabs:
neg ax
js xabs
add ax,tabl
xchg ax,si
cmp byte[si],0
je notprx
inc bp
mov byte[si],0
notprx:
xchg ax,si
ret

; *** print number in ax

printdec:
push ax
push cx
push dx
mov cx,10
xor dx,dx
div cx
test ax,ax
je pdbye
call printdec
pdbye:
add dl,'0'
call printchar
pop dx
pop cx
pop ax
ret

printchar:
mov ah,2
int 021
ret

xhigh:dw 0

xa:dw n1-2
xb:dw n2
xc:dw n3
xd:dw n4
xe:dw n5

prime:
dw 2
dw 3

tabl equ prime+vprime+10