I was given a short problem which was to sum the Fibonacci numbers below a given value. This was relatively simple using a function that iteratively loops through the Fibonacci numbers, maintaining a running sum until it reaches one greater than the limit:

int GetSumOfFibonacciNumbers(int nMax)
{

int fib_num_1 = 1; //the (nth) Fibonacci number (default first)
int fib_num_2 = 1; //the (n+1) Fibonacci number (default second)
int running_sum = 1; //variable to store the sum

if (nMax >= 1){
while (fib_num_2 <= nMax){

running_sum += fib_num_2;

//Cal next fib number
int temp = fib_num_2;
fib_num_2 += fib_num_1;
fib_num_1 = temp;

//cout << fib_num_2 << “\n”;
}
return running_sum;

} else
return -1;

}

But I was thinking that if we wanted to calculate this sum for Fibbonacci numbers less than 1,000,000 there should be a more efficient way…

After some poking around I discovered there is an explicit form for Fibonacci numbers in the form of the sum of two geometric sequences. “The standard formula for the Fibonacci numbers is due to a French mathematician named Binet. If F(n) represents the nth Fibonacci number, then”:

F(n) = (a^n – b^n)/(a – b)
where a and b are the two roots of the quadratic equation x^2-x-1 = 0.
i.e.a = (1 + Sqrt[5])/2 and b = (1 – Sqrt[5])/2, so a – b = Sqrt[5]

It turns out that ‘a=phi’ where phi is the golden ration, and b=1-phi. This gives us:

F(n) = [phi^n + (1-phi)^n]/sqrt(5)

Whilst this gave me hope, I couldn’t work out how to invert the equation and solve for ‘n’. In fact I believe equations in the form a^n + b^n = c cannot be directly solved and iterative methods such as Newton’s need to be used instead.

Whilst somewhat disappointed, some more reading revealed that there is an approximation (which becomes more accurate as ‘n’ increases – this is due to the decreasing nature of one of the geometric sequences):

F(n) ~= phi^n/sqrt(5)
= round[phi^n/sqrt(5)]

This is much easier to invert:

n ~= ln(F(n)*sqrt(5)) / ln(phi)

Due to rounding errors, sometimes the inverted form returns an index which is not quite right so I had to calculate F(n) and F(n+1) to determine which index was actually correct. Once I had the index I could use the formula for the sum of a geometric sequence (Sn:= a[(1-r^n)/(1-r)]) to calculate the sum:

a1 = a2 = 1/sqrt(5)
r1 = phi
r2 = (1-phi)

S(n) = [(1-phi^n)/(1-phi) + (1-(1-phi)^n)/(1-(1-phi))] / sqrt(5)

int GetSumOfFibonacciNumbers2(int FnMax)
{
// Can use the approximation for Fn:= phi^n/sqrt(5), where phi is the golden ratio
double golden_ratio = (1+sqrt(5))/2;
int n = round((log(FnMax*sqrt(5)))/(log(golden_ratio)) – 1);
//cout << n << endl;

//Calculate the index number – we need to check n+1 in case there is a small rounding issue
int Fn1 = round(pow(golden_ratio,n)/sqrt(5));
int Fn2 = round(pow(golden_ratio,(n+1))/sqrt(5));

//Check which n is correct, and update as nessacary
if (Fn2 <= FnMax){
n += 1;
cout << “<the maximum Fibonnaci number is: ” << Fn2 << “, n = ” << n << “>” << endl;
} else
cout << “<the maximum Fibonnaci number is: ” << Fn1 << “, n = ” << n << “>” << endl;

//Calculate the sum up to that number
//Fn:= (golden_ratio^n – (1-golden_ratio)^n)/sqrt(5);
// this is the sum of two geometric sequences so can use Sn:= a[(1-r^n)/(1-r)]
return ((1-pow(golden_ratio,n+1))/(1-golden_ratio) + (1-pow(1-golden_ratio,n+1))/(1-(1-golden_ratio)))/sqrt(5);
}

Whilst I now have two working solutions, I have yet to validate if/when the closed solution performs better than the open solution for larger values.

References:

http://mathforum.org/library/drmath/view/52707.html
http://mathforum.org/library/drmath/view/52700.html
http://mathforum.org/library/drmath/view/52677.html
http://mathforum.org/library/drmath/view/51448.html
http://vsdev.me/notes/closed_form_fib/
http://matthewhr.wordpress.com/2013/10/13/project-euler-fibonacci-numbers-and-problem-25/

Advertisements