Jump to content

Photo

BASIC Interpreter Speed Comparison: Prime Number Generation

BASIC Performance Primes

136 replies to this topic

#126 thorfdbg OFFLINE  

thorfdbg

    Dragonstomper

  • 746 posts

Posted Tue Dec 5, 2017 1:13 AM

What do you mean by better math model?

 

Microsoft Basic uses binary to represent floating point numbers, Atari Basic a kludgy decimal format with the base 100 which makes multiplications and divisions unbearably slow. The latter does not matter in this case - for additions and subtractions, it is somewhat ok.



#127 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,872 posts
  • Location:Flyover State

Posted Tue Dec 5, 2017 2:29 AM

 

Microsoft Basic uses binary to represent floating point numbers, Atari Basic a kludgy decimal format with the base 100 which makes multiplications and divisions unbearably slow. The latter does not matter in this case - for additions and subtractions, it is somewhat ok.

You mean binary coded decimal?
Well, Microsoft's math library isn't exactly the most efficient thing I've ever seen either.
But standard Atari BASIC C turned in a time of 4.17 seconds vs 3.133 on the C64 and the Atari is clocked faster.
Faster times that have been posted for the Atari are due to optimized math libs, or through the use of a compiler. 



#128 tecci06 OFFLINE  

tecci06

    Space Invader

  • 16 posts

Posted Tue Dec 5, 2017 6:41 AM

had to do a change in the code for the ACORN Electron:

10CLS:CLEAR
20K%=0:I%=0:T%=0:P%=0
100PRINT"Prime Number Generator"
110INPUT"Upper Limit";N%
120ETIME=TIME
130T%=INT((N%-3)/2)
140DIMA%(T%+1)
160FORI%=0TOT%:A%(I%)=0:NEXT
200FORI%=0TOT%:IFA%(I%)THENPRINT"..";:NEXT:GOTO330
220P%=I%+I%+3:PRINT;P%;".";:K%=I%+P%:IFK%<=T%FORK%=K%TOT%STEPP%:A%(K%)=1:NEXT
260NEXT
330ETIME=(TIME-ETIME)/100
340PRINT:PRINT"Total: ";ETIME
360END

Line 330: it has to divide by 100, not 60 to get the correct seconds.

Did check this value by hand timing with a limit of 10000.

 

Now the results are:

Limit 250: 1,41
Limit 10000: 52,11

 

For the C64, the division by 60 is correct.


Edited by tecci06, Tue Dec 5, 2017 6:58 AM.


#129 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,872 posts
  • Location:Flyover State

Posted Tue Dec 5, 2017 9:19 AM

I'm guessing that will change the BBC Micro results as well.



#130 _The Doctor__ ONLINE  

_The Doctor__

    River Patroller

  • 2,872 posts
  • Location:10-0-11-00:02

Posted Tue Dec 5, 2017 10:28 AM

standard Atari basic is not built in Atari basic... Atari's official Basics are BASIC A,B,C and MicroSoft Basic.... built in basic is something done for convenience later in the line, and was simply to get people started. It was implemented as it was ready to go first...


Edited by _The Doctor__, Tue Dec 5, 2017 10:31 AM.


#131 tecci06 OFFLINE  

tecci06

    Space Invader

  • 16 posts

Posted Wed Dec 6, 2017 7:44 AM

I compiled the Plus/4 version with Austrospeed.
With the blanking code:
Limit 250 = 1.05 seconds
Limit 10000 = 43.3333333 seconds

Limit 20000 = 87.2333333 seconds

Skipping the parser makes a huge difference, but it's obviously not as efficient as FastBASIC.
It's probably making ROM calls and bankswitching between ROM and RAM. 
It still handles larger arrays.

 

Made this on the Commodore 64 with Basic-Boss Compiler V2.4

 

Limit 250: 0,33  seconds

Limit 10000: 26,283 seconds

Limit 20000: 53,7 seconds


Edited by tecci06, Wed Dec 6, 2017 7:46 AM.


#132 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,872 posts
  • Location:Flyover State

Posted Wed Dec 6, 2017 10:50 AM

Last night I created a simple patch for the Plus/4's CHRGOT code that reads the next byte of the program because it banks in and out memory for every byte.
The result is about 4% faster than the original code here, but it still banks in and out RAM/ROM when copying variables to/from the floating point registers. 
There is still more speed to be had with more patching but I don't know what % improvement it would offer.
Another 4% would certainly be worth pursuing, but it's not going to make the Plus/4 one of the leaders on this benchmark.
It would need another 50% to get into that category and I think that would require a new ROM if it's even possible.

Standard BASIC without screen blanking:
Limit 250     3.61666667

Limit 10000 147.216667
Limit 20000 295.65

 

Patched CHRGOT without screen blanking:

Limit 250     3.48333333
Limit 10000 141.833333
Limit 20000 284.866667

Patched CHRGOT with screen blanking
Limit 250       2.31666667
Limit 10000 94.51966667

Limit 20000 189.8


*NOTE:  Subsequent runs turned in slightly different times.  It may depend on where the clock was when the program started.


Edited by JamesD, Wed Dec 6, 2017 11:19 AM.


#133 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,872 posts
  • Location:Flyover State

Posted Wed Dec 6, 2017 11:12 AM

Plus/4 code. 
The latest version of the benchmark is listed first, then the added patch (which only needs to be executed once after startup), and then the code to blank the screen.
The patch actually has to be deleted (at least lines 0 and 5) before you can run the code additional times 
 


10 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  DIMA(T+1)

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

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

0 REM012345678901234567890123456789012
5 A=4102:FORI=0 TO 30:READ T:POKE A+I,T :NEXT I:SYS A

10000 DATA 160,18,185,18,16,153,121,4,136,16,247,96
10010 DATA 160,0,177,59,201,58,144,1,96,233,47,201
10020 DATA 240,240,235,56,233,208,96


115 POKE65286,PEEK(65286)AND239
335 POKE65286,PEEK(65286)OR16


Edited by JamesD, Wed Dec 6, 2017 11:15 AM.


#134 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,872 posts
  • Location:Flyover State

Posted Wed Dec 6, 2017 11:07 PM

A little fix to the patch so you don't have to delete line 0.  
You can delete line 1 and the lines with DATA statements after the first RUN. 
Then you can save the code with the patch already embedded in line 0.

0 REM012345678901234567890123456789012345
1 FORI=0 TO 35:READ T:POKE 4102+I,T :NEXT I
2 SYS 4102
 
10000 DATA 160,18,185,23,16,153,121,4,136,16,247,200,152,153,122,4,96
10010 DATA 160,01,177,59,201,58,144,1,96,233,47,201
10020 DATA 240,240,235,56,233,208,96


Edited by JamesD, Wed Dec 6, 2017 11:08 PM.


#135 evilmoo OFFLINE  

evilmoo

    Chopper Commander

  • 123 posts

Posted Yesterday, 6:00 PM

I'm not sure if anyone has taken this into account or not, but as you test each number, you only have to test with the primes you've found so far.  For example, if you've already determined the number isn't divisible by three, there's no way it's divisible by 9, 15, 21, 33, etc.  So if you make the effort to save your discovered primes, you can minimize your division attempts.



#136 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,872 posts
  • Location:Flyover State

Posted Yesterday, 7:07 PM

I'm not sure if anyone has taken this into account or not, but as you test each number, you only have to test with the primes you've found so far.  For example, if you've already determined the number isn't divisible by three, there's no way it's divisible by 9, 15, 21, 33, etc.  So if you make the effort to save your discovered primes, you can minimize your division attempts.

The more recent code uses a large array to flag which numbers and their multiples have been found already.
That's the limiting factor on largest prime number the machines can calculate with this code.  
 



#137 evilmoo OFFLINE  

evilmoo

    Chopper Commander

  • 123 posts

Posted Yesterday, 7:16 PM

The more recent code uses a large array to flag which numbers and their multiples have been found already.
That's the limiting factor on largest prime number the machines can calculate with this code.  
 

 

You can further encode that data by saving the distance from the previous prime, rather than all the possible numbers.

 

so 3, 5, 7, 11, 13, 17, 19, 23, 29 becomes

 

(start at 3) 2, 2, 4, 2, 4, 2, 4, 6

 

and since the distance is always even, you can divide it by 2

or 1,1,2,1,2,1,2,3.

And at least on Atari, you can save it as a CHR$() in a string array rather than a numeric array.  I'm not sure when the distance goes over 512, but that should keep you guys busy for a little while. :)







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

0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users