factall() v1.0 - Quickly Find *ALL* Factors of an Integer released 2003-06-22 for the TI-89 by Jeff Connelly / shellreef The Need For FactAll() ====================== The TI-89 provides a fast, built-in factor() function for complete prime-factorization of integers. However, there are often additional, composite factors not returned by factor(). factall(x) returns a list of all the factors of x, including: - 1 - x - prime factors - composite factors, if any - negative integers, if x is negative factor(18) returns: 2 * 3^2 -- only primes factall(18) returns: {1 2 3 6 9 18} -- everything The Speed of FactAll() ====================== It is written in BASIC, but runs relatively quickly. factall relies on factor() to find the prime factors, and from there additional factors, if any, are calculated. This means that factall() takes only slightly longer than factor(). Usage ===== Copy main.factall.89f to your TI-89 using a link cable. Just type factall(, the integer you wish to factor, and a closing ")". TIP: If you don't want to type the closing brace (who does?), install Kevin Kofler's excellent AutoClBr program. Search Google to find it, I highly recommend it. http://members.chello.at/gerhard.kofler/kevin/ti89prog.htm#autoclbr Additional Information ====================== That's all you need to know to use factall! But if you want to know more about factoring, continue reading. Version History --------------- 1.0 initial release FAQ --- Q: Is factall fast? A: I tried to make it fast. Let me know if you have any speed improvements. Note that factall() will never be faster than factor(). Q: Can factall() factor negative integers? A: Yes. factall'ing a negative will return both positive and negative factors. factall(-4) => {1 -1 2 -2 4 -4} Q: Does factall() always return negative factors? A: No. Negative factors are only returned if the argument is negative. If you want to have a list of negative and positive factors, do something like this: augment(factall(6), -factall(6)) Q: Is the list returned by factall() in numerical order? A: No; TI does not allow SortA or SortD to be called within a function, so the returned list is left unsorted. It is, however, in a rough numerical order. See "Technical Overview" for details. Q: Can factall() factor polynomials or other equations? A: No. Use factor() for that. You'll get an error if you try it. Q: Can factall() factor irrational or complex numbers? A: It tries, but it may not always suceed. Q: I have a suggestion/comment/patch/money to give you. A: Contact me at ticalc-factall@xyzzy.cjb.net. Feedback is greatly appreciated. Rejected Factoring Methods -------------------------- Divide x by 2 to x/2, returning integers that divided in evenly. This is the most naive and slow factoring method. TOO SLOW! Divide x by 2 to sqrt(x), noting which integers divide evenly and their quotient. This is slightly faster, but BASIC cannot match TI's built-in factor() function. STILL SLOW! Technical Overview ------------------ factall(x) calls factor(x), and then proceeds to parse the returned expression into the prime factors (pfc list) and their exponents (expn array). This takes a lot of code, because factor() returns a human-readable expression which must be transformed into computer-readable lists. Each element in pfc[] corresponds to an element of the same index in expn[]. An exponent of 1 is assumed if none specified. Next, all possible integer exponents less than or equal to the exponents of the prime factorization are calculated and applied to the prime factors. For example: 360 = 2^3 * 3^2 * 5 (prime factorization) pfc = {2,3,5} expn = {3,2,1} factors: 2^3 * 3^2 * 5^1 = 360 2^2 * 3^2 * 5^1 = 60 2^1 * 3^2 * 5^1 = 90 2^0 * 3^1 * 5^1 = 15 2^3 * 3^1 * 5^1 = 120 2^2 * 3^1 * 5^1 = 60 2^1 * 3^0 * 5^1 = 10 2^0 * 3^0 * 5^1 = 5 2^3 * 3^0 * 5^1 = 40 2^3 * 3^2 * 5^0 = 72 2^2 * 3^2 * 5^0 = 36 2^1 * 3^2 * 5^0 = 18 2^0 * 3^1 * 5^0 = 3 2^3 * 3^1 * 5^0 = 24 2^2 * 3^1 * 5^0 = 12 2^1 * 3^0 * 5^0 = 2 2^0 * 3^0 * 5^0 = 1 1,2,12,24,3,18,36,72,40,5,10,60,120,15,90,60,360 The incrementation is done as if the factors were in a mixed-radius system, with each exponent able to be incremented from 0 up to the exponent in the prime factorization. This allows for all factors to be derived from the prime factorization, without duplicates. To my knowledge this method is original to me, I haven't seen it anywhere. It works quite well. Let me know, -Jeff Connelly