Optimization

Forum Attachments

Summary:

This thread is to help people optimize their programs to run faster

Optimization

ARubiksCube 19 Feb 2016 02:23

This is an very extremely basic program to find prime numbers. Is there a way to optimize it in any way, it takes about 30 sec to find the 1st prime number after 5000 (5003)
(I don't know if there is a way to get an arrow on a laptop keyboard so -> will do)
(and the Zeros look like Os)

ClrHome
0->B
Input "STARTING NUMBER",C
C-1->C

Lbl 1
getkey->B
While B=0
C+1->C
1->D
For(D,2,(C/2),1)
remainder(C,D)->R
If R=0
Goto 1
End

Disp C
Goto 1
End

Re: Optimization

jonbush 19 Feb 2016 02:57

Without significantly changing the algorithm, there are several possible optimizations:

ClrHome
Input "STARTING NUMBER",C
C+not(fPart(C/2->C   //start at the first odd number at or after C, assuming C is natural and C≥4
Repeat getKey
For(D,3,sqrt(C),2)
If not(fpart(C/D
C->D
End
If C+2!=D
Disp C
C+2->C
End

It is bad practice to jump out of loops using Goto, because it creates memory leaks, which slow down the program and eventually lead to an error.

Re: Optimization

Trenly 19 Feb 2016 04:31

Im wondering what exactly the fastest algorithm would be for this.

Obviously, to test if a number is prime you have to see if it is divisible by any number other than itself or one. Now if a number is divisible by a non-prime number, then it is also divisible by the prime factors of the divisor. So 48 is divisible by 12, but also 2 and 3. That being the case, you simply have to test the divisibiltiy of a number against all the prime numbers below it. Obviously, testing larger numbers would be slower.

Would lists be the fastest way? Perhaps using matricies?

Re: Optimization

jonbush 19 Feb 2016 05:24

The fastest way is most likely an implementation of a segmented Sieve of Eratosthenes with wheel factorization.

Re: Optimization

Trenly 19 Feb 2016 16:26

Hmmm. Perhaps….

Wouldnt a segmented Seive of Atkin be faster, if preceded with wheel factorization?

And im assuing that Eulers Seive would be just as fast as Eratosthenes

Last edited on 19 Feb 2016 16:35 by Trenly Show more

Re: Optimization

jonbush 19 Feb 2016 17:48

The Seive of Atkin would be faster for larger values, but due to the additional complexity, a TI-BASIC implementation may be slower overall. I have not tested this, but I may make a Sieve of Atkin to compare with my improved Sieve of Eratosthenes eventually.

Re: Optimization

lirtosiast 20 Feb 2016 03:52

Wikipedia says the segmented Sieve of Atkin offers little advantage over the Sieve of Eratosthenes, except for very large numbers. Since the numbers we're capable of dealing with on the calculator aren't very large (and since the implementation overhead on the Sieve of Eratosthenes is basically nonexistent, while that of the Sieve of Atkin is significant), the Sieve of Eratosthenes should be faster.

Re: Optimization

ARubiksCube 19 Feb 2016 13:02

Thanks! That helped a lot. I tried 5000 again and it only took 1.5 seconds. Using sqrt(C) rather than C/2 helped a lot. I'm working on a program to test for primes using a wheel sieve, but it needs a lot of work.

Last edited on 19 Feb 2016 17:09 by ARubiksCube Show more