#458 factor(2^31-i) extremely slow/FIX

closed
nobody
None
5
2006-04-18
2003-12-02
No

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 &gt; 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:

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 ((&gt; 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&gt; divisor maxdivisor)
(return (cond ((f&gt; x 1) (list* x 1 ans))
(t ans)))))
(go sett)))

With the new code, all numbers &lt; 2^31 factor fast. In
fact, we can factor all 2^31-1000 &lt; i &lt; 2^31-1 in 4.2
seconds.

Maxima 5.9.0 gcl 2.5.0 W2k

Discussion

• Stavros Macrakis - 2003-12-02

Revised code

• Raymond Toy - 2003-12-06

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.

• Stavros Macrakis - 2003-12-06

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?

• Andrej Vodopivec - 2006-04-18
• status: open --> closed

• Andrej Vodopivec - 2006-04-18

Logged In: YES
user_id=1179910

This code is not present in current CVS sources.

andrej