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

fibonaccifunctionloop

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.

Best Answer

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.

Related Solutions

MATLAB: How do you save really big integers in the symbolic toolbox

VPI has no problem dividing a number by 2. Here, for example, is one of my favorite moderately large primes. (That is, it is the smallest value of n, such that (n+1)*17^n-1 is a prime.)

N = 42*vpi(17)^41 - 1;
N
N =
    11793835525721281286023333792285550996689383337325513
mod(N,2)
ans =
    1
N/2
ans =
    5896917762860640643011666896142775498344691668662756
[Q,R] = quotient(N,2)
Q =
    5896917762860640643011666896142775498344691668662756
R =
    1

You can use quotient divides by 2, also returning the remainder of that integer divide.

But, if you absolutely need to use syms...

N = 42*sym(17)^41 - 1
N =
11793835525721281286023333792285550996689383337325513
mod(N,2)
ans =
1

The reason you had a problem with sym is because you used it improperly. When you did this:

n = sym(85098710871039482877157098724987234509871123545)

you made a mistake. When you type it like this:

n = sym(85098710871039482877157098724987234509871123545)
n =
85098710871039487337987513201467377652091322368

MATLAB does NOT look at what you will be doing with the number 85098710871039482877157098724987234509871123545. It converts it to a DOUBLE, so roughly 16 decimal digits. Then it passes that to sym, so you get garbage. Remember that when you want a number to be interpreted NOT as a double, you cannot let MATLAB create the number as a double. Both VPI and SYM have a simple way to avoid that problem.

See the difference here:

n = sym('85098710871039482877157098724987234509871123545')
n =
85098710871039482877157098724987234509871123545

In fact, VPI has the same problem. You cannot just pass that number to VPI as a double. syms actually has no problem with factoring that number.

factor(sym('85098710871039482877157098724987234509871123545'))
ans =
[ 3, 5, 59, 144864327936049, 663770969827375707224424962533]

In fact, sym is quicker than is VPI on that number, in fact, syms even beats my replacement for VPI, thus is much faster than VPIJ in factoring. (One thing I always wanted to improve. One day I'll get a nice quadratic sieve code running for VPIJ.)

MATLAB: Helped needed in Fibonacci Sequence code

Hello Cici. We can solve this by introducing another variable count into the function as shown below.

function[F_n, count] = Fibonacci(n, count)
    count = 1;
    
    if n == 2
        F_n = 1; 
    elseif n == 1
        F_n = 0;
    else
        [F_n_1, count_1] = Fibonacci(n-1);
        [F_n_2, count_2] = Fibonacci(n-2);
        F_n = F_n_1 + F_n_2;
        count = count + count_1 + count_2;
    end
end

Now your function returns both the

Fibonacci number as well as the number of times the function was called.

You may capture only the count in variable ans using this code snippet for the desired value of n.

[~, ans] = Fibonacci(n);

Hope this helps. :)

Best Answer

Related Solutions

MATLAB: How do you save really big integers in the symbolic toolbox

MATLAB: Helped needed in Fibonacci Sequence code

Related Question