Revised code
Number to factor Time
2^31-1 44 secs
2^31-19 20 secs
2^31-61 3.6 secs
2^31-325 3.3 secs
These are absurd numbers, considering how much time it
takes for other primes near 2^31:
2^31-2275 0.1 secs (dominated by overhead)
2^31-21757 0.2 secs
Surprisingly, numbers > 2^31 (bignums) are also fast:
2^31+11 0.1 secs
It turns out that there is a bug in fixnum-cfactor, which
can be seen by running it interpreted:
load("rat3d.lisp")$
factor(2^31-61);
Error: 2147673649 is not of type FIXNUM.
The problem is that (f* divisor divisor) can be greater
than max-fixnum. The solution is simple -- calculate the
maximum divisor using isqrt whenever the factorand is
changed. This also has the benefit of making the
calculation a little faster for all integers.
(defmfun fixnum-cfactor (x)
(declare (fixnum x))
(prog ((divisor 2) ; current trial divisor
(tt 0) ; exponent of divisor
(k 2) ; increment of divisor
(ans nil) ; result list
(maxdivisor 0) ; max divisor to try
(intfaclim
(if (and $intfaclim (typep $intfaclim 'fixnum))
$intfaclim
most-positive-fixnum)))
(declare (fixnum divisor tt k maxdivisor intfaclim))
(setq maxdivisor (min (isqrt x) intfaclim))
sett (setq tt 0)
loop (cond ((f= 0 (fixnum-remainder x divisor))
(setq tt (f+ 1 tt))
(setq x (the fixnum (quot x divisor)))
(go loop)))
(cond ((> tt 0)
(setq ans (cons divisor (cons tt ans))
maxdivisor (min (the fixnum (isqrt x))
intfaclim))))
(cond ((f= divisor 2) (setq divisor 3))
((f= divisor 3) (setq divisor 5))
(t (setq divisor (f+ divisor k))
(cond ((f= k 2) (setq k 4)) (t (setq k
2)))))
(cond ((f> divisor maxdivisor)
(return (cond ((f> x 1) (list* x 1 ans))
(t ans)))))
(go sett)))
With the new code, all numbers < 2^31 factor fast. In
fact, we can factor all 2^31-1000 < i < 2^31-1 in 4.2
seconds.
Maxima 5.9.0 gcl 2.5.0 W2k
Revised code
Logged In: YES
user_id=28849
Hmm, I don't see this slowdown with CMUCL with CVS maxima.
All of the examples take 0.05 sec or less on a fairly slow
450 MHz sparc.
Logged In: YES
user_id=588346
Ray, perhaps cmucl doesn't obey the fixnum declare in fixnum-
cfactor, and is doing everything in general arithmetic?
Logged In: YES
user_id=1179910
This code is not present in current CVS sources.
andrej
Log in to post a comment.