[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Faster algorithm for factor?
From: |
Trevor Wilson |
Subject: |
Re: Faster algorithm for factor? |
Date: |
Mon, 5 Jan 2004 16:44:09 +0000 (UTC) |
Yes, there is a bug for inputs >= 2^63 where the program does not
necessarily terminate. The program uses the Rabin-Miller primality test,
so it should return on primes almost immediately in general.
--Trevor
"Mathematics is like checkers in being suitable for the young, not too
difficult, amusing, and without peril to the state." --Plato
On Mon, 5 Jan 2004, Jim Meyering wrote:
> Trevor Wilson <address@hidden> wrote:
> > Here is the code for a factor-like program that uses Pollard's Rho
> > algorithm. It doesn't do any error-checking or anything fancy, but its
> > output is identical to that of factor, for testing purposes.
> >
> > It is slower for small inputs, so we should probably fall back to the
> > wheel method for these. However, I haven't yet found an input for which
> > it takes more than a second or so.
>
> Using GNU factor to `factor' the largest 64-bit prime
> takes 70 seconds on a 1.6 GHz Athlon:
>
> $ time ./factor 18446744073709551557
> 18446744073709551557: 18446744073709551557
>
> real 1m10.493s
> user 1m8.670s
> sys 0m0.030s
>
> However, trying to do the same thing with your program took a lot longer.
> I killed the process after it'd consumed almost 30 *minutes* of CPU time.
> Do you get better times in general?
>
>
Re: Faster algorithm for factor?, Trevor Wilson, 2004/01/05