2
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\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 '16 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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