Author 
Message 

mezz
Newbie
Joined: 29 Jan 2007 Posts: 3

Posted: 29 Jan 2007 08:52:33 pm Post subject: 


I created a simple little program to find prime numbers today.
This is one of my first TI BASIC programs, but I have read a bit about optimization and how to code well on it. I don't have any other coding experience though =/
0>B \\prepare B, used to count number of primes found
2>LPR(1 \\Make sure 2 and 3 are given primes on custom list "L PR"
3>LPR(2
Input "FIND N PRIMES: ",N \\User Inputs number of primes to find and append to list LPR
startTmr>θ \\For timing the different programs. the variable is theta
Lbl A \\Program will look back to here until N primes are found
dim(LPR>D \\number of primes in the list. The list isn't cleared every time so it can add up for later
2+LPR(D>X \\Starting value X is highest known prime + 2 (evens aren't prime)
1>A \\Prep A, used to go up and down the primes list to check for divisibility
Repeat LPR(A)>=(.5LPR(D \\repeats until all the primes up to half the number have been tried. Higher than 1/2 of X and they surely can't divide.
If not(fPart(X/LPR(A \\Checks to see if X is evenly divisible by a known prime. If it is divisible X is incremented by 2 and we start dividing by 3 again.
Then
2+X>X \\not going to deal with evens at all...
1>A \\A will be 2 by the time it tries again
End
A+1>A \\Goes to the next known prime to use as a divisor
End \\repeat ends if all known primes up to 1/2 of X have been tried, so X must be prime
X>LPR(D+1 \\stores a new prime to the end of the primes list
Disp X \\So you can see them whiz by , optional
1+B>B \\increments so we can stop it at the desired number of primes
If B!=N
Goto A \\loops everything
checkTmr(θ>L1(1 \\outputs my time
Starting with a blank LPR list:
Without the "disp X" my time is 23 seconds! (for the first 50 primes. setting N to 48, it starts with 2 and 3)
With disp x my time is 26 seconds
I checked this with a known primes list and it works. I am just wondering if I can optimize it more without learning ASM. So far this is the fastest one I've used, and I downloaded a couple so I'm pretty happy
Last edited by Guest on 29 Jan 2007 08:56:07 pm; edited 1 time in total 

Back to top 


Harrierfalcon The Raptor of Calcs
Super Elite (Last Title)
Joined: 25 Oct 2006 Posts: 2535

Posted: 29 Jan 2007 08:55:35 pm Post subject: 


First, you can replace the goto loop with "Repeat B=N". Save a few bytes and time.
Rather than using LPR, use something like L1 or L2, the system lists.
Welcome to UnitedTI! 

Back to top 


mezz
Newbie
Joined: 29 Jan 2007 Posts: 3

Posted: 29 Jan 2007 08:58:56 pm Post subject: 


Ah thanks, the repeat should help
Are the system lists any different? I have plenty of memory and was worried because I have to use my regular system lists sometimes.
I guess it would save bytes in the program though.. hmm. I'll use L6.
Thanks !'
Still it's at a healthy 23 seconds. This is kicking the pants off of any of the ones I downloaded and tested the time for.
It should matter a lot more for longer runs of say... N= 997 heh
Last edited by Guest on 29 Jan 2007 09:05:06 pm; edited 1 time in total 

Back to top 


luby I want to go back to Philmont!!
Calc Guru
Joined: 23 Apr 2006 Posts: 1477

Posted: 29 Jan 2007 09:45:34 pm Post subject: 


0>b can be delvar b
2>LPR(1
3>LPR(2
can be {2,3>pr(1 // don't need the L
those I see right off the bat. 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 29 Jan 2007 09:45:37 pm Post subject: 


luby wrote: 2>LPR(1
3>LPR(2
can be {2,3>pr(1 // don't need the L Not quite. ERR:DATA TYPE on that one.
Use [font="courier new;fontsize:9pt;lineheight:100%;color:darkblue"]DelVar B{2,3→PR instead.
mezz wrote: Higher than 1/2 of X and they surely can't divide. Higher than the square root of X and they surely can't divide.
mezz wrote: So far this is the fastest one I've used, and I downloaded a couple so I'm pretty happy It's a savvy implementation. Be proud, and welcome to UnitedTI.
Last edited by Guest on 29 Jan 2007 09:50:07 pm; edited 1 time in total 

Back to top 


mezz
Newbie
Joined: 29 Jan 2007 Posts: 3

Posted: 29 Jan 2007 09:53:56 pm Post subject: 


I can see the DelVar, but there may be a problem with "{2,3>L6"
I don't want the whole list to be overwritten, so I can continue it later.
Changed to :
DelVar B2>L6(1
3>L6(2
Changed to: Repeat L6(A)>Sqrt(X
I was trying that before, but I had >= and didn't notice so 9 was "prime" and it messed the whole thing up. With just > it works really, really fast.
13 seconds!!!!!!!
Thanks guys!
EDIT: 11 seconds without Disp X. Jeez! What a difference
Here's the most current version. I decided to use a For( loop because I was incrementing B anyway.
Also, I stored Sqrt(X to Y to save computation
Code: 2>L6(1
3>L6(2
Prompt N
For(B,0,N1
dim(L6>D
2+L6(D>X
1>A
Repeat L6(A)>Sqrt(X
If not(fPart(X/L6(A
Then
2+X>X
1>A
End
1+A>A
End
X>L6(D+1
End
At 111 bytes it's half the size and twice the speed of the rest~
9 seconds for first 50 primes
Last edited by Guest on 30 Jan 2007 02:46:21 am; edited 1 time in total 

Back to top 


thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569

Posted: 02 Feb 2007 01:20:06 pm Post subject: 


Reminds me... here's a prime number sieve I wrote a while back, returning all primes less than or same as N:
Code: PROGRAM:SIEVE
Prompt N
int(N/2)→M
M→dim(∟T)
Fill(1,∟T)
2→P:3→K
While K²≤N
For(J,P+K,M,K)
0→∟T(J)
End
Repeat ∟T(P)
P+1→P
End
2P–1→K
End
{2}→P:2→J
For(P,2,M)
∟T(P)→H
If H
2P–1→∟P(J)
J+H→J
End
DelVar ∟T
∟P
thornahawk 

Back to top 


