Prime numbers generator: my response

[Qwe]

Hi guys.
Some one on you tube posted a video that show the difference between an atari 8 bit and a moder pc.
In his video the atari take about 3 days to find prime numbers until 10000.
I respond to that video with my program.
I use a serious language and my program takes about 2 minuts to do the same task, so I ransom the little atari.
I don't use precalculated data; is there anyone who accepts the challenge and want to try to do better?
Download and try my program, for who is interested I'll share the source code.
Bye

 

P.S. sorry for my english

primi.xex

Edited April 14, 2014 by Qwe

[Qwe]

Hello Everyone!
Forget the old version, the new one is much better!!!
I've improve the generator and now 10000 numbers are processed in about 70 seconds.
I share the source code; it is not commented but it should be easy to understand.
I use C language, in Basic language this performance is impossible.
Have fun...change it and improve it!!!
Good bye

ataprime.xex

primi.zip

[ilmenit]

Hello Everyone!

Forget the old version, the new one is much better!!!

I've improve the generator and now 10000 numbers are processed in about 70 seconds.

I share the source code; it is not commented but it should be easy to understand.

I use C language, in Basic language this performance is impossible.

Have fun...change it and improve it!!!

Good bye

Printf is slow, using 'int' data type is slow, using signed int is even slower, passing data by stack is slow... A lot could be improved, even in C code.

[Qwe]

Printf is not slow is very slow but I think is slow the put char routine of the operative system that printf use.
Of course passing data by stack is slow but source code is more readable.
There is a margin of improvement in C language but the best is a jump to the hell and use assembly .

[a8isa1]

Printf is not slow is very slow but I think is slow the put char routine of the operative system that printf use.

Of course passing data by stack is slow but source code is more readable.

There is a margin of improvement in C language but the best is a jump to the hell and use assembly .

 

Hi guys.

Some one on you tube posted a video that show the difference between an atari 8 bit and a moder pc.

In his video the atari take about 3 days to find prime numbers until 10000.

I respond to that video with my program.

I use a serious language and my program takes about 2 minuts to do the same task, so I ransom the little atari.

I don't use precalculated data; is there anyone who accepts the challenge and want to try to do better?

Download and try my program, for who is interested I'll share the source code.

Bye

 

P.S. sorry for my english

This is a bit of a coincidence. In March while perusing some old Usenet messages I came across benchmark results of the Sieve of Eratosthenes on our 8bit but none of the source codes (well, not at first). I was curious so I wrote it (and rewrote it, repeat) in Atari BASIC.

 

Below is my final implementation but I can't take credit for it's speed. When I eventually found some sources (but not Atari BASIC source) I realized using an inner loop and changing the STEPs is more efficient. Originally I was actually computing the multiples. (about 6X slower).

 

The old Sieve benchmark results I found were for 10 iterations, determining primes up to 8192. My program also does 10 iterations but you can plug in a maximum value (up to 32767) for the search.

 

The screen goes blank during the whole process and the time of the run is displayed. 'Jiffies' are counted and they are assumed to be 1/60th of second (for NTSC) or 1/50th (for PAL). I couldn't remember the exact duration of jiffies so there no correction factor.

 

Prime number of 1 is assumed, not part of the algorithm, all other primes are determined by the search process

 

The search table is implemented in one string. No machine code was used.

 

I hope I did this right. Primes up to 1000 were correct. I did not compare beyond that.

 

If you lose patience waiting for the run to complete then delete line 2036 and line 2172 to reduce the iterations to just one.

 

My program finds primes from 1 to 8192 in 1978.5 seconds and from 1 to 10000 in 2487.6 seconds. That's for the 10 iterations. So, about 198 seconds and 249 seconds for a single iteration.

 

One last note. I didn't have the patience to do these timingsin real time. I used Atari800 3.0.0 emulator in 'Turbo' mode, NTSC video.

 

Here's the program.

10 REM SIEVE OF ERATOSTHENES
20 REM DIM TABLE$(8190)
30 GOTO 2000:REM MAIN
1000 REM SIEVE
1010 FOR I=2 TO INT(SQR(LAST))
1020   LASTMULT=INT(LAST/I)
1030   IF TABLE$(I,I)<>"T" THEN 1070
1040   FOR J=I+I TO LAST STEP I
1050     TABLE$(J,J)="F"
1060   NEXT J
1070 NEXT I
1080 RETURN
2000 REM MAIN - SIEVE OF ERATOSTHENES
2010 RTCLK1=20:RTCLK2=19:RTCLK3=18:SDMCTL=559:PALFLG=53268
2012 IF PEEK(PALFLG)=1 THEN JDIV=5:GOTO 2015
2013 JDIV=6
2015 POKE 82,0
2017 ?  "PRIME NUMBERS BENCHMARK":? "(10 ITERATIONS)"
2020 ?  "MAXIMUM VALUE";:INPUT LAST
2030 DIM TABLE$(LAST)
2032 POKE SDMCTL,0
2034 GOSUB 4000
2036 FOR ITERATION=1 TO 10
2040   TABLE$(LAST)=" ":REM PLACE HOLDER
2047   TOTAL=0
2060   FOR I=1 TO LAST
2070     TABLE$(I)="T":REM T FOR TRUE
2080   NEXT I
2112   GOSUB 1000:REM START THE SIEVE
2140   COUNT=0
2150   FOR I=1 TO LAST
2160     IF TABLE$(I,I)="T" THEN COUNT=COUNT+1
2170   NEXT I
2172 NEXT ITERATION
2175 GOSUB 5000:TOTAL=TOTAL+JIFFIES
2180 ?  "TOTALS"
2200 ? COUNT;" PRIMES"
2210 ? TOTAL;" JIFFIES "
2220 ? INT(TOTAL/JDIV+0.5)/10;" SECONDS"
2230 ?  "PRESS ANY KEY TO DISPLAY THE PRIMES"
2235 POKE SDMCTL,34
2240 OPEN #1,4,0,"K:":GET #1,I:CLOSE #1
2250 GOSUB 3000:END
3000 FOR I=1 TO LAST
3010   IF TABLE$(I,I)="T" THEN ? I;" ";
3020 NEXT I
3030 RETURN
4000 POKE RTCLK1,0:POKE RTCLK2,0:POKE RTCLK3,0:RETURN
5000 JIFFIES=PEEK(RTCLK2)*256+PEEK(RTCLK1)+PEEK(RTCLK3)*65536:RETURN

Hmm, Kwrite did the indentations not me

 

-SteveS

 

Edited April 18, 2014 by a8isa1

[a8isa1]

LOL

 

I found a speed-up already!

 

line, 1020 LASTMULT=INT(LAST/I), is a remnant from the earlier version of the program. It's not needed.

 

-SteveS

[a8isa1]

I always thought the number 1 was a prime number. Seems I was mistaken.

 

Here is my program with the corrections.

10 REM SIEVE OF ERATOSTHENES
30 GOTO 2000:REM MAIN
1000 REM SIEVE
1010 FOR I=2 TO INT(SQR(LAST))
1020   LASTMULT=INT(LAST/I)
1030   IF TABLE$(I,I)<>"T" THEN 1070
1040   FOR J=I+I TO LAST STEP I
1050     TABLE$(J,J)="F"
1060   NEXT J
1070 NEXT I
1080 RETURN
2000 REM MAIN - SIEVE OF ERATOSTHENES
2010 RTCLK1=20:RTCLK2=19:RTCLK3=18:SDMCTL=559:PALFLG=53268
2012 IF PEEK(PALFLG)=1 THEN JDIV=5:GOTO 2015
2013 JDIV=6
2015 POKE 82,0
2017 ?  "PRIME NUMBERS BENCHMARK":? "(10 ITERATIONS)"
2020 ?  "MAXIMUM VALUE";:INPUT LAST
2030 DIM TABLE$(LAST)
2032 POKE SDMCTL,0
2034 GOSUB 4000
2036 FOR ITERATION=1 TO 10
2040   TABLE$(LAST)=" ":REM PLACE HOLDER
2047   TOTAL=0
2060   FOR I=1 TO LAST
2070     TABLE$(I)="T":REM T FOR TRUE
2080   NEXT I
2112   GOSUB 1000:REM START THE SIEVE
2140   COUNT=0
2150   FOR I=2 TO LAST
2160     IF TABLE$(I,I)="T" THEN COUNT=COUNT+1
2170   NEXT I
2172 NEXT ITERATION
2175 GOSUB 5000:TOTAL=TOTAL+JIFFIES
2180 ?  "TOTALS"
2200 ? COUNT;" PRIMES"
2210 ? TOTAL;" JIFFIES "
2220 ? INT(TOTAL/JDIV+0.5)/10;" SECONDS"
2230 ?  "PRESS ANY KEY TO DISPLAY THE PRIMES"
2235 POKE SDMCTL,34
2240 OPEN #1,4,0,"K:":GET #1,I:CLOSE #1
2250 GOSUB 3000:END
3000 FOR I=2 TO LAST
3010   IF TABLE$(I,I)="T" THEN ? I;" ";
3020 NEXT I
3030 RETURN
4000 POKE RTCLK1,0:POKE RTCLK2,0:POKE RTCLK3,0:RETURN
5000 JIFFIES=PEEK(RTCLK2)*256+PEEK(RTCLK1)+PEEK(RTCLK3)*65536:RETURN

Edited April 19, 2014 by a8isa1

[bob_er]

Check 'toys' here: http://sdx.atari8.info/index.php?show=en_addons.

Especially sieve.exe .

This is not optimized for speed nor binary size.

Require SpartaDOS X - sdx's reloc binary format is used.

 

edit: link fixed.

Edited April 29, 2014 by bob_er