matlab - 在 MATLAB/octave 中为 n > 100 创建更快的斐波那契函数

Question

我有一个函数可以告诉我斐波那契数列中的第 n 个数字。问题是当试图在斐波那契数列中找到更大的数字时，它变得非常慢，有人知道我该如何解决这个问题吗？

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

结果，

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

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

在执行 rtfib(100)

5 分钟后，我什至无法获得值

PS:我用的是octave 3.8.1

Answer 1

如果时间很重要(不是编程技术):

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;耗时是 0.000086 秒。

您甚至可以使用 uint64。 n = 92 是您可以从 uint64 获得的最大值:

tic;fib(92);toc; ans = 12200160415121876738;耗时是 0.001409 秒。

因为，

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

编辑

为了使 fib(n) 达到 n = 183，可以将两个 uint64 用作一个数，

具有求和的特殊功能，

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 是:

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

注意 LongSum 中的一些复杂情况似乎没有必要，但实际上并非如此!

(内部 if 的所有处理是我想避免在一个命令中使用 s = a + b - MaxNum，因为它可能溢出并存储不相关的数字在 s)

结果

tic;fib(159);toc;耗时是 0.009631 秒。

ans = 1226132595394188293000174702095995

tic;fib(183);toc; 耗时是 0.009735 秒。

fib(183) = 127127879743834334146972278486287885163

但是，您必须小心 sprintf。

我也用三个 uint64 做到了，我可以达到，

tic;fib(274);toc; 耗时是 0.032249 秒。

ans = 1324695516964754142521850507284930515811378128425638237225

(这几乎是相同的代码，但如果您有兴趣，我可以分享它)。

注意根据问题，我们有 fib(1) = 1 , fib(2) = 2，而 fib(1 ) = 1 , fib(2) = 1, 列出前 300 个 fib here (感谢@Rick T)。