[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Faster algorithm for factor?

From: Jim Meyering
Subject: Re: Faster algorithm for factor?
Date: Mon, 05 Jan 2004 13:28:36 +0100

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]