Enhancement to speed of ISQRT
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
SBCL |
Fix Released
|
Low
|
Unassigned |
Bug Description
1. Describe what you do, what happens, and what you expected
=======
a. Compute ISQRT for small and large integers (between 0 and 10e7.
b. ISQRT successfully computes it. See these benchmarks.
http://
http://
c. ISQRT should compute it even faster!
2. A complete repeatable test-case
=======
A faster version provided here (also attached):
https:/
The benchmark used was [modulo the value in DOTIMES and argument to ITEST:
(declaim (optimize (speed 3) (debug 0) (safety 0)))
(defparameter dum-dum-pop 0)
(defun itest (n ts &aux m1 m2)
(progn
(print 'isqrt) (terpri)
(time (dotimes (i ts)
(setq m1 (isqrt n))))
(print 'my-isqrt) (terpri)
(time (dotimes (i ts)
(setq m2 (isqrt-fast n))))
(print (list (integer-length m1) (integer-length m2)))))
(dotimes (i 3)
(setf dum-dum-pop (+ 7 (expt 11 (expt 10 i))))
(format t "======
(format t "x = 7 + 11^(10^~D); computed 10000000 times" i)
(itest dum-dum-pop 1000000)
(format t "~%====
3. SBCL version as reported by "sbcl --version"
=======
SBCL 1.0.44
(Installed from source.)
4. Output from uname -a
=======
Linux TheAmbiguousCase 2.6.35-25-generic #44-Ubuntu SMP Fri Jan 21 17:40:44 UTC 2011 x86_64 GNU/Linux
5. *FEATURES*.
==============
(:QUICKLISP :SB-BSD-
:SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS :SB-UNICODE :SB-EVAL
:SB-SOURCE-
:SB-THREAD :LARGEFILE :GENCGC :STACK-
:C-STACK-
:UNWIND-
:STACK-
:STACK-
:ALIEN-CALLBACKS :CYCLE-COUNTER :COMPLEX-FLOAT-VOPS :FLOAT-EQL-VOPS
:INLINE-CONSTANTS :MEMORY-
:OS-PROVIDES-
:OS-PROVIDES-
description: | updated |
description: | updated |
description: | updated |
tags: |
added: review removed: enhancement integers numerics speed |
Changed in sbcl: | |
assignee: | nobody → Nikodemus Siivola (nikodemus) |
Changed in sbcl: | |
importance: | Undecided → Low |
status: | New → Triaged |
Changed in sbcl: | |
status: | Fix Committed → Fix Released |
In 1.0.47.6.