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

Postby cmhhss1 » Tue Mar 24, 2009 4:04 pm UTC

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
Menu("Again?","Yes",2,"No", 3)
Lbl 3
Stop

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

Re: TI Basic Prime Factorer

Postby kriel » Wed Mar 25, 2009 12:30 am UTC

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
    Menu("Again?","Yes",2,"No", 3)
    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
    Menu("Again?","Yes",2,"No", 3)
    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
    Menu("Again?","Yes",2,"No", 3)
    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
Menu("Again?","Yes",2,"No", 3)
Lbl 3
Stop

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

Re: TI Basic Prime Factorer

Postby jaap » Wed Mar 25, 2009 12:53 am UTC

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

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

Re: TI Basic Prime Factorer

Postby psykx » Fri Mar 27, 2009 8:03 am UTC

hell if your optimizing you should only be testing the integers that conform to 6k+-1 :D
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.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: TI Basic Prime Factorer

Postby Xanthir » Fri Mar 27, 2009 11:46 am UTC

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

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

Re: TI Basic Prime Factorer

Postby alreadytaken4536 » Sat Jan 15, 2011 4:33 am UTC

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

Postby qbg » Sat Jan 15, 2011 6:48 pm UTC

Why not implement something like Shanks' square forms?

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

Re: TI Basic Prime Factorer

Postby alreadytaken4536 » Sun Jan 16, 2011 3:20 am UTC

I'm having a difficult time understanding that.

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

Re: TI Basic Prime Factorer

Postby kriel » Wed Jan 19, 2011 8:22 pm UTC

Reading back over this thread hurts my head, so bad. ><

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

Postby squareroot » Thu Jan 20, 2011 12:37 am UTC

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 - __ -


Return to “Coding”

Who is online

Users browsing this forum: Exabot [Bot] and 25 guests