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 <[EMAIL PROTECTED]> 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? > > _______________________________________________ Bug-coreutils mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/bug-coreutils
