Re: TI-M: Re: TI-Math Digest V1 #22


[Prev][Next][Index][Thread]

Re: TI-M: Re: TI-Math Digest V1 #22




In a message dated 6/7/00 10:02:40 PM Mountain Daylight Time, 
noveck@pluto.njcc.com writes:

>  Do you happen to know of a page with the Wheeler factorization algorithm
>  explained?  I suppose Knuth's fast algorithm won't work because it only
>  determines whether a number is prime to a high degree probability and is 
not
>  certain, correct?

Well, no, I don't know of a link to somewhere where it's explained, only 
mentioned.  However, I think I might be able to do an adequate enough job of 
explaining how it works below (I was thinking about it today while mowing the 
lawn, passes the time by a bit quicker ;)  Also, to reiterate, STL's 
documentation of Prime6 offers a good source.

>  Call it a hunch, but I'd imagine trial dividing a 32-digit number by all
>  primes up through 283 would take more than half  a second - especially with
>  BCD numbers.  There must be some other algorithm in there helping to speed
>  it up, especially since this is finding whether all these numbers are 
primes
>  as it goes???

Actually, there should be no noticeable delay when dividing a 32-bit number 
by even every single number from 2 to 283; it would take even less time by 
dividing by only primes or probable-primes.  Even with the extra time it 
takes to calculate through BCD, I'm guessing the M68K processor more than 
makes up for that fact.  PrimeASM for the 85/86 does 64-bit math, and it 
takes almost no time to trial-divide through the first 50 to 100 
probable-primes.

I'm not sure what algorithm is implemented on the 89/92+, but with Wheeler 
Factorization, I know that *most* of the numbers tried are in fact primes, 
especially in the beginning.

>  Somehow I don't think you could do it too much better, since we need to use
>  a 613 digit decimal number and I don't believe that IEEE decimals will cut
>  it (they don't guarantee full accuracy, correct?) so BCD seems like the way
>  to go.  Of course, the number of digits should decrease rapidly as soon as
>  we cut out all those factors of 2, 3, etc. . .

Raw binary (as opposed to BCD) seems to work decently on the Z80 in my 
implementation (and that's not even done too well...), so why wouldn't it 
work on an M68K?  In my opinion, raw binary would be the way to go, 
especially with integers and especially on the M68K...


Wheeler Factorization is based on, more or less, the congruency/incongruency 
of primes to other numbers.  For example, as STL has pointed out in his 
Prime6 documentation, many factoring programs use a very simple 
implementation of Wheeler Factorization based on the fact that for every 
prime, p, p = 1 (mod 2), with the exception of 2.  All this says is that 
every prime other than 2 is one more than a multiple of 2, or an odd number.  
Nothing new (I should hope).  But Wheeler Factorization can be extended to 
say that for every prime, p, p = 1 (mod 2*3) *or* p = 5 (mod 2*3).  Take any 
prime, say, 79: 79 = 1 (mod 6); 41 = 5 (mod 6).  This "property" of primes 
makes sense if you look at what a prime is *not* congruent to.  A prime 
cannot be congruent to neither 2 (mod 6) nor 4 (mod 6) because then 2 would 
be a factor.  Likewise a prime cannot be congruent to 3 (mod 6) because then 
3 would be a factor.  And of course a prime cannot be congruent to 0 (mod 6), 
so this only leaves 1 and 5.  Similarly, for every prime p, p = 1 (mod 
2*3*5), p = 7 (mod 30), p = 11 (mod 30), p = 13 (mod 30), p = 17 (mod 30), p 
= 19 (mod 30), p = 23 (mod 30), or p = 29 (mod 30).  Any number that is 
congruent to 0, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 
25, 26, 27, or 28 (mod 30) (in other words, any number that is divisible by 
2, 3, and/or 5, mod 30) must be composite.  This property can be extended to 
modulus 210 ( = 2*3*5*7) and even 2310 ( = 2*3*5*7*11); beyond that, i know a 
Z80 wouldn't be able to handle it, and it would probably be 
counter-productive on the M68K to go beyond modulus 2310.  I suppose I should 
put in that when creating a "congruency list" for prime numbers (such as the 
1, 7, 11, 13, ..., 29 list above), don't create the list based on primality, 
but rather whether the number is divisible by 2, 3, and/or 5 (with modulus 
30); 2, 3, 5, and/or 7 (with modulus 210); or 2, 3, 5, 7, and/or 11 (with 
modulus 2310).

I think that's about all you'd need to know; probably went overboard there on 
the explanation... ;)

JayEll