OISC Prime Number Demo
Prime Numbers
​An OISC synthetic assembly language program was written to find all the prime numbers less than 50,000, then to collect them all together so they were contiguous in RAM. Finally the program counts them and writes each to a single predefined address in memory, in a loop.
The algorithm used was based on the Sieve of Eratosthenes (the square root constant of the array range was hard-coded).
​
The first approach used an array to store the 50,000 candidate integers, but this couldn't be copied into the boot ROM 8KiB, so a hardcoded array pointer was used. For the former approach, a synthetic assembly instruction was added to the CPU to determine the address of the array (for the Indirect Indexed instructions to use). This could have been found during the compile/linking time, but it was easier to create a synthetic instruction to do so (however it used more program space).
​
540 SUBLEQ commands were used, which would have been a mind-bending task to write natively. Approximately 70 synthetic instructions were used, arranged into 5 subroutines.
​
Click here to return to the Eccentric Computing page.
​​​
The Code
_PROGSTART 0
_CONSTANTS $300
_VARIABLES $400
_STACK $1000
​
!arraylen 50000
!sqrtarraylen 224 ; round up; must be greater than 2 and less than arraylen
; .array[5] {} ; unused array
.tmpendsum 0
.currdiv 0
.currind 0
.cnt 0
.showprimelocation 0
.compsrcind 0
.compdestind 0
.arrayaddr 0
.numprimes 0
​
start:
; LEAV arrayaddr, array ; unused "new" command to find address of array
LDAV arrayaddr, #$2000
JSR fillarray ; 0,0, 2 to arraylen-1
JSR loopthroughdivisors ; loop through possible divisors and zero out non-primes
JSR compressprimes ; remove zeros and bring to start of array
JSR showprimesonbus ; store primes at showprimelocation sequentially
HLT
​
fillarray: ; 0 to N-1
LDAV cnt, arraylen
LDY #0
LDX #0
STAV y, (arrayaddr), x ; first 2 numbers = 0
INX
STAV y, (arrayaddr), x
INX
INY
INY
DECV cnt
DECV cnt
loopfillarray:
STAV y, (arrayaddr), x
INX
INY
DECV cnt
BZEV cnt, endfillarray
JMP loopfillarray
endfillarray:
RTS
loopthroughdivisors: ; 2 to sqrtarraylen [sqrt(N)]
LDAV cnt, sqrtarraylen
LDAV currdiv, #2
startloopthroughdivisors:
PUSV currdiv
JSR clearmultiples
INCV currdiv
DECV cnt
BZEV cnt, endloopthroughdivisors
JMP startloopthroughdivisors
endloopthroughdivisors:
RTS
clearmultiples: ; clears multiples of what is on the stack
POPV currind
LDA #$0
LDX currind
loopclearmultiples:
ADDV X currind
LDAV tmpendsum, arraylen
SUBV tmpendsum, x
BLEV tmpendsum, endclearmultiples ; if X>N jmp to endclearmultiples (RTS)
STAV acc, (arrayaddr), x
JMP loopclearmultiples
endclearmultiples:
RTS
compressprimes: ; collect them and make contiguous in memory
LDAV compsrcind, #0
LDAV compdestind, #0
LDY #$0
LDAV cnt, arraylen
loopcompressprimes:
LDAV acc, (arrayaddr), compsrcind ; get arraryaddr + compsrcind
BZE compressskipcopy ; if not zero then copy arraryaddr + compsrcind
; to arraryaddr + compdestind, and compdestind++
STAV acc, (arrayaddr), compdestind ; copy prime to next contiguous location
STAV y, (arrayaddr), compsrcind ; store 0 over previous prime
INCV compdestind
compressskipcopy:
DECV cnt
BZEV cnt, endcompressprimes
INCV compsrcind
JMP loopcompressprimes
endcompressprimes:
LDAV numprimes, compdestind
RTS
showprimesonbus: ; loop through numprimes from (arrayaddr) and store at $EEEE
LDAV cnt, numprimes
LDAV compsrcind, #0
loopshowprimes:
LDAV acc, (arrayaddr), compsrcind
STA $EEEE
DECV cnt
BZEV cnt, endshowprimes
INCV compsrcind
JMP loopshowprimes
endshowprimes:
RTS
