Re: Faster algorithm for factor?

[Jim Meyering]

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?