by Harrison Reiser
Internal Rate of Return (IRR – http://en.wikipedia.org/wiki/Internal_rate_of_return) is a common financial metric, used by investment firms to predict the profitability of a company or project. Finding the IRR of a company amounts to solving for it in the equation for Net Present Value (NPV – http://en.wikipedia.org/wiki/Net_present_value), another valuable decision-making metric:
N C_t
NPV = Σ ------------
t=0 (1 + IRR)**t
This week's quiz is to calculate the IRR for any given variable-length list of numbers, which represent yearly cash flows, the C_t's in the formula above: C_0, C_1, etc. (C_0 is typically a negative value, corresponding to the initial investment into the project.) From the example in the Wikipedia article (http://en.wikipedia.org/wiki/Internal_rate_of_return), for instance, you should be able to produce a rate of 17.09% (to four decimal places, let's say) from this or a similar command:
=> 0.1709...
Keep in mind that an IRR greater than 100% is possible. Extra credit if you can also correctly handle input that produces negative rates, disregarding the fact that they make no sense.
Quiz Summary
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:
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:
=> 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.
