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/10/00 5:48:20 PM Mountain Daylight Time, 
noveck@pluto.njcc.com writes:

>  Yeah, IEEE is binary floats.  I've never seen how those work; I just know
>  they're not necessarily precise.

I'm not sure on the specs specifically, but I would think binary floats would 
be just as precise as BCD as long as approximately equal significant digits 
are kept...

>  I'm thinking keep a small list for quick factorization of small numbers, 
and
>  use wheeler if you need to find larger factors.  I think that would provide
>  a great speed boost overall without compromising size too much.

Keeping a small list of the few first primes wouldn't speed up the 
factorization up all that much as compared to wheeler, or at least I 
shouldn't think it would (certainly not a great speed boost ;).  For example, 
a congruency list with modulus 210 would consist of 48 probable primes, 
excluding the initial trial-divisions of 2, 3, 5, and 7.  Of those 48 
probable primes, only 5 are composite.  A congruency list with modulus 2310 
consists of 485 (I think) probable-primes; I'm not sure how many of those are 
composite, I might look into that just for curiosity's sake.  Anyway, to 
really make the prime list worth it, it would probably have to be relatively 
large.  With the 89's memory, though, it really shouldn't be any problem to 
store a list of primes up through 10 000 or more.  In fact, if memory is any 
kind of concern, you can simply store the differences between each successive 
prime; each difference would only take a byte, so 10K would hold over 10 000 
primes.  That should cover primes up to maybe 50 000, which would cover 
primality-proving through to 2 500 000 000 ;)

>  Then, if you're trying to find factors larger than 2310, it's as simple as
>  taking the number mod 2130 and doing a binary search through the primality
>  list to see if that number's in there.  If so, then we start testing all 
the
>  probable primes up to sqrt(num). . .

Actually, that's a bit too much work for determining the number isn't 
divisible by 2, 3, 5, or 7, since the only numbers in a congruency list of 
mod 2310 are those that aren't divisible by 2, 3, 5, or 7...

>  ugg, this lines up horribly!  You don't use arial for email, do you?  Use a
>  monospaced font!

Will do next time ;)

>  > 17439280249 (=55511*314159)  5 min 5 sec    4 min 13 sec  1 min 28 sec
>  
>  My TI-89, Hardware Version 2.00, AMS 2.03:    2.78 seconds    =)

Give TI *some* credit, then ;)

>  It looks like finding the first factor is only a few minutes shorter than
>  finding them both

Well, after finding one factor and dividing, you only have to trial-divide up 
to the square root of the result, instead of the square root of the original 
number.  So, in the case of 9 876 511 069 135 577, as soon as 9 876 511 was 
found and divided into the original number, 1 000 000 007 was left, and its 
square root was already passed, so the other factor was immediately known as 
well.

>  LOL, my 89 does it all in 34.19 seconds =)

Damn m68k...

>  No, it doesn't display any of the factors till it's done.  It picked up 601
>  but kept trying for a long time to find more.

Oh, well then that 3 min isn't so surprising...maybe remarkable, though ;)

>  Got any binary multiplication/division algorithms?

Sure, these are fairly well-known algorithms:

(C++ - style pseudocode ;)

int Divide(int Dividend, int Divisor)
{
    int Remainder = 0;
    int x;
    for(x = 0; x < [number of bits in Dividend]; x++)
    {
        Remainder = Remainder<<1 + Dividend>>[number of bits in Dividend 
minus 1];
        Dividend <<= 1;
        if(Remainder >= Divisor){
            Remainder -= Divisor;
            Dividend++;}
    }
    ret(Dividend);
}

That's it to the division algorithm.  Iterate as many times as there are bits 
in the Dividend to push out.  In each iteration, shift out the left-most bit 
(most significant bit) and shift that into the Remainder.  Then if the 
Remainder is greater than or equal to the Divisor, update the Remainder by 
subtracting the Divisor and then set right-most bit (least significant bit) 
in the Dividend, which becomes the Quotient.  This algorithm is basically 
just the binary version of long division.

int Multiply(int Multiplicand, int Multiplier)
{
    int Product = 0;
    int x;
    for(x = 0; x < [number of bits in Multiplicand]; x++)
    {
        Product <<= 1;
        if(Multiplicand>>[number of bits in Multiplicand minus 1])
            Product += Multiplier;
        Multiplicand <<= 1;
    }
    ret(Product);
}

Multiplication is pretty straitfoward as well.  In each iteration, shift the 
running Product as well as the Multiplicand.  If the bit shifted out of the 
Multiplicand was set, add the Multiplier to the running Product.

I hope these are right, someone correct me if I screwed up somewhere ;)

>  No, it catches much larger than that.  It nails 131074 instanly as 2*65537.

Perhaps what I should've said was "doesn't the factor function only 
trial-divide up to 65535?"  Even though it catches 65537 as a factor of 
131074, it does so because the other factor is smaller than 65535 (*maybe*).  
What I'm asking is can the factor function, say, factor 65537^2 correctly?

Never mind, i guess it would have to in order to find the factors of 9 876 
511 069 135 577...

>  My only guess is that there's another algorithm, or some of that 2 megs of
>  Flash ROM is devoted to a prime list and wheeler is used afterwards. . .

I doubt the ROM would use a prime list to start out with and then wheeler, 
but you'd never know...

JayEll