Jump to content

Photo

"BASIC Interpreter Speed Comparison Prime Number Generator"


24 replies to this topic

#1 JamesD OFFLINE  

JamesD

    Quadrunner

  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 3:16 AM

Just making you aware of this topic in the Atari 8 bit area.
If someone wants to port the newer prime generator code to the TI it would be a welcome addition to the topic.
http://atariage.com/...ber-generation/



#2 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sat Nov 25, 2017 5:05 AM

Rustin Holmes already has a video uploaded with the TI. Link to his YouTube in post #1 in the thread referenced.  ;)
 
I timed a version I made for TI Basic, and it took 1 minute and 40 seconds to calculate primes up to 1,000. I'm sure it's beatable. ;)


Edited by sometimes99er, Sat Nov 25, 2017 5:26 AM.


#3 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sat Nov 25, 2017 8:10 AM

primes.png

 

;)



#4 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 11:34 AM

I'm aware of the original video and spreadsheet.  If you read the thread, I started with his code. 
His code relied on multiple divisions, tested all numbers, etc...
The latest code is based on the sieve of Sundaram algorithm (technically, I didn't look it up, I just took someone else's word for it).
It is very fast, but it could be argued that it's not really giving the floating point library much of a workout.

I would think the TI would do significantly better calculating primes to 1000 in 1:40.
 
The slowest version of the Sundaram algorithm I've tested so far found primes to 250 in about 6 seconds.
That was the VTEC VZ/Laser 200.  It's BASIC is based on Level II BASIC from the TRS-80 Model I, and it's horribly inefficient.  

 

The MC-10 version using a modified version of BASIC finds primes to 250 in around 2.5 seconds and it's only clocked at .89 MHz.  

And that version of BASIC still doesn't take full advantage of the 6803's 16 bit capabilities.
 

The Atari version I posted last night finds primes to 250 in as little as 1.15 seconds, and primes to 1000 in 4.7 seconds using Altirra BASIC.  

TI BASIC should do this in under 10 seconds.  I just don't want to fight with ANSI BASIC syntax to find out, and figured someone here would be up to the challenge.
 


Edited by JamesD, Sat Nov 25, 2017 11:35 AM.


#5 OLD CS1 OFFLINE  

OLD CS1

    River Patroller

  • 4,038 posts
  • Technology Samurai
  • Location:Tallahassee, FL

Posted Sat Nov 25, 2017 11:50 AM

Compiled XB?



#6 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 12:43 PM

Compiled XB?

I'd like to see compiled and regular interpreted results. 
The fastest time so far has been the Fast BASIC on the Atari which is also compiled, so that's certainly fair game.
At some point I'm sure the other versions will get compiled as well.
 



#7 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sat Nov 25, 2017 1:51 PM

I'm aware of the original video and spreadsheet.  If you read the thread, I started with his code. 

 

Okay, sorry about that. Just skipped quickly through the posts.  :(



#8 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sat Nov 25, 2017 2:37 PM

The latest code is based on the sieve of Sundaram algorithm (technically, I didn't look it up, I just took someone else's word for it).
It is very fast, but it could be argued that it's not really giving the floating point library much of a workout.

TI BASIC should do this in under 10 seconds.  I just don't want to fight with ANSI BASIC syntax to find out, and figured someone here would be up to the challenge.

 
Wow, that's fast.
 
primes.gif
 
 
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
 


#9 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 2:48 PM

Looks like less than 10 seconds to me.

*edit*
I'm guessing you added CALL CLEAR after recording that.
Since you didn't clear the screen before recording that, the time includes scrolling, so that's going to impact the results.
Also, not using input to read the max number or at least say go, and printing when it's done makes it a little tougher to time.
But it doesn't look like getting it running was difficult.
*edit*
Oh, you did have the screen cleared, it just did't reset the printing position


Edited by JamesD, Sat Nov 25, 2017 3:07 PM.


#10 mizapf OFFLINE  

mizapf

    River Patroller

  • 2,609 posts
  • Location:Germany

Posted Sat Nov 25, 2017 3:15 PM

That's the SIEVE algorithm. It successively removes all multiples of a number and then steps to the next. Thus it becomes faster to the end of the search space.



#11 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sat Nov 25, 2017 3:45 PM

Looks like less than 10 seconds to me.

 

Yes, I think so. :)
 

*edit*
I'm guessing you added CALL CLEAR after recording that.
Since you didn't clear the screen before recording that, the time includes scrolling, so that's going to impact the results.
Also, not using input to read the max number or at least say go, and printing when it's done makes it a little tougher to time.
But it doesn't look like getting it running was difficult.
*edit*
Oh, you did have the screen cleared, it just did't reset the printing position

 

On the TI you can't dynamically declare the size of an array at runtime. And with PRINT the cursor position is always at the bottom, even after clearing the screen.
 
;)

 



#12 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 4:15 PM

 

Yes, I think so. :)
 

 

On the TI you can't dynamically declare the size of an array at runtime. And with PRINT the cursor position is always at the bottom, even after clearing the screen.
 
;)

 

I would have clicked like, but I refuse to like those "features". 
 



#13 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sat Nov 25, 2017 4:17 PM

I would have clicked like, but I refuse to like those "features". 

 

He he.



#14 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 4:40 PM

I added an input to kick it off so the screen clear and initial print wouldn't be counted.  As near as I can tell, it takes about 10.5 seconds. 
Without printing, it takes around 6 seconds.



#15 Ksarul OFFLINE  

Ksarul

    River Patroller

  • 4,234 posts

Posted Sat Nov 25, 2017 8:59 PM

Of course, this algorithm skips the first prime: 2, so it isn't perfect. It is still a very nice and fast sort though, and as all systems are tested with it, no system advantages will crop up. . .  :)



#16 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sat Nov 25, 2017 10:37 PM

Of course, this algorithm skips the first prime: 2, so it isn't perfect. It is still a very nice and fast sort though, and as all systems are tested with it, no system advantages will crop up. . .  :)

Well, I'm not sure I agree on that last part, but that deserves an explanation.
  
One of the things I'm emphasizing is that features like the ELSE statement, support for long multi-statement lines, etc... make programs run faster.
It takes time to parse more characters, to search for line numbers, etc... and the results reflect that.
Just look how much time as a % is cut off of the Plus/4 numbers just by deleting the loop variables from the next statements, or by using ELSE.
It cut about 1/2 of a second off the time.  That's over a 10% advantage vs a BASIC that doesn't allow that. 

The important thing is that it doesn't provide any system with an unfair advantage.  It is a fair comparison of the capabilities of these machines and BASICs. 
We didn't try to tune the benchmark for one machine by unrolling loops or something you wouldn't normally do if you were used to programming these systems.
The functionality is the same as best as each system can manage.

FWIW, I could get more speed out of the initialization of the array by unrolling that loop once and stepping by 2.
You might not notice a huge difference when the limit is set to 250, but at 10,000 it's definitely going to be noticeable.
 



#17 RXB OFFLINE  

RXB

    River Patroller

  • 2,838 posts
  • Location:Vancouver, Washington, USA

Posted Sun Nov 26, 2017 1:36 AM

You do know that the comparisons of computers doing primes is larger numbers not small numbers?  

 

Who cares that a computer can do 3 digit primes when it is a 8 bit computer?

 

The entire race over the years since the 1950's was how many primes can you do and how high of primes can you get. 

 

The original video was based on very very small primes in the least time, almost a total useless waste of computer time.

 

Like using a Nuke on a cockroach. Better idea is to max out the computer to see what it is capable of, not some phoney useless contest.



#18 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sun Nov 26, 2017 2:17 AM

The important thing is that it doesn't provide any system with an unfair advantage.  It is a fair comparison of the capabilities of these machines and BASICs. 

 

Yep, it seems fair. It takes one particular algorithm unrelated to any particular computer.

 

But for a "comparison of capabilities of machines and BASICs", I think I would have to throw perhaps many and varied benchmarks at them. ;)
 
For a quick and dirty overall speed comparison, it probably fine, and this one should be too:
 
http://atariage.com/...-2#entry3773785

 

We usually benchmark computers to assess relative performance, and that could include accuracy as in the link. And perhaps also price, availability, markets, consoles sold, number of colors, number of games etc. ;)

 

Take the TI and the MSX. The TI was announced in June 1979, and was announced to pull out on October 28th, 1983. The MSX was announced on June 27th, 1983.
 
;)


Edited by sometimes99er, Sun Nov 26, 2017 2:20 AM.


#19 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sun Nov 26, 2017 2:33 AM

You do know that the comparisons of computers doing primes is larger numbers not small numbers?  

 

Who cares that a computer can do 3 digit primes when it is a 8 bit computer?

 

The entire race over the years since the 1950's was how many primes can you do and how high of primes can you get. 

 

The original video was based on very very small primes in the least time, almost a total useless waste of computer time.

 

Like using a Nuke on a cockroach. Better idea is to max out the computer to see what it is capable of, not some phoney useless contest.

 

The original goal was to compare the speed of the different BASICs, not how high they can count. 

You act as if this is the first speed benchmark you've ever seen.

I didn't choose 250, the original topic starter did.  The original program can handle much larger numbers though..

He probably chose 250 because the original program was so slow if he had chosen something larger it would take a long time to finish.

The newer code finishes primes to 10000 in under a minute on some machines.
The TI says memory full if I even try 8000.  It will handle 5000 though and larger numbers are easier to time by hand. 
To go higher on the TI it's going to require a slower algorithm.

If you want to know how high computers can count, all that is required to calculate that is knowing how the format used for floating point numbers.
Many of them probably even had it published in their manuals.  It's not like you don't already know the result.
 



#20 RXB OFFLINE  

RXB

    River Patroller

  • 2,838 posts
  • Location:Vancouver, Washington, USA

Posted Sun Nov 26, 2017 3:56 AM

 

The original goal was to compare the speed of the different BASICs, not how high they can count. 

You act as if this is the first speed benchmark you've ever seen.

I didn't choose 250, the original topic starter did.  The original program can handle much larger numbers though..

He probably chose 250 because the original program was so slow if he had chosen something larger it would take a long time to finish.

The newer code finishes primes to 10000 in under a minute on some machines.
The TI says memory full if I even try 8000.  It will handle 5000 though and larger numbers are easier to time by hand. 
To go higher on the TI it's going to require a slower algorithm.

If you want to know how high computers can count, all that is required to calculate that is knowing how the format used for floating point numbers.
Many of them probably even had it published in their manuals.  It's not like you don't already know the result.
 

True the TI kicks all of them in the ass with 10 digits compared to the best of them is 7 digits. (8 bit CPU vs 16 bit CPU)

 

Memory full? Are you saving all the numbers in a array? The TI had only 16K VDP memory and only 12K for Basic. Again a comparison designed to make the TI fail?

 

I mean to be fair write it in Assembly on all machines and since most of them are using NEW 3rd party add ons or software while the TI is using ORIGINAL memory and Software?

 

Tell you what use the SAMS 1 Meg card and Assembly and do a comparison.


Edited by RXB, Sun Nov 26, 2017 3:58 AM.


#21 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sun Nov 26, 2017 5:27 AM

True the TI kicks all of them in the ass with 10 digits compared to the best of them is 7 digits. (8 bit CPU vs 16 bit CPU)

 

Memory full? Are you saving all the numbers in a array? The TI had only 16K VDP memory and only 12K for Basic. Again a comparison designed to make the TI fail?

 

I mean to be fair write it in Assembly on all machines and since most of them are using NEW 3rd party add ons or software while the TI is using ORIGINAL memory and Software?

 

Tell you what use the SAMS 1 Meg card and Assembly and do a comparison.

First you complained about the limited number of primes, and now you are complaining about a large number of primes.
If you want it in assembly, write it in assembly.  Nobody is stopping you.
But it kinda defeats the original purpose which was to COMPARE BASICS!
I'm pretty sure I even said it was okay to compile the code but all you do is complain.
Hell, you didn't even look at the code or the common algorithm it's based on.
It's not my fault TI BASIC is so damn slow and the machine has such a small amount of RAM available to BASIC!
I didn't write it!  Complain to Texas Instruments!  
 



#22 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sun Nov 26, 2017 5:35 AM

 

Yep, it seems fair. It takes one particular algorithm unrelated to any particular computer.

 

But for a "comparison of capabilities of machines and BASICs", I think I would have to throw perhaps many and varied benchmarks at them. ;)
 
For a quick and dirty overall speed comparison, it probably fine, and this one should be too:
 
http://atariage.com/...-2#entry3773785

 

We usually benchmark computers to assess relative performance, and that could include accuracy as in the link. And perhaps also price, availability, markets, consoles sold, number of colors, number of games etc. ;)

 

Take the TI and the MSX. The TI was announced in June 1979, and was announced to pull out on October 28th, 1983. The MSX was announced on June 27th, 1983.
 
;)

FWIW, there is a large thread in the Atari 8 bit area on Ahl's benchmark.
Part of the reason I created an improved version of BASIC for the MC-10 was to prove it could beat faster 6502 machines on Ahl's benchmark after I said it could in that thread.
The results dropped from 1:59 to 1:07, and if you switch A^2 to A*A, it completes it in around 40 seconds.
And I couldn't squeeze most of the optimizations I wrote into 8K.
 



#23 sometimes99er OFFLINE  

sometimes99er

    River Patroller

  • 3,985 posts
  • Location:Denmark

Posted Sun Nov 26, 2017 5:46 AM

gallery_11132_2023_529.png
 
I'm fine. I can't get that boss anyway. :|

 



#24 RXB OFFLINE  

RXB

    River Patroller

  • 2,838 posts
  • Location:Vancouver, Washington, USA

Posted Sun Nov 26, 2017 7:13 AM

First you complained about the limited number of primes, and now you are complaining about a large number of primes.
If you want it in assembly, write it in assembly.  Nobody is stopping you.
But it kinda defeats the original purpose which was to COMPARE BASICS!
I'm pretty sure I even said it was okay to compile the code but all you do is complain.
Hell, you didn't even look at the code or the common algorithm it's based on.
It's not my fault TI BASIC is so damn slow and the machine has such a small amount of RAM available to BASIC!
I didn't write it!  Complain to Texas Instruments!  
 

 

No one is arguing that TI Basic is slow, known fact.

But ignoring that the others suck at top limits of digits and Floating Point accuracy is just centered on those limits alone is a rigged game.

 

Go ahead and get the Atari to do 9 digits primes. Anyway the TI does have some advantages not mentioned:

The register width of a processor determines the range of values that can be represented. Typical binary register widths for unsigned integers include:

8 bits: maximum representable value 28 − 1 = 255
16 bits: maximum representable value 216 − 1 = 65,535
32 bits: maximum representable value 232 − 1 = 4,294,967,295 (the most common width for personal computers as of 2005),
64 bits: maximum representable value 264 − 1 = 18,446,744,073,709,551,615 (the most common width for personal computer CPUs, as of 2017),
128 bits: maximum representable value 2128 − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455
When an arithmetic operation produces a result larger than the maximum above for a N-bit integer, an overflow reduces the result to modulo N-th power of 2, retaining only the least significant bits of the result and effectively causing a wrap around.

In particular, multiplying or adding two integers may result in a value that is unexpectedly small, and subtracting from a small integer may cause a wrap to a large positive value (for example, 8-bit integer addition 255 + 2 results in 1, which is 257 mod 28, and similarly subtraction 0 − 1 results in 255, a two's complement representation of −1).

Such wrap around may cause security problems – if an overflown value is used as the number of bytes to allocate for a buffer, the buffer will be allocated unexpectedly small, leading to a potential buffer overflow and arbitrary code execution.

If the variable has a signed integer type, a program may make the assumption that a variable always contains a positive value. An integer overflow can cause the value to wrap and become negative, which violates the program's assumption and may lead to unexpected behavior (for example, 8-bit integer addition of 127 + 1 results in −128, a two's complement of 128).


#25 JamesD OFFLINE  

JamesD

    Quadrunner

  • Topic Starter
  • 7,853 posts
  • Location:Flyover State

Posted Sun Nov 26, 2017 10:25 AM

Because clearly, 9 digit primes will reflect typical performance you can expect from a CPU.

*edit*

If it makes you feel any better, it's still going to be faster than the Sinclair Spectrum.

 


Edited by JamesD, Sun Nov 26, 2017 10:35 AM.





0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users