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/8/00 7:37:43 PM Mountain Daylight Time,
noveck@pluto.njcc.com writes:
> 32-_digit_ number. Do you still imagine that division of a 32-digit BCD
> number by all those primes could be done so quickly? I suppose it may not
> be that difficult. . .
Whoops, misread that one ;)
> Because trying to work with 613-digit decimal numbers (floats) in raw
binary
> would be horrendous. If you're going to limit your numbers to only a few
> bytes, raw binary may be fine (although 64 bits may be a bit much for raw
> binary floats?), but trying to take a binary number and converting it to a
> decimal number could take very, very, very, very long when the resulting
> decimal number is as long as 613 digits =)
Well, doesn't the 89/92+ have a seperate integer type that only holds
integers (duh)? Maybe I dreamed I read that somewhere or something ;)
I'm still a binary proponent, whether it be integers or floats, especially
for integers. Even when you have to convert to the decimal system for
display purposes, speed shouldn't be that much of a concern, and it would in
all cases, except for display purposes, be faster than BCD.
> > 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).
>
> So, for every prime this _is_ true, but is it not true for every number
> that's not prime (the contrapositive)? I imagine so, but I'm just checking
> =)
True, not every number with this property is prime, but every prime has this
property.
> If we're using BCD numbers, then this sounds great - after mod 30, it's
> _very_ easy to test divisibility by 2, 3, or 5 in BCD since each digit is
> kept in base 10 form. Were we to use hex numbers, division by 3 or 5 would
> be a pain - but with BCD, we can extract the last digit by itself and test
> whether it's even (check bit 0) or 5; otherwise, testing for divisibility
by
> 3 is as easy as adding the digits and checking if the resulting number is
3,
> 6, or 9. I would think that in this instance, BCD math could be faster
than
> 64-bit or larger binary numbers.
Actually, I probably could have put in a bit about implementation in my last
post ;) The idea of wheeler factorization is that you can continuously
trial-divide probable primes without actually checking the probable-primality
of those numbers. The way STL implemented this in Prime6 (as did I in
PrimeASM) was to first have a congruency list, and then keep a counter and
add each successive element in the list to the counter to get your
probable-primes. For example, if you use modulus 30, your list would be {1,
7, 11, 13, 17, 19, 23, 29}. Then you'd start by trial-dividing the inputted
number by 2, 3, and 5, and then every element in the congruency list starting
with 7. After that, initialize a counter to 30, and then trial-divide the
inputted number by the sum of the counter and each element of the list (31,
37, ..., 59). Upon trial-dividing by the last sum, 59, increase the counter
by 30 (so the new value is 60) and again trial-divide by the sum of the
counter and each element of the list, increase the counter by 30, etc. This
is obviously better than initially checking the divisibility of each
potential probable-prime to 2, 3, and 5.
>From experience in coding PrimeASM, the slowest process of this
implementation was the dividing of the number by each probable-prime, and I
think binary integers would be much faster at this than BCD floats (or even
BCD integers).
While on the implementation idea, there is another approach I've thought of.
Rather than using a congruency list, one could use a list of the differences
between each successive elements in the congruency list. For example,
instead of using the congruency list above, you could use the list {4, 2, 4,
2, 4, 6, 2, 6}. You again start by dividing by 2, 3, and 5, and then you
immediately "skip" to 7. To get to the next probable-prime, you simply add
each successive term in the difference list. So first add 4 to get 11, then
2 to get 13, then 4 to get 17, then 2 to get to 19, then 4 to get to 23, then
6 to get to 29, then 2 to get to 31, then 6 to get to 37, and then you simply
start at the front of the list again. This method might be better to the
aforementioned approach.
JayEll