# Integer square root

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."
[n]
{:pre [(not (neg? n))]}
(let [n (bigint n)]
(if (zero? n)
n
(loop [x (.shiftLeft BigInteger/ONE (quot (inc (.bitLength n)) 2))]
(let [y (quot (+ x (quot n x)) 2)]
(if (<= x y)
x
(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?
• 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. Commented Mar 3, 2016 at 0:39
• @PinCrash Are you sure? isqrt is the standard name for this function. Commented Mar 3, 2016 at 0:40
• I did not realize that, my bad. Number theory is not my strong suit. Commented Mar 3, 2016 at 0:42
• @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. Commented Mar 3, 2016 at 0:43

• 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. Commented Feb 19, 2016 at 14:38