[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?
Re: Faster algorithm for factor?, Trevor Wilson, 2004/01/05