This essentially performs the same function as exact-integer-sqrt in math.numeric-tower.

(defn isqrt
  "Returns the greatest integer less than or equal to the principal square root
  of n."
  {:pre [(not (neg? n))]}
  (let [n (bigint n)]
    (if (zero? n)
      (loop [x (.shiftLeft BigInteger/ONE (quot (inc (.bitLength n)) 2))]
        (let [y (quot (+ x (quot n x)) 2)]
          (if (<= x y)
            (recur y)))))))

I'm interested in any improvements to this code. Some specific questions:

  • Should the precondition be thrown explicitly as an IllegalArgumentException?
  • Is it a bad idea to shadow the parameter with a let binding?
  • Should the initial guess be more explicit about the calculation it is performing by using Math.ceil and BigInteger.pow instead of inc/quot and BigInteger.shiftLeft?
  • \$\begingroup\$ A small comment, I think isqrt is not a good name for your function (at first I thought it read issqrt and thought, "that must be a predicate"). Perhaps consider renaming to int-sqrt or something like that. \$\endgroup\$
    – Phrancis
    Mar 3, 2016 at 0:39
  • \$\begingroup\$ @PinCrash Are you sure? isqrt is the standard name for this function. \$\endgroup\$
    – Sam Estep
    Mar 3, 2016 at 0:40
  • \$\begingroup\$ I did not realize that, my bad. Number theory is not my strong suit. \$\endgroup\$
    – Phrancis
    Mar 3, 2016 at 0:42
  • \$\begingroup\$ @PinCrash No problem; I appreciate the feedback regardless. It may very well be better to use a longer name in this case; math.numeric-tower does, anyway. \$\endgroup\$
    – Sam Estep
    Mar 3, 2016 at 0:43

1 Answer 1


Regarding your questions:

  • No, unless you really want to have a specific type of exception thrown (to be able to catch and analyse it later). It's a programmer error to call this function with negative values, so this solution is fine.
  • No, unless you really really care about it. However, the fact that the function returns a bignum all the time should be documented and is also a cause for concern IMO, since conversion to bignums isn't free.
  • Yes, please, for exactly those reasons. Do you incur a performance penalty with those functions? Otherwise there's little reason not to use them.

Otherwise looks very good I'd say.

  • \$\begingroup\$ About the performance: on my machine, (time (run! isqrt (repeatedly 1000000 #(Math/pow 2 (rand Long/SIZE))))) takes 2300 milliseconds with the solution in the question, 2800 milliseconds using Math.ceil and BigInteger.pow. \$\endgroup\$
    – Sam Estep
    Feb 19, 2016 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.