!lm12
!rm75
Even Faster Primes..........................Anthony Brightwell

Is this the last word on prime number generation?  

I modified Charles Putney's program from the February issue, and cut the time from 330 milliseconds down to 183 milliseconds!  Here is what I did:

!lm+8
!pp-3
*  I sped up the zero-memory loop by putting more STA's within the loop.

*  I removed the CLC from the main loop.  After all, why CLC withing the loop if you're looping on a BCC condition?

*  I removed the LDA #$FF from the main loop.  It was there to be sure a non-zero value gets stored in non-prime slots, but why LDA #$FF if the accumulator never contains $00 within the loop?

*  I changed the way squares of primes are computed.  Charlie did it using a quick 8-bit by 8-bit multiply.  I took advantage of a little number theory, and shaved off some time.
!lm-8
!pp0

The method I use for squaring may appear very round-about, but it actually is faster in this case.  Look at the following table:

    Odd #'s  square   neat formula
       1       1       0 * 8 + 1
       3       9       1 * 8 + 1
       5      25       3 * 8 + 1
       7      49       6 * 8 + 1
       9      81      10 * 8 + 1

The high byte of the changing factor in the "neat formula" is stored in the LDA instruction at line 1550, and the low byte in the ADC instruction at line 1900.  The factor is the sum of the numbers from 1 to n:  1+2=3, 1+2+3=6, 1+2+3+4=10, etc.  In all, 31 primes are squared, and the total time for all the squaring is less than 3 milliseconds.

Here is a driver in Applesoft to load the program and then print out primes from the data array.

!lm+5
10  REM DRIVER FOR TONY'S FAST PRIME FINDER
20  PRINT CHR$ (4)"BLOAD B.TONY'S SUPER-FAST PRIMES"
30  HOME : PRINT "HIT ANY KEY TO START"
40  GET A$: PRINT " GENERATING PRIMES . . ."
50  CALL 32768
60  FOR A = 8195 TO 24576 STEP 2
70  IF  PEEK (A) = 0 THEN  PRINT A - 8192;" ";
80  NEXT
!lm-5

A few more cycles can probably still be shaved....  Any takers?
