Compute integer cubic root via Newton-Raphson

gistfile1.rb

class Integer
  #Newton-Raphson: cubic root of n is equivalent to finding x in x**3 - n = 0
  #=> x_(k+1) = x_k - f(x_k) / f'(x_k)
  #=> x_(k+1) = x_k - (x_k**3 - n) / (3 * x_k**2)
  #=> x_(k+1) = (2*x_k**3 + n) / (3*x_k**2)
  #=> x_(k+1) = 2*x_k/3 + n/(3*x_k**2)
  #returns an integer cubic root and a boolean indicating whether the root is exact 
  def icbrt
    iter = lambda { |x, n| 2 * x / 3 + n / (3 * x * x) }
    x = self
    x1 = iter.call(n, self)
    x1, x = iter.call(x1, self), x1 until (x1 - x).abs <= 1 # stopping criterion
    x1 = x1 - 1 while (tmp = x1*x1*x1) > self  
    return x1, tmp == self
  end
end