Prime numbers

[sometimes99er]

Last night I saw the video where you did the 1000 primes on TF and it took about 2 seconds. I put the same code into ES forth on the Atari (English Software Forth) and the same code took 13 seconds to run.

http://www.youtube.com/watch?v=V5VGuNTrDL8

 

Very nice.

 

I thought I would write an assembler equivalent. I don't understand Forth, so I read a little about prime number generating algorithms.

 

What you basically could do, is to test a value and see if any prior found prime is a factor. And then the greatest prime to use in a test is less than the square root of the value to test. I'm not going to try and explain any of this, but I quickly found, that I didn't have to use the square root function, which is nice, since I want the assembler source to be minimal.

 

I wrote this Basic program. XB takes about 1 minute and 40 seconds to do primes less than 1000.

 

Now, I don't want the program to be more complicated, and I don't want it to be much bigger, but I would like to know, if any of you think there's room for performance improvements (other than using short variable names and short line numbers).

 

Also, if any of you could compile the Basic, and time the output.

 

Edited April 4, 2018 by sometimes99er

[rocky007]

error...

Edited March 4, 2011 by rocky007

[rocky007]

Last night I saw the video where you did the 1000 primes on TF and it took about 2 seconds. I put the same code into ES forth on the Atari (English Software Forth) and the same code took 13 seconds to run.

 

http://www.youtube.com/watch?v=V5VGuNTrDL8

 

Very nice.

 

I thought I would write an assembler equivalent. I don't understand Forth, so I read a little about prime number generating algorithms.

 

What you basically could do, is to test a value and see if any prior found prime is a factor. And then the greatest prime to use in a test is less than the square root of the value to test. I'm not going to try and explain any of this, but I quickly found, that I didn't have to use the square root function, which is nice, since I want the assembler source to be minimal (will post).

 

I wrote this Basic program. XB takes about 1 minute and 40 seconds to do primes less than 1000.

 

Now, I don't want the program to be more complicated, and I don't want it to be much bigger, but I would like to know, if any of you think there's room for performance improvements (other than using short variable names and short line numbers).

 

Also, if any of you could compile the Basic, and time the output.

 

100 CALL CLEAR
110 LIMIT=1000
120 DIM PRIMES(1000)
130 STACK=0
140 VALUE=2
150 PRIMES(STACK)=VALUE
160 STACK=STACK+1
170 PRINT VALUE;
180 VALUE=3
190 PRIMES(STACK)=VALUE
200 STACK=STACK+1
210 PRINT VALUE;
220 VALUE=VALUE+2
230 IF VALUE>LIMIT THEN 999
240 DIVISOR=0
250 RESULT=VALUE/PRIMES(DIVISOR)
260 IF RESULT=INT(RESULT)THEN 220
270 IF PRIMES(DIVISOR)>=RESULT THEN 190
280 DIVISOR=DIVISOR+1
290 GOTO 250

 

Tryed to compile with HW compiler, but have one error ( undefined symbol 0034 ) in the assembler...

 

But look fast also ( the 2 first number is calculated before freezing )

primec.zip

Edited March 4, 2011 by rocky007

[sometimes99er]

error...

Compiling ? Is it line 230 ? Try and change 999 to END, or add line 999 !?

 

[sometimes99er]

But look fast also ( the 2 first number is calculated before freezing )

I think the TF just sets the first few prime numbers. At least my Basic version sets the first two numbers, so they are actually not calculated. Cheap trick, but used a lot, I think ...

 

[rocky007]

ah yes working, just added 999 END.... but now the problem, it stop after the calcuting numer 3

[sometimes99er]

ah yes working, just added 999 END.... but now the problem, it stop after the calcuting numer 3

I suspect that the compiler must be using integers (is there a way around this in the compiler and force floating point ?), so this line

 

260 IF RESULT=INT(RESULT)THEN 220

will always be true = it won't find prime numbers. Maybe a rewrite avoiding the need for floating point ?

 

The assembler version would use DIV instruction to get the "result" and then check for any remainder.

 

Edited March 4, 2011 by sometimes99er

[unhuman]

error...

Compiling ? Is it line 230 ? Try and change 999 to END, or add line 999 !?

 

 

Yeah, compiler gives undefined symbol (IIRC) for missing line #'s. Sort of gives a wee bit of insight on how it works under the covers.

[sometimes99er]

Here's a cartridge assembler version. Uses same algorithm as the XB version above.

 

 

 

[Rybags]

There's a couple of other optimisations, don't think they were mentioned in the Wiki text linked above.

 

First, the obvious ones: No even no.s other than 2, and any number with "5" as the last digit.

 

The not immediately obvious ones:

 

For any number divisible by 3, the digits in that number will always add to something divisible by 3, e.g. for 993, 3+3+9 = 15; for 1236, 1+2+3+6 = 12.

 

Also (remember this from a kickarse prime generator I wrote at school). You can also discard any "Triangular numbers" from consideration of being primes.

 

The Triangular sequence is easy to generate, it's just recursively adding a number one larger, so generating the sequence:

 

1 = 1

1+2 = 3

1+2+3 = 6, 1+2+3+4 = 10

 

then 15, 21, 28, 36, 45, 55, 66, 78, 91, etc.

[sometimes99er]

... any number with "5" as the last digit.

I've tried and keep it minimal. The test is about 10 assembler instructions, and display is maybe 20 instructions. I might just be able to optimize with the "5 as last digit" trick. Thanks.

 

[sometimes99er]

And the video ...

 

http://www.youtube.com/watch?v=0D_M7n3_Os4

 

[Opry99er]

Nice vid! =)

[Willsy]

Karsten, that's a great video.

 

Seeing how fast some stuff runs in TurboForth (which, let's face it, is fast, but still slower than raw assembly) and seeing Karsten's assembly version of the Primes program has kind of caused me to see the TI in a different light.

 

When we talk about assembly language on the TI, we're always thinking in terms of 'don't do it that way, it's slower, do it this way instead' - this is mainly because of the unique architecture of the 99/4A - there are many ways to skin the cat!

 

However, it's also starting to dawn on me that, really, in assembly language, and there really is no other way to say it... "The ol' 4A is fucking fast!"

 

[Opry99er]

"The ol' 4A is fucking fast!"

 

 

Ain't that the truth!!!!!!!

[sometimes99er]

Karsten, that's a great video.

 

Seeing how fast some stuff runs in TurboForth (which, let's face it, is fast, but still slower than raw assembly) and seeing Karsten's assembly version of the Primes program has kind of caused me to see the TI in a different light.

 

When we talk about assembly language on the TI, we're always thinking in terms of 'don't do it that way, it's slower, do it this way instead' - this is mainly because of the unique architecture of the 99/4A - there are many ways to skin the cat!

 

However, it's also starting to dawn on me that, really, in assembly language, and there really is no other way to say it... "The ol' 4A is fucking fast!"

 

Hi Mark, and thanks for being cool about it. I'm of course not in anyway trying to put down TurboForth. TurboForth is very impressive. I'm just interested in comparing TurboForth with raw Assembler - knowing that algorithms, tricks, memory usage, programming time, debugging time and more, are all different factors to consider when comparing. Your TurboForth is pretty darn fast, no question about that. Congratulations on getting it all this far.