The world of finance is rife with mathematical formulas. We are all familiar with the elementary ones like those for compound interest or tallying up the value of a savings account if we add a certain amount each month over a period of time. These kinds of formulas are fairly simple and, in general, they can be handled with nothing more than a calculator. Loan amortizations and their inverse, sinking funds, are a little more difficult, but even these types of financial problems succumb to either a calculator or a simple computer program.

In this article I would like to consider a more difficult problem, usually referred to as finding the internal rate of return (IRR). Stated simply, if we make a number of expenditures at different times and receive a number of payments, also at different times, what is the effective interest rate? Because the times are not constrained to regular intervals, the simple formulas referred to above are inadequate. In fact, amortizations, such as car and home loans, are a special case of IRR where the payments and time intervals are both constant. For example, a standard four-year car loan with fixed monthly payments is really an IRR problem where you receive one lump sum at time zero (the loan value) and pay it back in 48 installments. These installments happen to be equal and happen to occur at equal time intervals, namely monthly.

We will first develop the equation for the IRR, then solve it with three equivalent programs in Perl, C and Java. This way you can compare the same algorithm in three different languages. I have found this an interesting and efficient way to learn computer languages. As an added treat we will handle both the discrete and continuous compounding cases in each program. When we are done, you will have a very general program (three programs, actually) which can handle almost any financial interest rate problem.

The trick to working with money problems is to understand a concept called “the time value of money”. If someone agrees to give you $100 a year from now, that promise is, for financial purposes, worth less than $100. And, if the $100 is promised two years hence, it is worth even less. Conversely, if you agree to give someone $100 a year from now, you can start with less than that now and let your money earn a year's interest before parting with it. People are willing to pay a premium to be able to have things sooner rather than later, and this idea leads to the concept of interest and the time value of money.

Let us consider, for the moment, only discrete compounding, and let us further restrict the discussion to annual compounding, at say eight percent. Our $100 invested for one year increases to $108. Leave it invested for another year and we have $116.64. So, we can see that the general formula for determining the value V of D dollars invested at interest rate i percent for t years is

V = D * (1 + i / 100) t

or, in our case,

V = 100 * (1.08) t

In general, we multiply by (1 + i / 100) t to find values in the future and divide by the same factor to find past values. And this explains why and how the state lotteries can give you the choice of taking your winnings as either a series of checks at future time intervals or as one lump sum now. The lump sum results from reducing each of those checks by the above factor (calculated separately for each time interval) and summing the resulting amounts. The lump sum is, of course, always smaller than the total of all those checks, and that is the amount you sacrifice to have the money now rather than later. We will come back to lotteries later after we develop our programs.

We are now in a position to state the rule that governs financial transactions that take place over a period of time: the sum of all the transactions, corrected to the same (any) time using the IRR must total zero. If you think about this for a minute it makes perfectly good sense because, if the interest rate was zero, all of the correction factors would be one and this rule would state no more than the simple fact that expenditures must equal income. Interest compounds (no pun intended) the problem by introducing those pesky correction factors to account for the increase of money with time.

First, the transaction values have to be signed, with inflows typically positive and outflows negative (although reversing the signs consistently will not affect the resulting IRR). Let us take an easy example. You deposit $100 in the bank, withdrawing $40 one year later and $70 after two years. Correcting all transactions to the present, the IRR is the value of i that satisfies the equation:

-100 + 40 / (1 + i / 100) + 70 /
        ((1 + i / 100) 2) = 0

I will leave it to the reader to solve this one with the hint to define x = (1 + i / 100) and solve for x first, then i. Congratulations, if you got i = 6.02%. You probably solved a quadratic equation, and if so, you may have noticed the reason for the quadratic—three different transactions: now and one and two years hence. These kinds of problems get increasingly hard as the number of time periods increase and that provides the motivation for our program(s).

Before I present an algorithm to address financial problems, let us expand our scope to include not only discrete compounding but continuous compounding as well. This turns out to be very easy. Our factors become exponentials instead of powers, so (1 + i /100) t is replaced by exp(i * t / 100) . Money compounded continuously grows faster than money compounded discretely at the same rate and for this reason IRRs for continuous compounding are smaller than IRRs for the same discrete problem. You may wish to try recomputing our $100 bank account problem for continuous compounding. The IRR for this problem is 5.85%.

Let us agree on a straightforward input format with one dollar, time pair per line with both dollars and times as floating-point numbers for complete generality. For our little bank account problem the input file is:

-100 0.0
  40 1.0
  70 2.0

Note the negative sign on the investment.

I chose Newton's method to solve this problem, mainly because I know that the powers in the problem and their derivatives are well-behaved functions. More importantly, however, we have a handle on the IRR. Interest rates are usually in the 3% to 20% range, allowing us to choose a starting value that is, for most real world problems, going to ensure convergence.

Initially, I used a straightforward algorithm, applying Newton's method directly to the IRR equation. While I was successful, I noted that for some data sets the number of iterations required was disturbingly large. I plotted the IRR equation against the interest and quickly discovered the problem. Newton's method owes its simplicity to the neglect of all terms beyond linear ones, and thus, it works best when higher-order terms are relatively small. Another way of saying the same thing is that the closer the function is to a straight line, the quicker the linear Newton's method converges.

My plots revealed significant curvature of the IRR function, so I tried manipulating the equation into a “flatter” form. The trick is to collect the time-corrected terms into separate negative (expenses) and positive (income) groups. If we denote the sums as pos_sum and neg_sum we have equality:

pos_sum = neg_sum

where both sums are positive numbers. Dividing both sides of this equation by pos_sum and taking the logarithm of the result we have:

ln(neg_sum / pos_sum) = 0

The logarithm flattens the function and makes for very quick convergence. The slight trade-off of having to calculate the log is more than compensated for by the reduction in the number of iterations. I made the following substitution:

exp(-u) = 1 + i

and solved for u first, then i, which simplifies the calculations even more.

Three listings are available for anonymous download from ftp.linuxjournal.com/pub/lj/listings/issue48/2545.tgz: Listing 1 is the Perl program, irr.pl;Listing 2 is the same program in C, irr.c; and Listing 3, irr.java, is the equivalent Java code. Due to space considerations only the Perl code is printed here (see Listing 1).

Let us look at the Perl program first. It is the shortest of the three programs, in part because of Perl's many built-in functions and in part because of Perl's built-in memory management. It displays a simple usage message and exits should the user forget the expected format. There are three constants, one to control the maximum number of iterations before exiting the Newton loop, one to decide if convergence has occurred, and a starting value for the IRR (u = i = 0.0).

The data file is read in a loop, using the arrays @pos_d, @pos_t, @neg_d and @neg_t to hold the income and expenses and their respective times. Note that Perl dynamically allocates memory for the arrays as the data is read. The write function performs formatted output using the formats at the end of the program. Before starting the Newton algorithm loop we make sure the input data contains both income and expenses—the algorithm will not converge unless it does.

The for loop on the variable $iters is the Newton algorithm, where $d_neg and $d_pos are the derivatives with respect to u of the numerator and denominator, respectively. The program concludes with a display of the IRR if convergence is attained. Note that scalar variables start with a dollar sign and arrays with an @ sign. Variables and arrays do not have types and can contain strings or numbers with the type being determined by usage.

Note that Perl's print function accepts variable names and interpolates the actual value, whereas printf works pretty much like its C counterpart. Also, you can put “if” tests after the statements they control.

As a non-trivial example, consider the data set in Listing 2. In this example you spend $1000 today, get back $500 in a year, only to spend another $2000 two years from today, etc., with a total of six transactions spread out over five years. We can run the Perl program with this data set by typing:

irr.pl irr.dat

This results in a display of the input data followed by the line:

IRR = 10.6952% (discrete) = 10.1611% (continuous) after 3 iterations.

Note that it takes a higher interest rate when compounding is discrete to give the same return as continuous compounding. You will, of course, get the same results from the other two programs.

The C program is longer than its Perl equivalent—about twice as long. In the C program, I chose to define a structure for the dollar and time pairs. One complication—I had to scan the input data twice: the first time to determine the number of pairs so that I could use malloc to allocate memory for the array of structures, the second to actually load the data into memory. In this program I placed the Newton algorithm in a static function called irr. This function is of a defined type, ITERATOR, and returns either OK or NO_CONVERGE depending on whether the algorithm converges. The iterating function looks very much like the equivalent Perl code.

The Java program for IRR is longer yet, partly because of the exception checking, but also because I defined several classes in addition to my public Irr class. There are no structures in Java, so I put the input data into its own Expenses class. I used the interface Do_irr_returns to hold the return values as the equivalent to the C enumerations for the same purpose. This organization of the program into classes and interfaces tends to increase the amount of code, but leads to clear and easy-to-read programs. The MyDouble and MyInt classes serve another purpose, as well.

In Java, native variables are passed by value. There is no concept of passing by address, at least for individual built-in variables. One way around this limitation is to create classes as wrappers and then to pass the classes to methods. The MyDouble class is endowed with a constructor, so that we can set an initial value for du.

Note that there was no reason to scan the input data twice in this case. The variable in_data of type Vector grows automatically as elements are added—no allocating or reallocating of memory is necessary.

I contacted my state lottery in Colorado and came up with a good IRR problem. If you win the lottery, you have a choice of taking a lump sum equal to 40% of your winnings or 25 payments starting with 1/40 of your winnings followed by checks that increase by 3.7% each year. For example, if you win a million dollars you can walk away with a check for $400,000 (less federal and state withholding taxes of 28% and 4%, respectively) or receive yearly payments starting with $25,000, then $25,925, etc., through the last check for $59,790.22 (withholding applies to these checks, too). Add up those 25 checks and, indeed, you get your million dollars. (For you purists, or if you just like to count your pennies, you will note that the exact total is $1,000,066.48. The true increase each year is slightly less than 3.7%.) The question faced by every lottery winner is whether it is better to take the lump sum or the payments over time. From a strictly financial standpoint the question is answered once the IRR is determined. That is, at what interest rate would you have to invest the $400,000 to be able to write yourself the same 25 checks? The answer will be in my next article.

We have looked at the problem of determining the effective interest rate for a series of expenditures and returns of arbitrary amounts and occurring at arbitrary times. We developed the equation for the internal rate of return and manipulated it into a form that is suitable for application of Newton's method. We looked at equivalent programs in Perl, C and Java. You can use these programs to solve for interest rates and to compare investments for any problem involving transactions over time.