Re: TI-M: Algebra

To: ti-math@lists.ticalc.org
Subject: Re: TI-M: Algebra
From: JayEll64@aol.com
Date: Tue, 6 Jun 2000 19:54:21 EDT
Reply-To: ti-math@lists.ticalc.org

In a message dated 6/6/00 5:15:13 PM Mountain Daylight Time, 
noveck@pluto.njcc.com writes:

> The key to the 89's symbolic capabilities appears to be its amazing ability
>  to find the prime factorization of massive numbers in an amazingly short
>  amount of time.  For example, find 299! - the longest factorial the calc
>  will calculate out fully in exact mode - and try factor([all 613 digits
>  here]).  In under 20 seconds, it has the correct answer of
>      2^294*3^147*5^72*11^29*...*269*271*277*281*283*293
>  Keep in mind that this is not "factor(299!)" (for which I wish it was smart
>  enough to not calculate the whole factorial out), but "299! \
>  factor(ans(1))" - similarly, it can get you the prime factors of the
>  32-digit number that factors out to 283^8*293^5 _instantaneously_.  If
>  someone here could point me towards some algorithms that can do _that_, I
>  would appreciate it, since I myself have no idea how you could find the
>  prime factorization of a number like that in the blink of an eye.  If you
>  can do that, division is simply putting one number over the other and
>  cancelling out common prime factors (very quick if you sort them in
>  ascending order).  Addition and subtraction are simple, as is
>  multiplication; the rest follows easily after you get a good decimal
>  division routine.

I know Wheeler factorization is a good algorithm for proving/disproving 
primality of numbers by doing a sort of "enhanced" trial-divide.  It's based 
on the fact that, for example, all primes greater than 2*3*5 = 30 are 
congruent to 1, 7, 11, 13, 17, 19, 23, and 29, modulus 30 (I'd have to look 
that up to confirm that, but I think that list is right).  For example, 79 = 
19 (mod 30), and 293 = 23 (mod 30).  I'd suggest downloading STL's Prime6 
program from the 85/BASIC section at ticalc, and you also might wanna look at 
PrimeASM (which I wrote based off of STL's program) at 85/asm/Usgard/math and 
86/asm/math at ticalc.  It uses some fairly fast (not the fastest, probably) 
assembly (Z80) 64-bit integer math routines.

Factoring the "expanded" form of 283^8 * 293^5 would expectedly be very 
quick; it doesn't take long (expecially with Wheeler factorization) to 
trial-divide up to 283, and after that all the factors just "fall into 
place".  Likewise, I wouldn't expect the expanded form of 299! to take at all 
long to completely factor, as it has prime factors immediately at 2, and it's 
biggest prime factor is less than 299.  It's almost a shame that it takes the 
89 20 seconds to simply divide one number continuously by a few hundred 
numbers (although the original number is quite long); it's that BCD crap, I 
suspect...

JayEll