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