## TI Basic Prime Factorer

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

cmhhss1
Posts: 13
Joined: Thu Feb 12, 2009 8:13 pm UTC
Location: NY

### Re: TI Basic Prime Factorer

Alright guys, I'm going to give this one more try. The following program, though it does include 1 Lbl-Goto works very quickly and factors correctly every time.

Code: Select all

Lbl 2
ClrHome
Prompt X
Lbl 1
For (Y,2, sqrt X)
If x/y=int(x/y)
Then
Disp Y
X/Y -> X
Goto 1
End
End
Disp X, "Done"
Pause
Lbl 3
Stop

kriel
Posts: 922
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

### Re: TI Basic Prime Factorer

cmhhss1: If you do not want constructive criticism, do not open this spoiler. You've been warned.
Spoiler:
• Problems with the code
• There are memory leaks. Did you read the link I posted? Anytime you use a GOTO before anything that finishes with an END; it leaks memory. That includes {"FOR","WHILE","IF"} and possibly a few others that I can't think of at the moment.
• After every integer, it starts over from 2 again. After you've found a divisor, after you get all of said divisor out, it's guaranteed not to be there again. (Example: say I'm factoring 5*5*(?). After it checks 2,3,4,5 and finds 5 as a factor, it doesn't need to check 2,3,4 again. Right now it checks {2,3,4,5,2,3,4,5,...})
• It tests every integer between 2 and the square root of the number. It is a relatively simple cleanup to make it only scan every other integer, since after 2 we are assumed every even integer is not prime. (Every even integer is divisible by 2.)
• "x/y=int(x/y)" is relatively slow. I realize this is nitpicking at this point, but while I'm telling you how to optimize, use "fpart(x/y)=0". (To be super-optimized, use "not(fpart(x/y))". One less instruction, one bit faster.)

First, I'm going to take your program and turn it into a manual FOR loop. This will make more sense later.

Code: Select all

Lbl 2
ClrHome
Prompt X
Lbl 1
Y = 2 //Start at 2
While ( Y <= sqrt X) //keep going until you hit sqrt X
If x/y=int(x/y)
Then
Disp Y
X/Y -> X
Goto 1
End
Y + 1 -> Y //add one
End
Disp X, "Done"
Pause
Lbl 3
Stop

And now, I'm going to fix both the memory leaks and the fact that it repeats integers it's already checked. With one new line. Look carefully.

Code: Select all

Lbl 2
ClrHome
Prompt X
Lbl 1 //delete this
Y = 2
While ( Y <= sqrt X)
If x/y=int(x/y)
Then
Disp Y
X/Y -> X
Goto 1 //delete this
Y - 1 -> Y //add this
End
Y + 1 -> Y
End
Disp X, "Done"
Pause
Lbl 3
Stop

Now, using our 5*5*(?) example, it will only check {2,3,4,5,5,...} I'll let you figure out how to make it check just odds on your own.

End Result for posterity:

Code: Select all

Lbl 2
ClrHome
Prompt X
Y = 2
While ( Y <= sqrt X)
If fpart(x/y)=0
Then
Disp Y
X/Y -> X
Y - 1 -> Y
End
Y + 1 -> Y
End
Disp X, "Done"
Pause
Lbl 3
Stop

EDIT: I found an even simpler way to optimize your code. Just delete two lines and change a single statement.

Code: Select all

Lbl 2
ClrHome
Prompt X
Lbl 1//get rid of the goto/label stuff. Memory leaks, repeating factors, etc, etc.
For (Y,2, sqrt X)
While x/y=int(x/y)//change "If" to "While"
Then
Disp Y
X/Y -> X
Goto 1//get rid of more goto/label stuff.
End
End
Disp X, "Done"
Pause
Lbl 3
Stop

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: TI Basic Prime Factorer

kriel wrote:
Spoiler:
• "x/y=int(x/y)" is relatively slow. I realize this is nitpicking at this point, but while I'm telling you how to optimize, use "fpart(x/y)=0". (To be super-optimized, use "not(fpart(x/y))". One less instruction, one bit faster.)

As long as you're optimising,
Spoiler:

Code: Select all

While ( Y <= sqrt X) //keep going until you hit sqrt X
Isn't this square root calculated every iteration, whether X has changed or not?
I would use a separate variable to hold sqrt X, calculated before the loop starts and recalculated whenever X is updated.
If you don't want to use an extra variable, using a multiplication would probably be quicker:

Code: Select all

While ( Y*Y <= X) //keep going until you hit sqrt X

psykx
Posts: 408
Joined: Sat Feb 23, 2008 11:24 pm UTC
Location: England
Contact:

### Re: TI Basic Prime Factorer

hell if your optimizing you should only be testing the integers that conform to 6k+-1
Berengal wrote:Only if they're killer robots. Legos are happy robots. Besides, even if they were killer robots it wouldn't stop me. You can't stop science and all that.

Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: TI Basic Prime Factorer

Pfah! Luxury! Try 30k+-{1 7 11 13}.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Posts: 34
Joined: Thu Jun 10, 2010 10:56 pm UTC

### Re: TI Basic Prime Factorer

Just thought I'd share mine since I've been really into TI-Basic lately.

Nothing helps pass a boring high school trig class like writing programs for an hour and a half.

Code: Select all

:Input "INTEGERS ONLY!",X
:While X≠1
:2->N
:While int(X/N)≠X/N
:N+1->N
:End
:Disp N
:X/N->X
:End

Now I did read some of the earlier conversation about how there's no need to start from 2 every time because if you've tested 2-4 you won't need to test them again, so I'm going to try to fix that and see if I can shorten this even more. fpart too.

While I'm at it (haha pun), lemme share a program I wrote today that converts decimal to hexadecimal.

Code: Select all

:Prompt X
:int(ln(x)/ln(16))->N
:While N=>0
:int(X/16^N)->A
:prgmABCDEF //a convoluted piece of code that makes the program display A through F rather than 10 through 15, this line is essentially Disp A
:X-A16^N->X
:N-1->N
:End

This used to be over 30 lines of code but today it dawned upon me that I could find the nearest power of 16 by taking the log base 16 of a number. The rest I could explain but all of my energy went into writing it in the first place.

EDIT: I don't know what my pun means any more.
Last edited by alreadytaken4536 on Fri Feb 25, 2011 7:37 pm UTC, edited 1 time in total.

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: TI Basic Prime Factorer

Why not implement something like Shanks' square forms?

Posts: 34
Joined: Thu Jun 10, 2010 10:56 pm UTC

### Re: TI Basic Prime Factorer

I'm having a difficult time understanding that.

kriel
Posts: 922
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

### Re: TI Basic Prime Factorer

I can't dig up the code I used to make stuff work, but I remember some things I figured out.

• Anytime you use a GOTO before anything that finishes with an END; it leaks memory. That includes {"FOR","WHILE","IF"} and possibly a few others.
• Only check each possible factor once.
• Only check two and then the odds
• Only check up to the squareroot of the number for factors

These few steps alone should yield a scarily fast implementation. I'll guess at what it looked like.

Code: Select all

Prompt X
While fpart(X/2)=0
Disp 2
X/2 -> X
End
3 -> Y
While Y*Y < X
While fpart(X/Y)=0
Disp Y
X/Y -> X
End
End
If X =/= 1
Then
Disp Y
End

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: TI Basic Prime Factorer

You need to increments Y [by two].
ALSO: Even the measly 83 runs at 6 MHz. This is the age of computing. Everything is scarily fast.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -