Writing a code for Fibonacci sequence that will return a number closest to the number entered?

7 views (last 30 days)
How can I write a function that returns the largest Fibonacci number that is less than or equal to x. The Fibonacci number is defined as: f(n)=f(n-1)+f(n-2)
where f(0)=1 and f(1)=1 . Assume x is a positive integer.
  1 Comment
Adam
Adam on 17 Oct 2014
Probably use recursion, but as with my answer to your other question - work out the algorithm first and then code it up, or build it up from a simple case to a more complex case and keep doing that until you get the full result (e.g. TDD) if you prefer.

Sign in to comment.

Accepted Answer

John D'Errico
John D'Errico on 17 Oct 2014
Edited: John D'Errico on 17 Oct 2014
He, he, he. Rolls Royce? Yes, it probably is.
But for this problem, I'd make use of good old Binet and his formulaic legacy, at least for a start.
If phi is the golden ratio, then we have
phi = (1 + sqrt(5))/2;
F = @(n) (phi^n - (-phi)^(-n))/sqrt(5);
For example, the 12th Fibonacci number is:
F(12)
ans =
144
It is not truly exact, at least not in terms of floating point numbers. But we need to learn to know when to trust a number to be an integer or not. This is an essential part of computing.
F(12) - 144
ans =
5.6843418860808e-14
I can verify that 144 value using my Rolls Royce engine.
fibonacci(12)
ans =
144
Note that for n reasonably large, we get a very good approximation by ignoring the second term in that formula. For example...
format long g
phi^12/sqrt(5)
ans =
144.001388875493
So a good approximation for the largest Fibonacci number that does not exceed some value k will be simply obtained by taking the log of that expression, and solving for n.
n_k = @(k) floor(log(k*sqrt(5))/log(phi));
n_k(145)
ans =
12
n_k(143)
ans =
11
For larger values of k, say 10^23,
n_k(1e23)
ans =
111
fibonacci(111)
ans =
70492524767089125814114
fibonacci(112)
ans =
114059301025943970552219
You will find that the formula works quite well even for small k.

More Answers (1)

Image Analyst
Image Analyst on 17 Oct 2014
I'm sure the Rolls Royce of Fibonacci programs is that uploaded by John D'Errico : http://www.mathworks.com/matlabcentral/fileexchange/34766-the-fibonacci-sequence. Take a look at how he does it.
"Often I see students asking for help on a tool to compute the Fibonacci numbers. Or, I'll find....."

Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!