irootstest.cr

require "big"

module IntRoots
  def irootn(n : Int32)
    raise ArgumentError.new "Can't take even root of negative input" if self < 0 && n.even?
    raise ArgumentError.new "Root must be an Integer >= 2" unless n.is_a?(Int) && n > 1
    num = self.abs
    one = typeof(self).new(1)   # value 1 of type self
    root = bitn_mask = one << (num.bit_length - 1) // n
    until (bitn_mask >>= 1) == 0
      root |= bitn_mask
      root ^= bitn_mask if root**n > num
    end
    root *= (self < 0 ? -1 : 1) # ouput same Integer type as input
  end
  
  def iroot2; irootn(2) end
  
  def irootn1(n : Int32)
    raise ArgumentError.new "Can't take even root of negative input" if self < 0 && n.even?
    raise ArgumentError.new "Root must be an Integer >= 2" unless n.is_a?(Int) && n > 1
    num = self.abs
    one = typeof(self).new(1)   # value 1 of type self
    root = bitn_mask = one << (b = (num.bit_length - 1) // n)
    numb = 1 << b*n             # root**n
    until (bitn_mask >>= 1) == 0 || numb == num
      root |= bitn_mask
      root ^= bitn_mask if (numb = root**n) > num
    end
    root *= (self < 0 ? -1 : 1) # ouput same Integer type as input
  end

  def iroot2a; irootn1(2) end
  
  def nroot(k, n)
    u, s = n, n+1
    while u < s
        s = u
        t = (k-1) * s + n // s ** (k-1)
        u = t // k
    end
    s
  end

  def newton_sqrt(n = self)    # newton method with optimum initial estimate x
    raise ArgumentError.new "Input must be non-negative integer" if n < 0
    return n if n < 2
    bits = (n.bit_length - 1 & -2) - 52
    top = bits > 0 ? n >> bits : n
    r0 = Math.sqrt(top).to_big_i
    x = bits > 0 ? r0 << (bits >> 1) : r0
  
    y = (x + n // x) >> 1
    until y == x
      x = y
      y = (x + n // x) >> 1
    end
    x
  end

  def isqrt(n = self)          # newton method version used in Ruby for Integer#sqrt
    raise ArgumentError.new "Input must be non-negative integer" if n < 0
    return n if n < 2
    b = n.to_s(2).size
    #b = n.bit_length
    one = typeof(self).new(1)  # value 1 of type self
    x = one << (b - 1) // 2 | n >> ((b >> 1) + 1)
    while (t = n // x) < x; x = (x + t) >> 1 end
    x                          # ouput same Integer type as input
  end

  def isqrt1(n = self)         # newton method version used in Ruby for Integer#sqrt
    raise ArgumentError.new "Input must be non-negative integer" if n < 0
    return n if n < 2
    b = n.to_s(2).size
    #b = n.bit_length
    one = typeof(self).new(1)  # value 1 of type self
    x = one << (b - 1) // 2 + 1
    while (t = n // x) < x; x = (x + t) >> 1 end
    x                          # ouput same Integer type as input
  end
end

struct Int; include IntRoots end

def tm; t=Time.monotonic; yield; (Time.monotonic-t).total_seconds.round(9) end
puts
puts
n = 10.to_big_i ** 577
puts n, "root #{2}", root = n.iroot2, root**2, "#{tm{ n.iroot2 }} secs"
#puts "#{tm{ puts n.irootn(r) }} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using n.iroot2", root = n.iroot2, root**r, "#{tm{ n.iroot2 }} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using n.iroot2a", root = n.iroot2a, root**r, "#{tm{ n.iroot2a }} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using newton_faster", root = n.newton_sqrt, root**r, "#{tm{ n.newton_sqrt }} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using newton  isqrt", root = n.isqrt, root**r, "#{tm{ n.isqrt }} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using newton isqrt1", root = n.isqrt1, root**r, "#{tm{ n.isqrt1}} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using n.irootn", root = n.irootn(r), root**r, "#{tm{ n.irootn(r) }} secs"
puts
r = 2; puts "n = #{n}", "root #{r} using n.irootn1", root = n.irootn1(r), root**r, "#{tm{ n.irootn1(r) }} secs"
puts
#puts "#{tm{ puts n.irootn(r) }} secs"
r = 3; puts "n = #{n}", "root #{r} using n.irootn", root = n.irootn(r), root**r, "#{tm{ n.irootn(r) }} secs"
puts
r = 3; puts "n = #{n}", "root #{r} using n.irootn1", root = n.irootn1(r), root**r, "#{tm{ n.irootn1(r) }} secs"
puts
r = 4; puts "n = #{n}", "root #{r} using n.irootn", root = n.irootn(r), root**r, "#{tm{ n.irootn(r) }} secs"
puts
r = 4; puts "n = #{n}", "root #{r} using n.irootn1", root = n.irootn1(r), root**r, "#{tm{ n.irootn1(r) }} secs"
puts
r = 5; puts "n = #{-1*n}", "root #{r} using n.irootn", root = (-1*n).irootn(r), root**r, "#{tm{ (-1*n).irootn(r) }} secs"
puts
r = 5; puts "n = #{-1*n}", "root #{r} using n.irootn1", root = (-1*n).irootn1(r), root**r, "#{tm{ (-1*n).irootn1(r) }} secs"
puts
r = 6; puts "n = #{n}", "root #{r} using n.irootn", root = (n).irootn(r), root**r, "#{tm{ (n).irootn(r) }} secs"
puts
r = 6; puts "n = #{n}", "root #{r} using n.irootn1", root = n.irootn1(r), root**r, "#{tm{ n.irootn1(r) }} secs"
puts
r = 7; puts "n = #{-1*n}", "root #{r} using n.irootn", root = (-1*n).irootn(r), root**r, "#{tm{ (-1*n).irootn(r) }} secs"
puts
r = 7; puts "n = #{-1*n}", "root #{r} using n.irootn1", root = (-1*n).irootn1(r), root**r, "#{tm{ (-1*n).irootn1(r) }} secs"