TI Basic Prime Factorer

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

Moderators: phlip, Moderators General, Prelates

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

TI Basic Prime Factorer

Postby kriel » Wed Apr 30, 2008 12:39 am UTC

TI-Basic was my first programming language, and for some strange, sadistic reason, I ended up getting abit nostalgic. One of the things that always fascinated me and bugged me at the same time was my factoring program. I did the original naieve implementation, and figured it was good enough (a few futile stabs at it in high school yielded no real improvement).

However, the nostalgia came back, along with a better understanding of primes, and factors in general.

Under the spoiler is a description (the best I can word it) of the TI-basic environment. If you already know about it, skip ahead.

Spoiler:
The only variable types that are allowed are a messed up float/integer combination (Call it an integer for simplicity's sake) and a one-based array that allows 999 elements at most. (IE, an array[1-999]). Said array can only hold the integer(ish) variables mentioned above. You can modify elements in-place, and dynamically append to it, but you cannot make it sparse. (If it has an element n, it must have all elements from 1 to n). You cannot delete individual elements from the list (without wasting a lot of cycles), but you can clear the whole list at once.

If I remember correctly, you can only hold around 2300 elements in memory (each integerish value acts as an element, whether it's by itself, in an array, or otherwise.) however I may be slightly off on that number.

The processor is slow as a turtle, so even saving something as simple as a subtraction will make it noticably faster.


Here's psuedocode (runnable in python, but still not Ti-Basic, so the label 'psuedo' still applies) for what I wanted to do.

Code: Select all

n = 1009 * 2 #number to be factored
m = n #for the sake of not destroying the original

sieve = ['1']*1000 #don't use 0!
sieve[0] = 0 #for the hell of it
sieve[1] = 0 #ti fo lleh eht rof
pfacs = [] #prime factors
exitcode = 1 #0 is ok, 1 is too big a prime

for i in range(2,1000):
   if sieve[i]:
      #Look ma! it's prime!
      #Does it kill the number?
      while (m % i == 0):
         pfacs.append(i)
         m /= i
      if (m == 1):
         exitcode = 0
         break #I'm gonna get attacked by a raptor when I do this in TI-Basic
      #nope, keep going!
      j = 2
      while (i*j < 1000):
         #kill all the multiples!
         sieve[i*j] = 0
         j += 1
if exitcode:
   #yay! error handling!
   if exitcode == 1:
      print "Prime factor > 999 in number."
      print "Unresolved factor:",m
print "Prime factors found:"
print pfacs


Now, my question is:
can somebody suggest ways to get more than the primes < 1000, relatively progressively? (That way I can do the checking, and only find the biggest prime that I need to)

I had two thoughts. The first one was to backpedal slightly, and figure out each prime by doing a loop and testing it against all the previous primes. This would allow me to find the first 999 primes (as opposed to the primes < 999), however it would use more cycles and get rid of the elegance of erasthones' sieve. (And actually, I implemented this idea before as a simple prime-generator. I think I only found the first 500 or so before it ran out of memory, and even that took ages.)

The other idea was to save the primes in a second list. When I exhaust the first list (find all the primes < 999) clear it and then find all the primes from 1000 - 1998 (I'd have to iterate over the old list of primes to re-scratch out their multiples, but if you've got a prime > 1000, it's gonna take some serious cycles anyway.) In effect, paging out the sieve as I use it up.

I haven't managed to dig my old TI up out of whatever box it's hiding in, so I can't test the effectiveness of this algorithm yet (plus I'm describing the TI environment out of memory), but it feels promising. Plus, instant prime factors of 2002! (2002 factorial) was quite impressive. (Albeit, it was in python, but still.)

Here's a one-liner for factorial if you feel like feeding the program gawdawful numbers. (when I was testing it, I meant to type 2002, not fact(2002), but hey. I'm still being impressed over that.)

Code: Select all

def fact(x): return reduce(lambda x, y: x*y, xrange(2, x+1))


Suggestions? Comments? Kudos? Cookies?

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: TI Basic Prime Factorer

Postby Robin S » Wed Apr 30, 2008 12:46 am UTC

The Sieve of Eratosthenes is nice because it is simple, but there are many more efficient ways to find primes if you are interested. In particular, the AKS Primality Test runs in polynomial time, though I don't know enough details to know whether that would be practical for you to try to implement.
This is a placeholder until I think of something more creative to put here.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Wed Apr 30, 2008 1:04 am UTC

If you're finding a list of primes is in order to factor one number, there's really no reason. If you intend to precompute the primes so that you could use the list for factoring a bunch of numbers, that's different. But the way you have it, you'll get more efficiency by just testing every factor and not worrying about whether it's prime or not. This won't print out any non-prime factors, if that concerns you. This is because by the time you're testing for divisibility by 6, you've already checked for divisibility by 2 and 3 and divided them out, so you know that 6 won't divide what you're left with.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: TI Basic Prime Factorer

Postby Robin S » Wed Apr 30, 2008 1:18 am UTC

Actually, it could return prime power factors. But I don't see why you assume that the list of primes is being used to test for factors.
This is a placeholder until I think of something more creative to put here.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Wed Apr 30, 2008 1:34 am UTC

Take a closer look: testing for factors is what the program does. Finding primes is just done along the way. The sieve array doesn't get used after the loop, only the pfac array does.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: TI Basic Prime Factorer

Postby Robin S » Wed Apr 30, 2008 1:47 am UTC

Sorry, I didn't actually look at the code really, since I haven't used TI Basic and am too tired to spend the time working it out - only at the textual content. Now that I look at it, you are absolutely and obviously right.
This is a placeholder until I think of something more creative to put here.

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 Apr 30, 2008 2:05 am UTC

Cosmologicon wrote:If you're finding a list of primes is in order to factor one number, there's really no reason. If you intend to precompute the primes so that you could use the list for factoring a bunch of numbers, that's different. But the way you have it, you'll get more efficiency by just testing every factor and not worrying about whether it's prime or not.


But if I run the sieve along the way, I can test ONLY prime numbers. I'm not really 'precomputing' them, I'm more reducing the factors that I have to try.

Though, I suppose it might take more cycles to scratch out all the not-primes than to just try them along the way. Is that what you're trying to say?

My original idea was to use the same seive for multiple numbers (say, finding the GCD or LCM of a list) but I'm starting small, for now.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Wed Apr 30, 2008 2:24 am UTC

kriel wrote:it might take more cycles to scratch out all the not-primes than to just try them along the way. Is that what you're trying to say?

Yes. That's definitely the case.

Now, having a list of primes isn't a bad idea, and if you have it then you might as well use it. But if you want to know how to optimize your factorizer, either precompute the prime list or don't compute it at all.

If you are going to get the list of primes, what Robin said about the sieve being inefficient is true. However, for the primes you're looking at (only up to a few thousand) sophisticated primality tests are not the way to go either. The best method for your application is simply to check each number to see if it's divisible by any smaller prime in your list. (And actually, you only need to check primes up to the square root of n.)

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 Apr 30, 2008 2:37 am UTC

Well, what I'm doing right now, is I'm finding all the primes up to whatever the largest prime in the list is.

Lets say I ask it for the pfacs of 1024 (2^10).

It'll find 2 as the first prime, take all the 2's out of 1024, and say it's done. That's all it's factors.

It can't go past the sqrt of the number, because if it's got a factor bigger than it's squareroot, we just broke the maths.

However, if I give it 1009 * 2, it'll give me 2, and then say that it couldn't factor 1009 (because those primes are too big)

The only reason I even have that limit is that it's the maximum I can hold in the array for the sieve.

I can't precompute, because storing that array in the program eats up space. (Though, not as much as other possible methods.)


... I think you answered my question. It'd take less cycles (and less space) to just try all factors. Plus it'd get rid of that limit.

... I can't shake that feeling that I'm losing some time by just trying all factors, though, instead of just trying the primes...

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: TI Basic Prime Factorer

Postby Robin S » Wed Apr 30, 2008 3:02 am UTC

kriel wrote:It can't go past the sqrt of the number, because if its smallest factor is bigger than its squareroot, we just broke the maths.
Fixed that for you. A number can easily have factors, even prime factors, larger than its square root. Take 6. That has 3 as a prime factor, and 3 is bigger than the square root of 6.
However, if I give it 1009 * 2, it'll give me 2, and then say that it couldn't factor 1009 (because those primes are too big)
Couldn't it just test everything up to 31 (the largest integer below the square root of 1009) and, upon finding that nothing divided 1009, deduce that it was prime? You wouldn't reach any problems until you tried testing numbers with prime factors larger than a million.
... I can't shake that feeling that I'm losing some time by just trying all factors, though, instead of just trying the primes...
Try to. Sometimes redundancy is necessary.
This is a placeholder until I think of something more creative to put here.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: TI Basic Prime Factorer

Postby Berengal » Wed Apr 30, 2008 3:30 am UTC

Then try every second factor, much like you would with a naive prime-finder. 2 is the only even number you'll have to try. Again, you just need up to (and including) the square-root. If what you're left with after factoring up to the square-root isn't 1, then it's guaranteed to be prime. Simply append.

Pseudopythoncode:

Code: Select all

number = 1009*2
n = number
factors = []
while n % 2 == 0:
  factors.append(2)
  n = n / 2

sroot = sqrt(n)
p = 3
while n != 1 and p <= sroot:
  if n % p == 0:
    factors.append(p)
    n = n / p
  else:
    p += 2
if n != 1:
  factors.append(n)
print factors


Hmm... There's also the fact that every prime except 2 and 3 can be written as 6k +- 1, which is (5 + 2) + (4 + 2) + (4 + 2) etc. Not every 6k+-1 is prime, but only two thirds of all odd numbers can be written like that. Now we're down to 1/3 of all integers 1 < p < sqrt(n), where n is the factorized number.
Revised code (guaranteed runnable python):

Code: Select all

from math import sqrt

number = 10**99
n = number
factors = []
while n % 2 == 0:
    factors.append(2)
    n = n / 2
while n % 3 == 0:
    factors.append(3)
    n = n / 3
   
sroot = sqrt(n)
p = 5
while n != 1 and p <= sroot:
    while n % p == 0:
        factors.append(p)
        n = n / p
    p += 2
    while n % p == 0:
        factors.append(p)
        n = n / p
    p += 4
   
if n != 1:
    factors.append(n)
print factors

Note: I haven't profiled any of this, so I don't know what'll be fastest. This uses significantly less memory than a sieve, as it doesn't have to remember primes, just the factors it has found. It factorized 10**99 easily enough (only has 2 and 5 as factors, so duh), but it's taking it's time on 10**99+1. It does fine on semi-large arbitrary numbers I've arbitrarily mashed in, such as 9851687423 (which incidentally is prime, and thus the slowest to find), so it's probably not too bad an algorithm. How it works on toy-cpus I don't know.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: TI Basic Prime Factorer

Postby Robin S » Wed Apr 30, 2008 3:36 am UTC

Berengal wrote:9851687423
Almost exactly a 1 in 23 chance of a number that size being prime. Looks like you did quite a bit of testing.

And yeah, 1099+1 would probably take a while, even in Maple.
This is a placeholder until I think of something more creative to put here.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: TI Basic Prime Factorer

Postby Berengal » Wed Apr 30, 2008 3:44 am UTC

Robin S wrote:
Berengal wrote:9851687423
Almost exactly a 1 in 23 chance of a number that size being prime. Looks like you did quite a bit of testing.

And yeah, 1099+1 would probably take a while, even in Maple.

I just ran my fingers across the keypad for those large numbers. The size difference between them was probably large, since I wasn't aiming for a specific amount of digits.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

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

Re: TI Basic Prime Factorer

Postby cmhhss1 » Thu Feb 12, 2009 8:19 pm UTC

Hey, I'm a junior in high school at the moment, and I've actually been playing arround with my calculator and with prime numbers whenever I'm bored in math class. TI Basic is also my first programming language, though I do a tiny bit of C++, but i think I've managed to create a number of interesting prime-programs; namely, one which factors any numer that the user inserts, one which lists all of the primes beginning with 2 (which crashes due to limited memory space at 173), and one which simply determines whether or not a number is prime.

Are any of these the kind of program you're looking for?

Edit: I just realized how long after the original (and most recent) posts this is, so I'd like to revise my previous query to read "Do you still need any of these programs?"

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 » Thu Feb 12, 2009 9:46 pm UTC

cmhhss1 wrote:one which lists all of the primes beginning with 2 (which crashes due to limited memory space at 173)

Which calculator are you using? My TI-83 was able to list a ton more primes than that.

I suppose it's possible that you just have a lot more programs on your calc than I do.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: TI Basic Prime Factorer

Postby cmhhss1 » Thu Feb 12, 2009 10:27 pm UTC

Xanthir wrote:
cmhhss1 wrote:one which lists all of the primes beginning with 2 (which crashes due to limited memory space at 173)

Which calculator are you using? My TI-83 was able to list a ton more primes than that.

I suppose it's possible that you just have a lot more programs on your calc than I do.


I only have about 20 programs on my calculator, and I know that part of the problem is in the nature of my program, which I've been refining since Tuesday (3 days ago). It started crashing at 37, then I got it to go until 71, then until 101, then 109, then 173, and that's where I left off. I've only been programming this thing for a month or so now, so there's still a lot I've got to learn :(

If you'd like to see the code I'm currently using, here it is (not including TI Line Delineating Colons):

Code: Select all

Clrhome
2 -> X

Lbl 1
     DelVar Y
     2 -> Y

Lbl 2
     If int(X/Y)=(X/Y) and Y< or =(x^.5)
          Then
          X+1 -> X
          Goto 1
          End
     If Y< or = (x^.5)
          Then
          Y+1 -> Y
          Goto 2
          End

If Y>(x^.5)
Then
Disp X
x+1 -> X
Goto 1
End


Feedback is greatly appreciated, though if code could go in spoilers then I would like to try to figure it out for myself!

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 Feb 13, 2009 1:02 am UTC

Well, for some easy optimizations, realize that past 2 every prime number will be odd. So you can just hard-code the 2 value and *really* start with 3, then go up by +2 every time. This works for both the number you are testing and the numbers you're testing with.

Second, there is this thing called a for loop. Learn it. ^_^ Your goto-based programming is quite unnecessary here. It'll make your code a lot clearer. It'll also reduce the number of times you have to calculate sqrt(X) to 1, rather than every single loop like you're doing now.

Third, the best optimization is to use the primes you've already generated as the divisors for future primes. That way you don't waste time dividing by composites. Look into how your calculator implements Lists, and store your primes in a list as you go along.

As an added bonus, a List (at least on my TI-83) is a persistent data structure, so you can keep it around between invocations. I had a prime finder fill two lists completely (9999 entries each) and was in the middle of a third when I quit. Of course, those also take up valuable memory, so as the lists filled I was able to find less and less primes before a crash. ^_^ I just let it run whenever I wasn't doing anything in particular, and periodically restarted it when it crashed.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: TI Basic Prime Factorer

Postby cmhhss1 » Fri Feb 13, 2009 1:09 am UTC

Xanthir wrote:Well, for some easy optimizations...


Thanks! I already thought of the odd thing with the hard-coding 2, but that's cheating so I want to see if i can also program it without losing too much memory.
Also, I know loops but I like the If-Goto structure. I'll try loops if you think it'll work :)
Finally, I'm DEFINITELY going to have to look into the List thing because atm all I know how to store things as are strings and single letter variables :shock:

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 Feb 13, 2009 1:12 am UTC

cmhhss1 wrote:Thanks! I already thought of the odd thing with the hard-coding 2, but that's cheating so I want to see if i can also program it without losing too much memory.

2 is a special case. It's even more special because it's the first. Hard-coding it isn't cheating. ^_^

Also, I know loops but I like the If-Goto structure. I'll try loops if you think it'll work :)

You would do yourself immense good by forgetting that goto exists. You can remember it later in the excessively rare circumstances it is warranted. If you work with a decent language, you'll have enough structured goto-like things that you'll never have to use goto itself at all.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: TI Basic Prime Factorer

Postby cmhhss1 » Fri Feb 13, 2009 1:18 am UTC

Xanthir wrote: You would do yourself immense good by forgetting that goto exists.


Oh wow, you were completely correct!

New Code:
(CHEATING) is not part of the actual code btw... :wink:

Code: Select all

Disp 2 (CHEATING)
For(X,3,1000,2)
     DelVar P
     For(Y,3,1000,2)
          If int(x/y)=(x/y) and sqrt(x)>= 3
          Then
               P+1->P
          Else
          End
     End
     If P=0
     Then
          Disp X
     End
End

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 » Fri Feb 13, 2009 2:14 am UTC

Note that using the builtin menus in the TI calculator (argh) requires the use of labels (each choice runs a different goto). So; it's either write your own menu or deal with it.

That said; I haven't found any other use for GOTOs in TI-land. (Except possibly simulating subroutines; and that's a big possibly.)

As for the program; I've since optimized my programs quite nicely, thanks to someone's suggestions up there.

Psuedocode: (written out of memory; so if it doesn't work; don't blame me)

Code: Select all

factors = []
input "number to be factored",c
c -> a
2 -> b
while sqrt(a) < b
     if fpart(a/b) = 0
     then
          a/b -> a
          factors += [b]
          b -= 1
     end
     b += 1
end

and just in writing that out i realized i could do the 2 'cheat'. Oops. Oh well; it's still fairly good on time; especially if you only put 'sane' numbers into it. (IE: largest values of factors are less than a few hundred.)

as for finding all the primes (as a seperate exercise)...

Code: Select all

primes = [2,3]
a = 5
while 1
     b = 1
     c = 1*
     while b < dim(primes) and c**
          if fpart(a/primes[b]) = 0
               c = 0
          b += 1
     end
     if c
          primes += [a]
     a += 2
end

*c is acting as a boolean, basically 'ohshit it didn't work'
**this is emulating a for loop, allowing c to break it if need be

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

Re: TI Basic Prime Factorer

Postby cmhhss1 » Fri Feb 13, 2009 2:48 am UTC

Ok, not to sound like a total idiot or anything, but if you want a really rudimentary factor program, here's one with Goto's and Lbl's...

Code: Select all

ClrHome
Delvar x
DelVar Y

Lbl 0
     2 -> Y
     0 -> P
Lbl 1
     If int(x/y)=(x/y) and y= or < sqrt(x)
     Then
          Disp Y
          x/y -> x
          Goto 0
     End

     If int(x/y)!=(x/y)and y= or < sqrt(x)
     Then
          Y+1->Y
          Goto 1
     End

     If Y>sqrt X
     Then
          Disp X
          Stop
     End

User avatar
icewind
Posts: 43
Joined: Wed Dec 31, 2008 12:41 pm UTC
Location: Netherlands
Contact:

Re: TI Basic Prime Factorer

Postby icewind » Fri Feb 13, 2009 3:40 pm UTC

kriel wrote:as for finding all the primes (as a seperate exercise)...

Code: Select all

primes = [2,3]
a = 5
while 1
     b = 1
     c = 1*
     while b < dim(primes) and c**
          if fpart(a/primes[b]) = 0
               c = 0
          b += 1
     end
     if c
          primes += [a]
     a += 2
end

*c is acting as a boolean, basically 'ohshit it didn't work'
**this is emulating a for loop, allowing c to break it if need be

Hmm, after reading the first few posts of this topic before school I made a prime finder in TI-Basic using exactly this method.
It was able to find 999 prime numbers in about 20 minutes and after that it gave a domain error fot trying to add the 1000's element to the list

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: TI Basic Prime Factorer

Postby Random832 » Fri Feb 13, 2009 7:48 pm UTC

You should recalculate sroot inside the loop whenever you update n.

Also, it may be faster to check p*p vs n rather than p vs sqrt(n), if you can guarantee p*p won't overflow (though, if it does overflow, it has to be > n, right?)

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 » Fri Feb 13, 2009 9:54 pm UTC

icewind wrote:Hmm, after reading the first few posts of this topic before school I made a prime finder in TI-Basic using exactly this method.
It was able to find 999 prime numbers in about 20 minutes and after that it gave a domain error fot trying to add the 1000's element to the list
Using what model? My TI-83+ Silver stalled out when I tried to run it (though; I could always start it again. It got a little farther each time I started it.) (I haven't tried it on an 84 Silver yet)

Random832 wrote:You should recalculate sroot inside the loop whenever you update n.
It recalculates it when it checks the condition on the while loop.

Random832 wrote:Also, it may be faster to check p*p vs n rather than p vs sqrt(n), if you can guarantee p*p won't overflow (though, if it does overflow, it has to be > n, right?)
It's v. hard to make a TI overflow. So long as you give it relatively sane numbers; it should be okay. I didn't think about the calc time for squaring vs. sqrt, however.


And now for a challenge:

I've gotten the part where I get the prime factors of a number relatively optimized. Still not perfect; but optimized nonetheless.
... Now, does anybody have any ideas for getting said array of prime factors BACK into a list of factors for the original number?

-No recursion (It's all in the same scope) so trying to do the usual ways to get permutations is out.

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 Feb 13, 2009 11:27 pm UTC

kriel wrote:
Random832 wrote:You should recalculate sroot inside the loop whenever you update n.
It recalculates it when it checks the condition on the while loop.

He means, do it that way for efficiency. Sqrt is relatively expensive, and you're recalculating it for every Y, when it's only going to change when X changes. So, before Y's for loop, store the sqrt of X in a temporary variable, and test against that instead.


Random832 wrote:Also, it may be faster to check p*p vs n rather than p vs sqrt(n), if you can guarantee p*p won't overflow (though, if it does overflow, it has to be > n, right?)
It's v. hard to make a TI overflow. So long as you give it relatively sane numbers; it should be okay. I didn't think about the calc time for squaring vs. sqrt, however.

As well, there *may* be differences in comparing int/int and comparing int/float. This is totally out of my ass, though; I dont' know if there is a difference, or if it matters enough to care.

And now for a challenge:

I've gotten the part where I get the prime factors of a number relatively optimized. Still not perfect; but optimized nonetheless.
... Now, does anybody have any ideas for getting said array of prime factors BACK into a list of factors for the original number?

-No recursion (It's all in the same scope) so trying to do the usual ways to get permutations is out.

Read this for a nice introduction to the permutation iterator. Completely non-recursive, but it does depend on the ability to reverse a list. Don't know if you can do that.

Alternately, use a factoradic index, and manually parse it into a permutation.

However, if you're trying to find proper factors (not just prime factors), then using primes to do it is actually rather slow. It's best to just iterate through all numbers from 2 to sqrt(n), listing each one that divides it evenly (and the other number, ie, if x divides n, then n/x = y is also a factor). At least, that was my experience implementing a proper-factors function.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Fri Feb 13, 2009 11:51 pm UTC

Xanthir wrote:if you're trying to find proper factors (not just prime factors), then using primes to do it is actually rather slow. It's best to just iterate through all numbers from 2 to sqrt(n), listing each one that divides it evenly (and the other number, ie, if x divides n, then n/x = y is also a factor). At least, that was my experience implementing a proper-factors function.

My intuition suggests that this would work well for small (< 10,000) n, but becomes extremely sub-optimal for numbers with several small factors. If you want a proper-factor function, I think it would be worthwhile to make one that builds it from the prime factor list. I don't see how permuting the list would help you do this, though. Can anyone explain?

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

Re: TI Basic Prime Factorer

Postby cmhhss1 » Sat Feb 14, 2009 12:12 am UTC

My program isn't optimal or anything, but can anyone tell my why it wouldn't work? It runs perfectly well with large numbers (n>10000) and is fairly quick.

Code: Select all

Clrhome
Prompt X
Lbl 1
For(Y,2, sqrt X)
     x -> A
     If X/Y=int(x/y)
          Then
          Disp Y
          X/Y -> X
          Goto 1
     End
End

If X=A
     Then
     Disp A
End
Disp "DONE!"

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 » Sat Feb 14, 2009 12:13 am UTC

If you're relatively sure that you're working with numbers with small numbers of factors, then yeah, it's probably faster using the prime list. My actual experience doing a PE problem, though, is that just running through every candidate number with trial division is faster on average.

As for permutatiosn, I had a huge brain fart. You *don't* use permutations, you use a powerset. Take a prime decomposition. Find the powerset. For each member of the powerset, multiple all the numbers within it. Remove duplicates (implicit in the definition of a set, but not if you're using a list or something). What you have left are the proper factors.

In that case, ignore the factoradics. Binary numbers index powersets in the same way, and they're simpler to use.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Sat Feb 14, 2009 1:08 am UTC

Xanthir wrote:If you're relatively sure that you're working with numbers with small numbers of factors, then yeah, it's probably faster using the prime list. My actual experience doing a PE problem, though, is that just running through every candidate number with trial division is faster on average.

Like I said, this is counterintuitive to me. I would believe your method's slightly faster for small n, just because it avoids some overhead, but once n gets even medium-sized, I would expect it to never be better, and sometimes be much worse, than building from a list of prime factors.

I tried it in python on 100,000 random 6-digit numbers. Your method took 16 seconds compared with prime-factoring's 13. For 100,000 random 7-digit numbers, your method took 47 seconds compared with prime-factoring's 31. So I guess my actual experience conflicts with yours.

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 » Sat Feb 14, 2009 3:00 am UTC

cmhhss1 wrote:My program isn't optimal or anything, but can anyone tell my why it wouldn't work? It runs perfectly well with large numbers (n>10000) and is fairly quick.

Code: Select all

Clrhome
Prompt X
Lbl 1
For(Y,2, sqrt X)
     x -> A
     If X/Y=int(x/y)
          Then
          Disp Y
          X/Y -> X
          Goto 1
     End
End

If X=A
     Then
     Disp A
End
Disp "DONE!"
That's similar to mine. It just has a few things different.
-It doesn't save the prime factors while printing it. If there's a lot of 2's and 3's the screens gonna scroll too fast for you to read it.
-It starts over at 2 every time it finds a new factor. Once you get all the 2's out; there's no point in checking for any more 2's. (Note the difference between ONE two and ALL the twos.)
-It checks every number. It's a fairly simple change to make it check only odd numbers.

Mmmmm yeah.

[[I'm still absorbing wtf happened about the figuring out all primes while I was gone. Why wouldn't it be faster to multiply the prime factors we've already got in favor of going out and finding all the factors the hard way?]]

EDIT: Yes! Power sets! That's what I wanted. I must have mixed up what permutations are. >< My bad.
But yeah. Now; all I gotta figure out how to do is... uh... generate power sets on a TI. Fuck.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Sat Feb 14, 2009 4:11 am UTC

kriel wrote:... Now, does anybody have any ideas for getting said array of prime factors BACK into a list of factors for the original number?

-No recursion (It's all in the same scope) so trying to do the usual ways to get permutations is out.

As I mentioned, I don't know what the usual ways are, but here's how I would do it. It's easier to build the list of factors while you're finding the prime factors. Failing that, you should keep track of the multiplicity of each prime factor while you're finding them. Failing that, if all you have is a list of (possibly repeated) primes, I still think it's most efficient (on average, for large-ish n) to reconstruct the multiplicity of each prime factor and do something like the following. But the best way to do it is to get the factors along with the prime factors:

Code: Select all

  m = n  # copy of number to be factorized
  f[0] = 1  # array of factors
  nfac = 1  # number of factors
  for (p = 2 ; p < m ; p += 1) {
    if (p^2 > m) p = m
    z = nfac
    j = 0
    while (m % p == 0) {
      m /= p
      for ( ; j < nfac ; j += 1) {
        f[j+z] = f[j] * p
      }
      nfac += z
    }
  }

I think that should be pretty straightforward, but apparently my code isn't as clear as I think it is.

Power sets might be a little simpler, but when you have a highly repeated factor they'll be highly sub-optimal.

User avatar
icewind
Posts: 43
Joined: Wed Dec 31, 2008 12:41 pm UTC
Location: Netherlands
Contact:

Re: TI Basic Prime Factorer

Postby icewind » Sat Feb 14, 2009 10:49 am UTC

kriel wrote:
icewind wrote:Hmm, after reading the first few posts of this topic before school I made a prime finder in TI-Basic using exactly this method.
It was able to find 999 prime numbers in about 20 minutes and after that it gave a domain error fot trying to add the 1000's element to the list
Using what model? My TI-83+ Silver stalled out when I tried to run it (though; I could always start it again. It got a little farther each time I started it.) (I haven't tried it on an 84 Silver yet)

I have a TI-84+
But one thing you also have to take care of, is that TI-BASIC has some memory leaks if you use variables the wrong way, the first time I I will post the source sometimes but I don't have my TI now.

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 » Sat Feb 14, 2009 2:33 pm UTC

Cosmologicon wrote:
Xanthir wrote:If you're relatively sure that you're working with numbers with small numbers of factors, then yeah, it's probably faster using the prime list. My actual experience doing a PE problem, though, is that just running through every candidate number with trial division is faster on average.

Like I said, this is counterintuitive to me. I would believe your method's slightly faster for small n, just because it avoids some overhead, but once n gets even medium-sized, I would expect it to never be better, and sometimes be much worse, than building from a list of prime factors.

I tried it in python on 100,000 random 6-digit numbers. Your method took 16 seconds compared with prime-factoring's 13. For 100,000 random 7-digit numbers, your method took 47 seconds compared with prime-factoring's 31. So I guess my actual experience conflicts with yours.

I may have been lazy and just consed up a goddam storm of throwaway lists in the process, thus making it slower. IIRC, my code was pretty much exactly (remove-duplicates (mapcar (curry 'reduce '*) (powerset (factorize x)))). I will return to this with further, more efficient experiments later.

But yeah. Now; all I gotta figure out how to do is... uh... generate power sets on a TI. Fuck.

Cosmo brought up good points, but if you do still want to do plain powersets it's very easy.

Like I mentioned, powersets are 'indexed' by binary numbers. Say you have a 5-element set. The powerset will contain 32 sets. A 5 digit binary number can represent 32 different things.

Specifically, every set of the powerset either has a particular element from the original set, or doesn't. If you assign one digit to each original element, then, you can express any of the sets as a string of five 0s and 1s, which can be interpreted as a binary number. If you list all of the powerset, you just so happen to get every number from 0 ("00000") to 31 ("11111").

Since binary numbers are easy to work with, this makes it relatively easy to move through the powerset.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: TI Basic Prime Factorer

Postby Cosmologicon » Sat Feb 14, 2009 5:58 pm UTC

Xanthir wrote:if you do still want to do plain powersets it's very easy.

Like I mentioned, powersets are 'indexed' by binary numbers. Say you have a 5-element set. The powerset will contain 32 sets. A 5 digit binary number can represent 32 different things.

Specifically, every set of the powerset either has a particular element from the original set, or doesn't. If you assign one digit to each original element, then, you can express any of the sets as a string of five 0s and 1s, which can be interpreted as a binary number. If you list all of the powerset, you just so happen to get every number from 0 ("00000") to 31 ("11111").

Since binary numbers are easy to work with, this makes it relatively easy to move through the powerset.

Since we don't actually need the power set - just the product of each member of the power set - we can find it somewhat more simply (and slightly more efficiently). Here's how it might look in python (because that's all I got ATM). It would probably be simpler in Lisp and more complicated in TI-Basic:

Code: Select all

factors = [1]
for p in primefactors:
  factors += [f * p for f in factors]

EDIT: And along these same lines, if you actually do want the power set, that's a little simpler too if your language supports nested lists. I'm not sure it would work well in TI-Basic, though:

Code: Select all

powerset = [()]
for p in primefactors:
  powerset += [s + (p,) for s in powerset]

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 » Sat Feb 14, 2009 10:30 pm UTC

Don't have enough time to fully comprehend everything here; but read the OP for a description of the TI environment.

one type of variable, a float.
one type of list, is 1-indexed [1-999] and can hold 999 elements of the type of variable described above. (Which means no nesting lists.)
one scope.
goto's are static.

uhhh... any other questions?

[still thinking about the 'generate factors as you find the prime factors' bit.] [I'm curious about these memory leaks, too]

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 » Sat Feb 14, 2009 11:06 pm UTC

Maybe it's easier to understand as Lisp?

Code: Select all

(loop with factors = (list 1)
      for p in (factorize 40)
      do (setf factors (nconc factors (map_ (* p _) factors)))
      finally (return factors))

nconc is a function which joins two lists. Map_ applies a function (the (* p _) thing) to every element of a list, substituting the _ for the element.

The problem with this is that you still need to run a remove-duplicates over the output, as running the above (which finds the proper factors of 40, obviously) returns (1 2 2 4 2 4 4 8 5 10 10 20 10 20 20 40). Considering that it also does things which are relatively difficult to accomplish in TI-BASIC (and I have no clue about their performance characteristics), I still recommend a simple trial-division through the numbers:

Code: Select all

(loop with n = 40
      for x from 2 to (floor (sqrt n))
      if (zerop (mod n x))
        collect x
        and collect (/ n x))

Note: this code does *not* return 1 or n as a factor. If you want them, just add them in manually.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
PM 2Ring
Posts: 3701
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: TI Basic Prime Factorer

Postby PM 2Ring » Wed Feb 18, 2009 12:24 pm UTC

Here's how I find all factors in Python. The mixed base counting iterator comes in handy for other permutation generator tasks, too.

mbcount.py

Code: Select all

#! /usr/bin/env python

'''
Mixed base counting iterator

The digits are stored in a list, with the msd in the zeroth element.
Initializer t is a list containing the bases, in the same order.
'''

def mbc(t):
  lt = len(t)
  v = lt*[0]
  lt -= 1
  while True:
    yield v
    k = lt
    v[k] += 1
    while v[k] == t[k]:
      v[k] = 0
      k -= 1
      if k<0: return
      v[k] += 1

def main():
  t = [int(s) for s in sys.argv[1:]] or [4,3,2]
  print '<%s>' % t
  for p in enumerate(mbc(t)):
    print '%3d: %s' % p

if __name__ == '__main__':
  import sys
  main()


factorize.py

Code: Select all

#! /usr/bin/env python

import sys

def fac():
  ''' Make a generator for the sequence [2, 3, 6n-1, 6n+1, ...]'''
  for i in [2, 3]:
    yield i
  i = 6
  while 1:
    yield i - 1
    yield i + 1
    i += 6

def factorize(m):
  """ Put prime factors of m into a list of tuples (p, power) """
  f = fac()
  s = []
  for p in f:
    if p*p>m:
      s.append((m,1))
      break
    if m%p == 0:
      k = 0
      while m%p == 0:
        m /= p
        k += 1
      s.append((p,k))
      if m==1:
        break
  return s

def main():
  m = len(sys.argv) > 1 and int(sys.argv[1]) or 20
  #for i in xrange(1,m): print i, factorize(i)
  print factorize(m)

if __name__ == '__main__':
  main()


allfactors.py

Code: Select all

#! /usr/bin/env python

''' Generate all factor pairs of m as a list of tuples '''

from factorize import factorize
from mbcount import mbc

def allfactors(m):
  ''' Generate all factor pairs of m as a list of tuples '''
  #Get prime factorization, as a list of tuples (p, power)
  pf = factorize(m)
  #Put smallest factor last.
  pf.reverse()
  #Unzip.
  pr = [u for u,v in pf]    #primes
  pw = [v+1 for u,v in pf]  #powers plus one

  #Count using a mixed base iterator.
  f = [reduce(lambda u,v:u*v, [u**v for u,v in zip(pr, k)], 1) for k in mbc(pw)]
  ff = [(u, m/u) for u in f if u <= m/u]
  ff.sort()
  return ff

def main():
  m = len(sys.argv) > 1 and int(sys.argv[1]) or 120
  print allfactors(m)

def test():
  m1 = len(sys.argv) > 1 and int(sys.argv[1]) or 120
  m0 = len(sys.argv) > 2 and int(sys.argv[2]) or m1
  if m0>m1:
    m0, m1 = m1, m0
  for u, v in [(i, allfactors(i)) for i in xrange(m0, m1+1)]:
    #print "%2d: %s" % (u, v)
    print "\n%2d:" % u,
    for j,k in v:
      print "%2d * %2d," % (j, k),

if __name__ == '__main__':
  import sys
  #main()
  test()

User avatar
darkspork
Posts: 532
Joined: Tue Sep 23, 2008 12:43 am UTC
Location: Land of Trains and Suburbs

Re: TI Basic Prime Factorer

Postby darkspork » Thu Feb 19, 2009 4:58 pm UTC

Ah yes, the TI 84. If you want, you can have a piece of my nostalgia.
http://home.adelphi.edu/~cd17347/TIIDE_2.7.01.zip
I wrote this in visual basic back when, because TI made no compiler for Windows. Macs have an editor for this, but I don't think Linux does. *gets idea to translate this into Python...

BTW that calculator is slow as fuck. I remember it taking over five minutes to execute a simple loop 32768 times. :\
Shameless Website Promotion: Gamma Energy
My new esoteric programming language: GLOBOL
An experiment to mess with Google Search results: HARDCORE PORNOGRAPHY HARDCORE PORNOGRAPHY

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 18, 2009 5:34 pm UTC

Code: Select all

input X
clrlist L1 //list of prime factors
{1} -> L2 //list of all factors
X -> A //current number we're trying to find factors of
2 -> B //current number we're trying to divide by
1 -> C //control var. 0 = break; 1 = normal; 2 = last repetition
while C
    while fpart(A/B)=0
        B -> L1(Dim(L1)+1) //this mess of a construct adds B to the end of the list.
        A/B -> A
        augment(L2, L2 * B) -> L3 //augment concatenates the lists.
        //from here to the end of this while loop is simply removing the duplicates from L3
        SortA(L3)
        -1 -> E
        ClrList L2
        for(D,1,Dim(L3))
            if L3(D) != E
            then
                L3(D) -> L2(Dim(L2)+1)
                L3(D) -> E
            end
        end
    end
    B+2 -> B
    if B = 4
        3 -> B
    if C = 2 or A = 1
        0 -> C
    if B > sqrt(A) and C = 1
    then
        2 -> C
        A -> B
    end
end
//variable cleanup. Optional, really.
clrlist L3
delvar A
delvar B
delvar C
delvar D
delvar E


There you go. Fairly optimized; finds both prime and all factors.

I'm still waiting for someone to give more info on these memory leaks.

Edit: Found some! http://tibasicdev.wikidot.com/memory-leaks
I don't remember using ANY gotos in my primefinder programs though; so I'm not quite sure how I ended up leaking memory...


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests