Square root calculation using Newton-Raphson

sroot.rb

# Square root calculation using Newton-Raphson
# from Practical Programming (1968)

a = 256

x = (1 + a) / 2.0

loop do
  ox = x
  x = (x + a.to_f / x) / 2.0
  break if x >= ox
end

puts "The square root of #{a} is #{x}"

Cf. Section 1.1.7 of Structure and Interpretation of Computer Programs, (http://dpk.org.uk/V) which shows this off in a functional style in Scheme. (It's not quite the method shown here, since it uses a routine to determine if the answer is a close-enough approximation. It's a relatively trivial exercise to adapt it to check exactness using the limit of float precision as shown here.)

Thanks! I'll have to check that out. I'm not sure why I don't remember it because I've done about a third of SICP in the past.

The technique used in this gist is not as good as it could be, but I wanted to keep it authentic to the ALGOL method outlined in that book from 1968 ;-)

Thought I'd try the SICP approach:

def improve(guess, x)
  (guess + (x / guess.to_f)) / 2.0
end

def sqrt_iter(guess, x)
  return guess if good_enough?(guess, x)
  sqrt_iter improve(guess, x), x
end

def good_enough?(guess, x)
  (guess ** 2 - x).abs < 0.001
end

def sqrt(x)
  sqrt_iter(1.0, x)
end

puts sqrt(25)

A particularly slow approach in Ruby, though. I think tail recursion optimization is turned off by default.

I don't believe Ruby performs TCO at all, even as an option. Here's a faster sqrt_iter:

def sqrt_iter guess, x
  until good_enough? guess, x
    guess = improve guess, x
  end
  return guess
end

In vm_opts.h:

#define OPT_TAILCALL_OPTIMIZATION    0

Supposedly it can also be turned on at runtime, but I didn't have any luck with it when I first noticed the option a year or two ago. Might have another try now as it may be tied up ;-)

I gave it a go. No significant performance gain, as far as I could tell. On the few runs I tried, it was a few percent.

All in the interests of science though since, of course, the iterative solution is quicker anyway ;-)

src = <<-RUBY
  def improve(guess, x)
    (guess + (x / guess.to_f)) / 2.0
  end

  def sqrt_iter(guess, x)
    return guess if good_enough?(guess, x)
    sqrt_iter improve(guess, x), x
  end

  def good_enough?(guess, x)
    (guess ** 2 - x).abs < 0.001
  end

  def sqrt(x)
    sqrt_iter(1.0, x)
  end

  y = nil
  500000.times { y = sqrt(2401) } 
  puts y
RUBY

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => false
}

puts "Tail call optimization is #{RubyVM::InstructionSequence.compile_option[:tailcall_optimization] ? "ON" : "OFF"}"
p RubyVM::InstructionSequence.compile(src, nil, nil, 1).eval