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

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

Solution

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