Create faster Fibonacci function for n > 100 in MATLAB / octave

Question

I have a function that tells me the nth number in a Fibonacci sequence. The problem is it becomes very slow when trying to find larger numbers in the Fibonacci sequence does anyone know how I can fix this?

function f = rtfib(n)
 if (n==1)
     f= 1;
 elseif (n == 2)
     f = 2;
 else
     f =rtfib(n-1) + rtfib(n-2);   
 end

The Results,

tic; rtfib(20), toc
ans =  10946
Elapsed time is 0.134947 seconds.

tic; rtfib(30), toc
ans =  1346269
Elapsed time is 16.6724 seconds.

I can't even get a value after 5 mins doing rtfib(100)

PS: I'm using octave 3.8.1

Carbineer

Write an iterative solution, rather than a recursive solution. – Rolland

It might be faster when you avoid the rekursive call but use an array instead. – Rankins

https://mcmap.net/q/567792/-what-is-a-non-recursive-solution-for-fibonacci-like-sequence-in-java/97160 – Febricity

If the function must only output the nth term, not the first n terms of the sequence, you can do it in θ(log(n)) complexity with recursive doubling. Max's answer hints at such a solution. – Triumph

Answer 1

If time is important (not programming techniques):

function f = fib(n)
if (n == 1)
   f = 1;
elseif (n == 2)
   f = 2;
else
   fOld = 2;
   fOlder = 1;
   for i = 3 : n
     f = fOld + fOlder;
     fOlder = fOld;
     fOld = f;
   end
end
end

tic;fib(40);toc; ans = 165580141; Elapsed time is 0.000086 seconds.

You could even use uint64. n = 92 is the most you can get from uint64:

tic;fib(92);toc; ans = 12200160415121876738; Elapsed time is 0.001409 seconds.

Because,

fib(93) = 19740274219868223167 > intmax('uint64') = 18446744073709551615

Edit

In order to get fib(n) up to n = 183, It is possible to use two uint64 as one number,

with a special function for summation,

function [] = fib(n)
fL = uint64(0);
fH = uint64(0);
MaxNum = uint64(1e19);
if (n == 1)
   fL = 1;
elseif (n == 2)
   fL = 2;
else   
   fOldH = uint64(0);
   fOlderH = uint64(0);
   fOldL = uint64(2);
   fOlderL = uint64(1);
   for i = 3 : n
      [fL q] = LongSum (fOldL , fOlderL , MaxNum);
      fH = fOldH + fOlderH + q;
      fOlderL = fOldL;
      fOlderH = fOldH;
      fOldL = fL;
      fOldH = fH;
   end
 end
 sprintf('%u',fH,fL)
 end

LongSum is:

function [s q] = LongSum (a, b, MaxNum)
if a + b >= MaxNum
   q = 1;
   if a >= MaxNum
      s = a - MaxNum;
      s = s + b;
   elseif b >= MaxNum
      s = b - MaxNum;
      s = s + a;
   else
      s = MaxNum - a;
      s = b - s;
   end
else
   q = 0;
   s = a + b;
end

Note some complications in LongSum might seem unnecessary, but they are not!

(All the deal with inner if is that I wanted to avoid s = a + b - MaxNum in one command, because it might overflow and store an irrelevant number in s)

Results

tic;fib(159);toc; Elapsed time is 0.009631 seconds.

ans = 1226132595394188293000174702095995

tic;fib(183);toc; Elapsed time is 0.009735 seconds.

fib(183) = 127127879743834334146972278486287885163

However, you have to be careful about sprintf.

I also did it with three uint64, and I could get up to,

tic;fib(274);toc; Elapsed time is 0.032249 seconds.

ans = 1324695516964754142521850507284930515811378128425638237225

(It's pretty much the same code, but I could share it if you are interested).

Note that we have fib(1) = 1 , fib(2) = 2according to question, while it is more common with fib(1) = 1 , fib(2) = 1, first 300 fibs are listed here (thanks to @Rick T).

Feaster

Thanks!!! Very Fast!!! For those who may use this in the future. Please note the sequence of fib numbers is off by one when checked against a list of fibonacci numbers maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html – Carbineer

I think you can use this too for large sums. – Apparently

@Amro, because we started with fib(1) = 1 and fib(2) = 2, (according to question), while it's more common with fib(1) = 1 and fib(2) = 1. – Feaster

Answer 2

Seems like fibonaacci series follows the golden ratio, as talked about in some detail here.

This was used in this MATLAB File-exchange code and I am writing here, just the esssence of it -

sqrt5 = sqrt(5);
alpha = (1 + sqrt5)/2;   %// alpha = 1.618... is the golden ratio
fibs  = round( alpha.^n ./ sqrt5 )

You can feed an integer into n for the nth number in Fibonacci Series or feed an array 1:n to have the whole series.

Please note that this method holds good till n = 69 only.

Levina

nice about the connection of fib and golden ratio. – Feaster

Does this approach maintain accuracy as n increases in magnitude? – Rolland

@OliverCharlesworth You are right about that! Thank you on pointing out that. So, I have checked with vpa and it's good till 69 only. – Levina

Answer 3

If you have access to the Symbolic Math Toolbox in MATLAB, you could always just call the Fibonacci function from MuPAD:

>> fib = @(n) evalin(symengine, ['numlib::fibonacci(' num2str(n) ')'])
>> fib(274)
ans =
818706854228831001753880637535093596811413714795418360007

It is pretty fast:

>> timeit(@() fib(274))
ans =
    0.0011

---

Plus you can you go for as large numbers as you want (limited only by how much RAM you have!), it is still blazing fast:

% see if you can beat that!
>> tic
>> x = fib(100000);
>> toc               % Elapsed time is 0.004621 seconds.

% result has more than 20 thousand digits!
>> length(char(x))   % 20899

Here is the full value of fib(100000): http://pastebin.com/f6KPGKBg

Febricity

some related readings: mathforum.org/library/drmath/view/52677.html, catonmat.net/blog/… – Febricity

highly recommended: mathworks.com/matlabcentral/fileexchange/… (really anything by John D'Errico you know is high quality!) – Febricity

Answer 4

To reach large numbers you can use symbolic computation. The following works in Matlab R2010b.

syms x y %// declare variables
z = x + y;  %// define formula
xval = '0'; %// initiallize x, y values
yval = '1'; 
for n = 2:300
    zval = subs(z, [x y], {xval yval}); %// update z value
    disp(['Iteration ' num2str(n) ':'])
    disp(zval)
    xval = yval; %// shift values
    yval = zval;
end

Cattier

I would love to try this out but the symbols package in octave isn't really compatible with matlab code yet. It gives errors with syms x y – Carbineer

Answer 5

You can do it in O(log n) time with matrix exponentiation:

X = [0 1
     1 1]

X^n will give you the nth fibonacci number in the lower right-hand corner; X^n can be represented as the product of several matrices X^(2^i), so for example X^11 would be X^1 * X^2 * X^8, i <= log_2(n). And X^8 = (X^4)^2, etc, so at most 2*log(n) matrix multiplications.

Joist

Answer 6

One performance issue is that you use a recursive solution. Going for an iterative method will spare you of the argument passing for each function call. As Olivier pointed out, it will reduce the complexity to linear.

You can also look here. Apparently there's a formula that computes the n'th member of the Fibonacci sequence. I tested it for up to 50'th element. For higher n values it's not very accurate.

Sodality

It's way more than just saving the argument passing; it reduces the time complexity from exponential to linear. – Rolland

Answer 7

The implementation of a fast Fibonacci computation in Python could be as follows. I know this is Python not MATLAB/Octave, however it might be helpful.

Basically, rather than calling the same Fibonacci function over and over again with O(2ⁿ), we are storing Fibonacci sequence on a list/array with O(n):

#!/usr/bin/env python3.5

class Fib:
    def __init__(self,n):
        self.n=n
        self.fibList=[None]*(self.n+1)
        self.populateFibList()
    def populateFibList(self):
        for i in range(len(self.fibList)):
            if i==0:
                self.fibList[i]=0
            if i==1:
                self.fibList[i]=1
            if i>1:
                self.fibList[i]=self.fibList[i-1]+self.fibList[i-2]
    def getFib(self):
        print('Fibonacci sequence up to ', self.n, ' is:')
        for i in range(len(self.fibList)):
            print(i, ' : ', self.fibList[i])
        return self.fibList[self.n]

def isNonnegativeInt(value):
    try:
        if int(value)>=0:#throws an exception if non-convertible to int: returns False
            return True
        else:
            return False
    except:
        return False

n=input('Please enter a non-negative integer: ')

while isNonnegativeInt(n)==False:
    n=input('A non-negative integer is needed: ')

n=int(n) # convert string to int

print('We are using ', n, 'based on what you entered')

print('Fibonacci result is ', Fib(n).getFib())

Output for n=12 would be like:

I tested the runtime for n=100, 300, 1000 and the code is really fast, I don't even have to wait for the output.

Marquettamarquette

Answer 8

One simple way to speed up the recursive implementation of a Fibonacci function is to realize that, substituting f(n-1) by its definition,

f(n) = f(n-1) + f(n-2)
     = f(n-2) + f(n-3) + f(n-2)
     = 2*f(n-2) + f(n-3)

This simple transformation greatly reduces the number of steps taken to compute a number in the series.

If we start with OP's code, slightly corrected:

function result = fibonacci(n)
switch n
case 0
   result = 0;
case 1
   result = 1;
case 2
   result = 1;
case 3
   result = 2;
otherwise
   result = fibonacci(n-2) + fibonacci(n-1);
end

And apply our transformation:

function result = fibonacci_fast(n)
switch n
case 0
   result = 0;
case 1
   result = 1;
case 2
   result = 1;
case 3
   result = 2;
otherwise
   result = fibonacci_fast(n-3) + 2*fibonacci_fast(n-2);
end

Then we see a 30x speed improvement for computing the 20th number in the series (using Octave):

>> tic; for ii=1:100, fibonacci(20); end; toc
Elapsed time is 12.4393 seconds.
>> tic; for ii=1:100, fibonacci_fast(20); end; toc
Elapsed time is 0.448623 seconds.

Of course Rashid's non-recursive implementation is another 60x faster still: 0.00706792 seconds.

Phenocryst