[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.


"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?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]