Integer square root

Question

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?

• Phrancis: 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.
• Sam Estep: @PinCrash Are you sure? isqrt is the standard name for this function.
• Phrancis: I did not realize that, my bad. Number theory is not my strong suit.
• Sam Estep: @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.

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.

• Sam Estep: 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.