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
letbinding? - Should the initial guess be more explicit about the calculation it is performing by using
Math.ceilandBigInteger.powinstead ofinc/quotandBigInteger.shiftLeft?
isqrtis not a good name for your function (at first I thought it readissqrtand thought, "that must be a predicate"). Perhaps consider renaming toint-sqrtor something like that. – Phrancis Mar 3 at 0:39isqrtis the standard name for this function. – Sam Estep Mar 3 at 0:40math.numeric-towerdoes, anyway. – Sam Estep Mar 3 at 0:43