Enhancement to speed of ISQRT

Bug #713343 reported by Robert Smith on 2011-02-04
This bug affects 1 person
Affects Status Importance Assigned to Milestone

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.
c. ISQRT should compute it even faster!

2. A complete repeatable test-case
A faster version provided here (also attached):


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)
        (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


Robert Smith (quadricode) wrote :
description: updated
tags: added: integers numerics optimization speed
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
Nikodemus Siivola (nikodemus) wrote :


Changed in sbcl:
assignee: Nikodemus Siivola (nikodemus) → nobody
status: Triaged → Fix Committed
Stas Boukarev (stassats) on 2011-05-09
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers