Sometimes you have to improvise. If you have never heard of newton's method, binary search should probably come to mind next. It should be O(log N) which is a b

Sometimes you have to improvise. If you have never heard of newton's method, binary search should probably come to mind next. It should be O(log N) which is a bit worse than constant-complexity square root but not too bad. DELTA = 0.0000001 def sqrt_bin_search(squared_value, lower, higher) middle = (lower + higher) / 2.0 if ((middle * middle) - squared_value).abs < DELTA middle elsif middle * middle > squared_value sqrt_bin_search(squared_value, lower, middle) else sqrt_bin_search(squared_value, middle, higher) end end def sqrt(x) sqrt_bin_search(x, 0, x) end