BASIC Interpreter Speed Comparison: Prime Number Generation

JamesD · November 22, 2017

I think this fixes the Plus/4 version, and the loops should be similar on the Apple II.
It has not been verified against other versions though.

Run time was 4.2 seconds.

20 K=0:T=0:P=0:I=0
30 SCNCLR
100  PRINT "Prime Number Generator"
110  INPUT "Upper Limit";N
120  eTime=TIME
130  T = (N-3)/2
140  DIM A(T+1)
160  FOR I=0 TO T:A(I)=1:NEXT I

200  FOR I=0 TO T
220   IF A(I)=1 THEN P=I+I+3:PRINT P;".";:K=I+P:GOTO 250
240   PRINT "..";:NEXT I:GOTO 330
250   IF K<=T THEN FOR K=K TO T STEP P:A(K)=0:NEXT K
260  NEXT I

330  eTime = (TIME - eTime)/60
340  PRINT
350  PRINT "Total: ";eTime
360 END

*edit*
I forgot, the Plus/4 supports ELSE. This is cleaner and if you remove the spaces from the loops it runs in 4.1 seconds.
I vaguely remember something about Commodore being faster if you leave the variable off of the NEXT statement, but I'm not messing with it.

200  FOR I=0 TO T
220   	IF A(I)=1 THEN P=I+I+3:PRINT P;".";:K=I+P:ELSE PRINT "..";:NEXT I:GOTO 330
250     IF K<=T THEN FOR K=K TO T STEP P:A(K)=0:NEXT K
260  NEXT I

Edited November 22, 2017 by JamesD

JamesD · November 22, 2017

Okay, I messed with it. The Plus/4 turned in a time of 3.76666667 with this section of code.
This may speed up other Microsoft versions as well but I haven't tried it yet.

160 FORI=0TOT:A(I)=1:NEXT
200 FORI=0TOT
220 IFA(I)THENP=I+I+3:PRINTP;".";:K=I+P:ELSEPRINT"..";:NEXT:GOTO330
250 IFK<=TTHENFORK=KTOTSTEPP:A(K)=0:NEXT:NEXT

JamesD · November 22, 2017

Hand timing sucks, but here is the latest.

The MC-10 with the enhanced ROM benchmarks around 2.5 seconds with this loop configuration.

160 FORI=0TOT:A(I)=1:NEXT
200 FORI=0TOT
220   IFA(I)THENP=I+I+3:PRINTP;".";:K=I+P:IFK<=TTHENFORK=KTOTSTEPP:A(K)=0:NEXT:ELSEELSEPRINT "..";:NEXT:GOTO340
320 NEXT

Apple II just over 3 seconds

160  FORI=0TOT:A(I)=1:NEXT
200  FORI=0TOT
220   IFA(I)=1THENP=I+I+3:PRINTP;".";:K=I+P:IFK<=TTHEN226 
225   PRINT"..";:NEXT:GOTO340
226   FORK=KTOTSTEPP:A(K)=0:NEXT:NEXT

JamesD · November 22, 2017

The CoCo parser is temperamental about spaces. To get the rest out, you'd need to remove them with a crunch utility..
But, like this, the CoCo says 1.71666667 seconds.
Every space removed seems to cut off 0.05 seconds, which suggests it could run in 1.5666667 seconds if you run a crunch utility on it, but I make no promises..

160 FORI=0TOT:A(I)=1:NEXT
200 FORI=0TOT
220   IFA(I)THENP=I+I+3:PRINTP;".";:K=I+P:IFK<=T THENFOR K=K TOT STEPP:A(K)=0:NEXT:ELSEELSEPRINT"..";:NEXT:GOTO340
320 NEXT

JamesD · November 23, 2017

The VZ200 takes about 6 seconds.
It would do better if the editor supported longer lines, but it would require an external tokenizer and loading if from a cassette or disk image to do that.
Some other BASICs may benefit by doing that as well since the only part of many BASICs that cares is the tokenizer..

160  FORI=0TOT:A(I)=1:NEXT
200  FORI=0TOT
220   IFA(I)THENP=I+I+3:PRINT P;".";:K=I+P:IFK<=TTHEN226 
225   PRINT "..";:NEXTI:GOTO340
226   FORK=KTOTSTEPP:A(K)=0:NEXT:NEXT

JamesD · November 23, 2017

I'm not going to write a version for the TI or Atari.
Atari Microsofo BASIC should work pretty well based on the enhanced MC-10 BASIC, or CoCo code unless the lines are too long..
The Plus/4 code would probably work if neither of those do.

The other BASICs, are different enough It would take longer to figure out than I want to mess with.

JamesD · November 24, 2017

I had a little time to mess with Atari Microsoft BASIC.

Atari Microsoft BASIC is pretty picky which prevents using many of the optimizations I used on other versions.
It doesn't seem to like lines longer than one screen line, it had issues with multiple NEXT statements for the same loop, it barfs on lines when I delete spaces, and that's just what I remember.

This seems to work but someone that has used it more might be able to shave some time off of this.
If Microsoft BASIC uses the Atari math library ROM then a faster version of that should also make a difference.

The time here is 3.26667 on Altirra.

*edit* There also appears to be a bug in the print. Use 10000 and you'll see what I mean.
FWIW, the difference between this and the CoCo/MC-10 is worse when you use larger values that require scrolling the screen. The MC-10 uses a 16 bit screen scroll and the CoCo probably does as well... unless that was one of my optimizations to the MC-10 ROM, I've forgotten.

10 DEFINT A,K,I,T
20 K=0:T=0:P=0:I=0
30 CLS
100 PRINT "Prime Number Generator"
110 INPUT "Upper Limit";N
120 TIME=0
130 T = (N-3)/2
140 DIM A(T+1)


160 FOR I=0 TO T:A(I)=1:NEXT I


200 FOR I=0 TO T
210 IF A(I)=0 THEN 255
211 P=I+I+3:PRINT P;".";:K=I+P
250 IF K>T THEN 256
251 FOR K=K TO T STEP P:A(K)=0:NEXT K
254 GOTO 256
255 PRINT"..";
256 NEXT I


330 ETIME = TIME/60
340 PRINT
350 PRINT "Total: ";ETIME
360 END

This gave the same result.

10 DEFINT A,K,I,T
20 K=0:T=0:P=0:I=0
30 CLS
100 PRINT "Prime Number Generator"
110 INPUT "Upper Limit?";N
120 TIME=0
130 T = (N-3)/2
140 DIM A(T+1)

160 FOR I=0 TO T:A(I)=1:NEXT I

200 FOR I=0 TO T
210 IF A(I)=1 THEN 240
212 PRINT"..";
213 GOTO 256

240 P=I+I+3:PRINT P;".";:K=I+P
250 IF K>T THEN 256
251 FOR K=K TO T STEP P:A(K)=0:NEXT K
256 NEXT I

330 ETIME = TIME/60
340 PRINT
350 PRINT "Total: ";ETIME
360 END

Edited November 24, 2017 by JamesD

JamesD · November 25, 2017

I pasted the first Atari Microsoft BASIC version into Altira BASIC..
It ran after changing the INPUT line, so I google "Atari BASIC timer" and "Atari BASIC clear screen" and here we are..
So Altirra BASIC runs it in 1.15 seconds if I did this right.
*edit* You'll need to use more digits of the timer for larger numbers.

20 K=0:T=0:P=0:I=0
50 PRINT CHR$(125)
100 PRINT "Prime Number Generator"
110 PRINT "Upper Limit";:INPUT N
120 POKE 20,0
130 T = (N-3)/2
140 DIM A(T+1)

 
160 FOR I=0 TO T:A(I)=1:NEXT I

200 FOR I=0 TO T
210 IF A(I)=1 THEN 240
212 PRINT"..";
213 GOTO 256

240 P=I+I+3:PRINT P;".";:K=I+P
250 IF K>T THEN 256
251 FOR K=K TO T STEP P:A(K)=0:NEXT K
256 NEXT I

330 ETIME=PEEK(20)/60
340 PRINT
350 PRINT "Total: ";ETIME
360 END

120 POKE 19,0:POKE 20,0
330 ETIME=(PEEK(19)*256+PEEK(20))/60

Edited November 25, 2017 by JamesD

RXB · November 25, 2017

I suggest you test all the computers in that video on Assembly for speed and for highest number of digits accuracy.

You will find the TI99/4A does 10 digits and the rest top out at 6 to 8 at best.

The reason TI99/4A would win hands down is 16 bit CPU vs the rest are all 8 bit CPU's.

Edited November 25, 2017 by RXB

JamesD · November 25, 2017

I suggest you test all the computers in that video on Assembly for speed and for highest number of digits accuracy.

You will find the TI99/4A does 10 digits and the rest top out at 6 to 8 at best.

The reason TI99/4A would win hands down is 16 bit CPU vs the rest are all 8 bit CPU's.

At this point, we are using the Sieve of Sundaram algorithm which doesn't even require floating point.

The latest code is more about looping, indexing arrays, finding variables, and finding line numbers quickly.

JamesD · November 25, 2017

I pasted the first Atari Microsoft BASIC version into Altira BASIC..

It ran after changing the INPUT line, so I google "Atari BASIC timer" and "Atari BASIC clear screen" and here we are..

So Altirra BASIC runs it in 1.15 seconds if I did this right.

*edit* You'll need to use more digits of the timer for larger numbers

I'm getting the same numbers with and without the Fast FP Math option set.

Did Altirra 2.71 actually use 6502 math libraries when this option is turned off?

JamesD · November 25, 2017

The TI version care of sometimes99er from the TI group.

The TI can't dynamically allocate arrays so the code has to be modified to run with different a limit.
Also, the TI can only print to the bottom of the screen, so it has to scroll after every line which slows it down.
I added an input at line 111 so it would be easier to time and it takes bout 10.5 seconds.

50 call clear
100 PRINT "Prime Number Generator"
110 N=250
130 T=(N-3)/2
140 DIM A(123)
160 FOR I=0 TO T::A(I)=1::NEXT I

200 FOR I=0 TO T
210 IF A(I)=1 THEN 240
212 PRINT"..";
213 GOTO 256

240 P=I+I+3
241 PRINT P;".";
242 K=I+P
250 IF K>T THEN 256
251 FOR K=K TO T STEP P::A(K)=0::NEXT K
256 NEXT I

_The Doctor__ · November 26, 2017

emulation is not always spot on in timing..

JamesD · November 26, 2017

emulation is not always spot on in timing..

I think that's the least of the problems here given the fact that I'm trying to time most of these by hand.

RXB · November 26, 2017

At this point, we are using the Sieve of Sundaram algorithm which doesn't even require floating point.

The latest code is more about looping, indexing arrays, finding variables, and finding line numbers quickly.

So finding Primes only matters if it is very very small numbers?

If the point was to find the least effective way to find least number of primes fast yea you are on the right track.

It does point to a favored result as the only reason to do the test.

JamesD · November 26, 2017

Atari BASIC C returned a time of 3.18333333 when using a limit of 250.

JamesD · November 26, 2017

Just so people know, I've been privately running a lot of these with a limit of 10000.
But if you try to DIM a large enough array on the TI-99/4A, it runs out of memory.
The other machines handle it just fine.

To make it handle different limits, I set out to DIM it to the largest array size I might use and then added the LIMIT input.
That's when I discovered the issue. But it will handle 5000. I haven't tried to find exactly where it runs out of memory.

110 PRINT"LIMIT?";::INPUT N
140 DIM A(2500)

Edited November 26, 2017 by JamesD

JamesD · November 26, 2017

I looked at the Ahl's benchmark thread, and OSS BASIC XE was much faster than BASIC XL.
I couldn't get it to run on the emulator through.

JamesD · November 26, 2017

I thought I'd check a couple changes to the Plus/4 version since it might benefit the most from a small change, and it has a timer to use to compare differences in code.
The new time is 3.7 which isn't far off of other standard 6502 BASICs even though it supports 60K of user RAM.

I squeezed more of the main loops together, trimmed a few spaces from the timed area, and changed the order variables were defined in.

Combining two lines made a slight improvement.

The spaces didn't even register since they weren't in the loops.

Just changing the order variables were defined on line 20 cut .01666667 off of the results.
Without line 20, the results are 3.91666667, so it's quite an improvement for so little effort. I can't guarantee a different order wouldn't yield better results on larger numbers though.
But such a simple change would really add up counting to 10000 and the same change should make other Microsoft BASIC versions faster.
So, CoCo, MC-10, Apple II, VZ, etc... Not sure about other BASICs.

20 K=0:I=0:T=0:P=0

30 SCNCLR
100  PRINT "Prime Number Generator"
110  INPUT "Upper Limit";N
120  eTime=TIME
130  T = (N-3)/2
140  DIM A(T+1)

160 FORI=0TOT:A(I)=1:NEXT
200 FORI=0TOT:IFA(I)THENP=I+I+3:PRINTP;".";:K=I+P:ELSEPRINT"..";:NEXT:GOTO330
250 IFK<=TTHENFORK=KTOTSTEPP:A(K)=0:NEXT:NEXT
260 NEXT

330  eTime=(TIME-eTime)/60
340  PRINT
350  PRINT "Total: ";eTime
360 END

JamesD · November 26, 2017

CoCo 1.68-1.71 MESS keeps giving different numbers.

Without the high speed POKE... 3.41666667

The CoCo math library is like the original MC-10 math library. Strait 6800 code.

Using 10000, the CoCo takes 67.75 seconds, but you must first type PCLEAR 1 on Extended BASIC machines to free up some of the RAM reserved for graphics in order to run with this large of number. MESS's inconsistent results may have impacted this.
The MC-10 with the optimized BASIC takes about 55 seconds based on how much less time it took than the CoCo *WHEN CLOCKED AT THE SAME DOUBLE SPEED*
About 100 seconds at normal speed.

The Plus/4 takes 75.58333334
Atari BASIC takes 138.659949 seconds.
Altirra BASIC takes 48.95 seconds..

20 K=0:I=0:T=0:P=0
30 CLS
100  PRINT "Prime Number Generator"
110  INPUT "Upper Limit";N
120 TIMER=0
130  T=(N-3)/2
140  DIM A(T+1)

160 FORI=0TOT:A(I)=1:NEXT
200 FORI=0TOT:IFA(I)THENP=I+I+3:PRINTP;".";:K=I+P:IFK<=T THENFOR K=K TOT STEPP:A(K)=0:NEXT:ELSEELSEPRINT"..";:NEXT:GOTO330
320 NEXT

330 ETIME=TIMER/60
340  PRINT
350  PRINT "Total: ";,ETIME
360 END

Edited November 26, 2017 by JamesD

JamesD · November 27, 2017

The VZ makes it to 10000 in 3:15
I altered the code 3 times trying to get a better result, and this was the best.
I forgot to declare A as and integer on one try and it added 5 seconds to the run time.
Swapping the order K and I are initialized didn't seem to matter.

10 DEFINT K,I,P,A
20 K=0:I=0:T=0:P=0
30 CLS
100  PRINT "Prime Number Generator"
110  INPUT "Upper Limit";N
130  T=(N-3)/2
140  DIM A(T+1)

150 FORI=0TOT:A(I)=1:NEXT
200 FORI=0TOT:IFA(I)=0THENPRINT"..";:NEXT:GOTO340
230P=I+I+3:PRINTP;".";:K=I+P:IFK<=TFORK=KTOTSTEPP:A(K)=0:NEXT
260 NEXT

340  PRINT
350  PRINT "DONE"
360 END

JamesD · November 28, 2017

I'm not sure what happened, but I'm getting different results for the Plus/4.
Maybe with all the changes part of the program got deleted and it didn't run the full benchmark but I just didn't notice.

The Plus/4 is turning in a time of 151.516667 seconds.

The Apple II runs it in about 154 seconds.
The VZ's 195 seconds clearly shows it's BASIC has lots of room for improvement through compiling or by optimizing the interpreter.

The Plus/4 would perform significantly better if it can be patched so it doesn't use so much memory for programs.

JamesD · November 28, 2017

The Oric turns in a hand timed number around 175 seconds on Oricutron. How accurate that is I don't know.
Like many machines that use a screen editor, it only allows BASIC code lines to be two screen lines in length,
It supports ELSE but can't really take advantage of it here. So far Tandys are the only machines that handle really long lines.

_The Doctor__ · November 28, 2017

are you remembering to poke 82,0 on zee ataree to get a couple more in per line but is it really needed? Yeah looks like you need to go back and verify your code and posted times....

Edited November 28, 2017 by _The Doctor__

JamesD · November 29, 2017

are you remembering to poke 82,0 on zee ataree to get a couple more in per line but is it really needed? Yeah looks like you need to go back and verify your code and posted times....

I did not.

The later times are 10000, not 250. It's easier to time by hand with large numbers.

BASIC Interpreter Speed Comparison: Prime Number Generation

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members