## [Maxima-bugs] [ maxima-Bugs-852413 ] factor(2^31-i) extremely slow/FIX

 [Maxima-bugs] [ maxima-Bugs-852413 ] factor(2^31-i) extremely slow/FIX From: SourceForge.net - 2006-04-18 23:48:30 ```Bugs item #852413, was opened at 2003-12-02 07:33 Message generated for change (Comment added) made by andrejv You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None >Status: Closed Resolution: None Priority: 5 Submitted By: Stavros Macrakis (macrakis) Assigned to: Nobody/Anonymous (nobody) Summary: factor(2^31-i) extremely slow/FIX Initial Comment: 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 ---------------------------------------------------------------------- >Comment By: Andrej Vodopivec (andrejv) Date: 2006-04-19 01:48 Message: Logged In: YES user_id=1179910 This code is not present in current CVS sources. andrej ---------------------------------------------------------------------- Comment By: Stavros Macrakis (macrakis) Date: 2003-12-07 00:37 Message: 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? ---------------------------------------------------------------------- Comment By: Raymond Toy (rtoy) Date: 2003-12-06 22:36 Message: 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. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 ```

 [Maxima-bugs] [ maxima-Bugs-852413 ] factor(2^31-i) extremely slow/FIX From: SourceForge.net - 2003-12-02 06:33:34 ```Bugs item #852413, was opened at 2003-12-02 01:33 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Stavros Macrakis (macrakis) Assigned to: Nobody/Anonymous (nobody) Summary: factor(2^31-i) extremely slow/FIX Initial Comment: 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 ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 ```
 [Maxima-bugs] [ maxima-Bugs-852413 ] factor(2^31-i) extremely slow/FIX From: SourceForge.net - 2003-12-06 21:36:12 ```Bugs item #852413, was opened at 2003-12-02 01:33 Message generated for change (Comment added) made by rtoy You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Stavros Macrakis (macrakis) Assigned to: Nobody/Anonymous (nobody) Summary: factor(2^31-i) extremely slow/FIX Initial Comment: 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 ---------------------------------------------------------------------- >Comment By: Raymond Toy (rtoy) Date: 2003-12-06 16:36 Message: 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. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 ```
 [Maxima-bugs] [ maxima-Bugs-852413 ] factor(2^31-i) extremely slow/FIX From: SourceForge.net - 2003-12-06 23:37:26 ```Bugs item #852413, was opened at 2003-12-02 01:33 Message generated for change (Comment added) made by macrakis You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 Category: None Group: None Status: Open Resolution: None Priority: 5 Submitted By: Stavros Macrakis (macrakis) Assigned to: Nobody/Anonymous (nobody) Summary: factor(2^31-i) extremely slow/FIX Initial Comment: 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 ---------------------------------------------------------------------- >Comment By: Stavros Macrakis (macrakis) Date: 2003-12-06 18:37 Message: 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? ---------------------------------------------------------------------- Comment By: Raymond Toy (rtoy) Date: 2003-12-06 16:36 Message: 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. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 ```
 [Maxima-bugs] [ maxima-Bugs-852413 ] factor(2^31-i) extremely slow/FIX From: SourceForge.net - 2006-04-18 23:48:30 ```Bugs item #852413, was opened at 2003-12-02 07:33 Message generated for change (Comment added) made by andrejv You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None >Status: Closed Resolution: None Priority: 5 Submitted By: Stavros Macrakis (macrakis) Assigned to: Nobody/Anonymous (nobody) Summary: factor(2^31-i) extremely slow/FIX Initial Comment: 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 ---------------------------------------------------------------------- >Comment By: Andrej Vodopivec (andrejv) Date: 2006-04-19 01:48 Message: Logged In: YES user_id=1179910 This code is not present in current CVS sources. andrej ---------------------------------------------------------------------- Comment By: Stavros Macrakis (macrakis) Date: 2003-12-07 00:37 Message: 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? ---------------------------------------------------------------------- Comment By: Raymond Toy (rtoy) Date: 2003-12-06 22:36 Message: 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. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=104933&aid=852413&group_id=4933 ```