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 S. 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.

As my comment implies, the missing piece of code sets some
bounds variables: l for lower and r for roof, I think.

Left and Right?

=)

On Feb 14, 2008, at 9:13 AM, Matthew M. wrote:

As my comment implies, the missing piece of code sets some
bounds variables: l for lower and r for roof, I think.

Left and Right?

Never thought of that. I bet you are right too. It makes more sense
with the way the code handles negative numbers.

James Edward G. II

On Feb 14, 9:32 am, Ruby Q. [email protected] wrote:

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.

Thank you, James, and well done! You’ve given quite a lot to the Ruby
community.

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.

Me too!

Eric

On Feb 14, 2008, at 1:20 PM, Eric I. wrote:

during the
run. They carried me a good portion of the way and I’m eternally
grateful for
that.

Sincerely, thank you all.

Thank you, James, and well done! You’ve given quite a lot to the Ruby
community.

Thanks Eric. I think your solutions have given the community at least
as much. :wink:

James Edward G. II

On Feb 14, 2008, at 2:25 PM, Bill K. wrote:

give a huge thanks to those who contributed quizzes and summaries
Thanks, James for all the quizzes !
Thanks so much Bill. I appreciate that.

James Edward G. II

From: “Ruby Q.” [email protected]

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.

Thanks, James for all the quizzes !

I only solved a few, but I followed the discussion on the rest with
interest and
enjoyment.

Hard to believe it’s been three years already. Over time, the summary
on
Thursday and new quiz on Friday was something I’d really gotten to look
forward to each week.

You did a fantastic job. Enjoyed it.

Regards,

Bill

On Feb 14, 2008, at 2:47 PM, Robert D. wrote:

Well I know I have said thanx already, cause I wanted to be the
first ;).
But I guess that you might save this one single thread to show to your
grandchildren and so I repeat my expression of gratitude for what you
have done for this community and Ruby in general.

My grandchildren, eh? Brilliant.

Thank you Robert.

James Edward G. II

Well I know I have said thanx already, cause I wanted to be the first
;).
But I guess that you might save this one single thread to show to your
grandchildren and so I repeat my expression of gratitude for what you
have done for this community and Ruby in general.

C U around
Robert

On Feb 14, 2008, at 9:32 AM, Ruby Q. wrote:

run. They carried me a good portion of the way and I’m eternally
grateful for
that.

Sincerely, thank you all.

Thank you so much.

I was a late comer to Ruby Q… My first submission was Quiz 90. And
I didn’t solve all that many quizzes after that one. Still I always
followed the submissions and read the summaries from Quiz 90 on. And
I enjoyed and learned from each. I am particularly fond of your
summaries. They were always cogent and extremely well written –
amazingly so, when one considers how little time you had to write
each one.

Now that you’re retired , James, why don’t you use some newly
available free time to get out a second “Best of Ruby
Quiz” book ? Either an updated second edition, or a separate
second volume. I’d would really like to see this happen. They were
certainly enough great quizzes after the book came out to fill
another volume.

Regards, Morton

On Feb 14, 2008, at 9:17 PM, Morton G. wrote:

give a huge thanks to those who contributed quizzes and summaries
And I didn’t solve all that many quizzes after that one. Still I
always followed the submissions and read the summaries from Quiz 90
on. And I enjoyed and learned from each. I am particularly fond of
your summaries. They were always cogent and extremely well written
– amazingly so, when one considers how little time you had to write
each one.

Thanks for the high praise Morton.

Now that you’re retired , James, why don’t you use some newly
available free time to get out a second “Best of Ruby
Quiz” book ? Either an updated second edition, or a
separate second volume. I’d would really like to see this happen.
They were certainly enough great quizzes after the book came out to
fill another volume.

I may very well do that at some point. I would like to and I agree
with you about there being a lot of good material for it now.

However, for just a little while first, I would like to have a little
more time for programming… :wink:

James Edward G. II

On Feb 14, 4:32 pm, Ruby Q. [email protected] wrote:

[snip my solution]

Uh, I’m surprised to see that elaborate explanation of such a dumb
code of mine. Sorry, if that had taken you a lot of time–it was
really my job to explain it at least in a few words, but I’m too
lazy. :slight_smile:

Sincerely, thank you all.

Thank you! I’ve joined the quiz very late, but found it very exciting
and watched every single problem since when. Solving little quizzies
in such a nice language like Ruby is really refreshing after hours of
routine job at work. :slight_smile:

On Feb 15, 2008, at 3:04 AM, Alex S. wrote:

On Feb 14, 4:32 pm, Ruby Q. [email protected] wrote:

[snip my solution]

Uh, I’m surprised to see that elaborate explanation of such a dumb
code of mine.

I personally found it to be pretty clever. I couldn’t think of a way
to solve that problem without using the math, so it was neat to have
you show it too me.

Sincerely, thank you all.

Thank you! I’ve joined the quiz very late, but found it very exciting
and watched every single problem since when. Solving little quizzies
in such a nice language like Ruby is really refreshing after hours of
routine job at work. :slight_smile:

Thanks Alex.

James Edward G. II

On Feb 16, 2008, at 7:26 PM, Carl P. wrote:

I’d like to mention my appreciation for all the hard work you’ve put
into Ruby Q… It has certainly proven to be a valuable resource for
learning Ruby. And it has brightened my day when my solution has been
featured in your weekly summary.

Thanks for giving me those great solutions to talk about Carl.

James Edward G. II

Hey James,

I’d like to mention my appreciation for all the hard work you’ve put
into Ruby Q… It has certainly proven to be a valuable resource for
learning Ruby. And it has brightened my day when my solution has been
featured in your weekly summary.

The quizmasters following you have very big shoes to fill.

Thanks again,
Carl