[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Improved performance for factor.
From: |
Ralph Loader |
Subject: |
Improved performance for factor. |
Date: |
Wed, 16 May 2007 20:43:34 +1200 |
Hi,
factor in coreutils accepts 64 bit numbers, but can be very slow, e.g.,
try
factor 18446743979220271189
Attached is a patch to use the the Pollard rho factorisation algorithm.
On my ancient dog slow PC it does the above factorisation in about 1/4
seconds instead of 2 minutes.
It factors a number n in time approx O(n**(1/4)) so should be perfectly
OK on any 64 bit number. [If anyone has a 128 bit machine handy feel
free to let me play :-)].
Ralph.
factor.diff
Description: Text Data
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Improved performance for factor.,
Ralph Loader <=