bug-coreutils
[Top][All Lists]
Advanced

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





reply via email to

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