On The Computational Complexity of Being Greedy
Entry posted by wpirobotbuilder
697 views
During my lunch break today, I wrote this MATLAB function:
function [rate] = greedy( balance, periods, profit)
% greedy Takes in a numerical balance, an integer number of periods, and
% the desired profit to be made from the loan holder. Returns the optimal
% APR in decimal form (i.e. 3.94% = .0394)
payment = (profit + balance)/periods;
syms x
fun = 0;
for i = 0:periods-1
fun = fun - payment*(1+x/12)^i;
end
fun = fun + balance*(1+x/12)^periods;
solns= double(solve(fun == 0, x));
rate = solns(solns> 0);
end
The coding description is pretty brief; I'll outline it a little more:
P is the desired monthly payment from the loan holder such that, over a given number of periods n, we will obtain the desired profit R, in dollars, from an initial loan balance B, also in dollars. It can be calculated as follows:
P = (B + R)/n
fun(x) is the amount of money left on the balance B after n periods of interest, which compounds at rate x, assuming the loan holder makes a single payment of amount P every period of interest. It is generated as a symbolic expression of the variable x, which evaluates to:
fun(x) = B*(1 + ax)n-1 - P(1 + ax)n-2 - P(1 + ax)n-3 - ... - P(1 + ax)1 - P
Where B is the starting loan balance, P is the required monthly payment, n is the number of periods for interest to compound, and a is the inverse of the rate of interest compounding (1/12).
The goal is to find a zero of the function fun(x), i.e. (x : fun(x) = 0). This will return the optimal APR such that the loan is paid off in full after n periods of interest compounding.
This is not easy to solve. The polynomial order of fun(x) grows linearly with n, which means finding the roots of an (n-1)th order polynomial. If your loan compounds over 5 years (60 months), you are solving for the roots of a polynomial that looks like this:
f(x) = a0x59 + a1x58+ ... + a58x + a59
Yikes. Fortunately, MATLAB has the beautiful function solve, which you see in the script above. This allows us to solve for all the roots of the polynomial. As it turns out, most of them are complex numbers with a nonzero imaginary part, but most of the time there is one real root, which is the one you care about.
For example:
I have a $14162 car loan with a 3.94% APR, to be paid back monthly for 5 years. According to calculator.net, I will give the bank approximately $1463.89 over those 5 years, paying out $260.43 per month.
Running the MATLAB function,
We can see that our function works. And if the bank wanted to make a large sum, say $3200:
That is about the original APR I was offered before I got a cosigner with good credit.
This algorithm doesn't take very long to run on modern computers, making it incredibly easy to do this. Of course, it didn't stop loaners before, because you could work in reverse, trying different APRs and calculating the profit from each APR until you got something close to what you wanted.
It was a good lunch break.
5 Comments