# 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. – Phrancis Mar 3 '16 at 0:39
• @PinCrash Are you sure? isqrt is the standard name for this function. – Sam Estep Mar 3 '16 at 0:40
• I did not realize that, my bad. Number theory is not my strong suit. – Phrancis Mar 3 '16 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. – Sam Estep Mar 3 '16 at 0:43

• 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.

• 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. – Sam Estep Feb 19 '16 at 14:38