Integer sqrt and nth roots

[jzakiya]

Initiated in forum: https://forum.crystal-lang.org/t/integer-sqrt-in-stdlib/1839/8

Using Math.sqrt(n).to_i provides inaccurate results once n reaches a certain large size, rendering this operation useless for numerical algorithms/processing using large numbers. Including methods for Integer sqrt, and nth roots makes Crystal much more useable for numerical applications (which Julia, et al, promote as its claim-to-fame).

require "big"

module IntRoots

  def isqrt(n = self)   # Newton's method for integer sqrt
    raise "ivalid negative integer" if n < 0
    return n if n < 2
    b = n.to_s(2).size
    one = typeof(self).new(1)  # value 1 of type self
    x = one << ((b-1) >> 1) | n >> ((b >> 1) + 1)
    while (t = n // x) < x; x = (x + t) >> 1 end
    x
  end

  def irootn(n)        # Newton's method for integer nth root
    return nil if self < 0 && n.even?
    raise "root n not an Integer >= 2" unless n.is_a?(Int) && n > 1
    return self if self == 0 || (self == -1 && n.odd?)
    num = self.abs
    one = typeof(self).new(1)  # value 1 of type self
    e, x = n-1, one << (num.to_s(2).size-1) // n + 1
    while (t = (e * x + num // x ** e) // n) < x
      x = t 
    end
    x *= self < 0 ? -1 : 1
  end
end

struct Int; include IntRoots end

There are multiple implementation details that need to be agreed upon (and documented) to present a consistent name and use API to users, but other than that, the code above provides working implementations that can be a starting point for optimization.

[HertzDevil]

Partially resolved by #10549.