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

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.

[Adam]

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.

Answer 1

[John D'Errico]

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.

Answer 2

[Image Analyst]

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