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