Jump to content

Photo

BASIC Interpreter Speed Comparison: Prime Number Generation

BASIC Performance Primes

56 replies to this topic

#51 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Wed Nov 22, 2017 2:33 AM

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 by JamesD, Wed Nov 22, 2017 2:47 AM.


#52 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Wed Nov 22, 2017 8:28 AM

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



#53 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Wed Nov 22, 2017 1:15 PM

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



#54 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Wed Nov 22, 2017 1:49 PM

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


#55 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Wed Nov 22, 2017 8:25 PM

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


#56 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Wed Nov 22, 2017 8:32 PM

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.
 



#57 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,754 posts
  • Location:Flyover State

Posted Today, 4:22 PM

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 by JamesD, Today, 5:19 PM.






Also tagged with one or more of these keywords: BASIC, Performance, Primes

1 user(s) are browsing this forum

0 members, 1 guests, 0 anonymous users