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 07:22:20 +0000 (UTC)

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.

--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:

> > Are there any plans to implement faster algorithms in factor? For 64-bit
> > integers Pollard's rho method would be a good choice. I have an
> > implementation that is hundreds of times faster than factor for
> > large inputs. Is anyone interested in this?
> 
> Sounds interesting to me.
> 
> 

Attachment: rho.c
Description: Text document


reply via email to

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