From: Ruby Quiz <james@...>
Date: 2008-02-14T23:32:27+09:00
Subject: [SUMMARY] Internal Rate of Return (#156)

Solving the IRR equation is essentially a matter of computational guesswork. 
You pick an IRR and check to see if the NPV is zero, or very close to it.  When
it is, you found the right IRR.  If you didn't find the right IRR, it's time to
guess again.

How to make your guesses is the main issue with solving this problem.  Most
people used a little calculus to refine their guess.  Newton's method can be
used to solve equations like the one we have for NPV.

Alex Shulgin used a simpler guess metric that's probably a little more familiar
to us computer guys, especially if you have forgotten as much calculus as I
have.  Alex did a binary search for the answer.  This process is actually very
simple, once you find a good upper and lower bound for the search.

Let's have a look at how Alex solved the quiz.  First, we need to be able to
calculate an NPV:

	#!/usr/bin/env ruby
	
	def npv(ct, i)
	 sum = 0
	 ct.each_with_index{ |c,t| sum += c/(1 + i.to_f)**t }
	 sum
	end
	
	# ...

That's a direct code translation of the equation given in the quiz.  With it, we
can test our IRR guess to see what NPV value they return.

Now, for Alex's irr() method, let's actually start at the end of the code since
that makes it easier to understand:

	# ...
	
	def irr(ct)
	 # ... set l and r bounds in here ...
	
	 m = 0
	 loop do
	   m = (l + r)/2.0
	   v = npv(ct, m)
	
	   break if v.abs < 1e-8
	   if v*sign < 0
	     r = m
	   else
	     l = m
	   end
	 end
	 m
	end

As my comment implies, the missing piece of code sets some bounds variables:  l
for lower and r for roof, I think.  It also sets the sign variable, which give
us the sign of the rate we are solving for.

If you can take those elements on faith for now, we're looking at a simple
binary search in this code.  First we find the mid-point and check its NPV.  If
that number is really close to zero, it's our answer.  If the NPV tells us it is
too high, we drop the roof.  Otherwise, we raise the lower bound.  Rinse,
repeat.  This will converge on the IRR we seek.

Now we need to know how Alex found those bounds:

	# ...
	
	def irr(ct)
	 l = -0.9999
	 sign = npv(ct, l)
	 r = 1.0
	 while npv(ct, r)*sign > 0 do
	   r *= 2
	   break if r > 1000
	 end
	 if r > 1000
	   l = -1.0001
	   sign = npv(ct, l)
	   r = -2.0
	   while npv(ct, r)*sign > 0 do
	     r *= 2
	     return 0.0/0.0 if r.abs > 1000
	   end
	 end
	
	 # ... binary search here ...
	end

The first thing to understand here is why Alex is skirting around the -1 number
with values like -0.9999 and -1.0001.  The reason is that NPV doesn't help us
there:

	>> npv(Array.new(5) { rand(201) - 100 }, -1)
	=> NaN
	>> npv(Array.new(5) { rand(201) - 100 }, -1)
	=> -Infinity
	>> npv(Array.new(5) { rand(201) - 100 }, -1)
	=> NaN

Given that, Alex's bounds checking code starts by assuming a lower bound of
-0.9999.  The first while loop then walks the roof bound up from 1.0 to 1000
searching for a good upper bound.  If those points don't work out, the code
pivots to -1.0001 and walking the other bound from -2.0 to -1000.  If both
searches fail, we're in the area were IRR is undefined and Alex returns NaN to
indicate that.  Otherwise, we have found suitable boundaries and the code moves
on to the binary search.

Again, that's a non-mathy way to solve this problem.  Definitely browse through
the other solutions to get a feel for Newton's method based solutions as well.

Since this brings us to three full years of weekly quizzes and my retirement as
quizmaster, I want to thank not only those who solved this week's problem but
anyone who ever solved a quiz.  If people hadn't supported the effort so well
these last three years, it never would have made it this far.  I also need to
give a huge thanks to those who contributed quizzes and summaries during the
run.  They carried me a good portion of the way and I'm eternally grateful for
that.

Sincerely, thank you all.

Tomorrow, I join most of you as a quiz solver.  I'll leave it to the new team to
drop hints about their problems, but I for one am anxious to see them.