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