在MATLAB/octave中为n> 100创建更快的Fibonacci函数

Question

我有一个函数告诉我Fibonacci序列中的第n个数字.问题是,当试图在Fibonacci序列中找到更大的数字时它变得非常慢有没有人知道如何解决这个问题？

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.

5分钟后我甚至无法获得价值 rtfib(100)

PS:我正在使用八度音阶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; Elapsed time is 0.000086 seconds.

你甚至可以使用uint64.n = 92是你能得到的最多uint64:

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

因为,

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; Elapsed time is 0.009631 seconds.

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个纤维(感谢@Rick T).

Answer 2

似乎斐波那契（Fibonaacci）系列紧随其后golden ratio，正如详细讨论的那样here。

这是在此MATLAB文件交换代码中使用的，而我在这里写的只是它的本质-

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

您可以输入一个整数n作为nth数字，Fibonacci Series也可以输入一个数组1:n以包含整个序列。

请注意，此方法n = 69仅适用于。

Answer 3

如果您可以访问MATLAB中的Symbolic Math Toolbox，则始终可以 从MuPAD 调用 Fibonacci函数：

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

它非常快：

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

另外，您还可以根据需要选择尽可能多的数字（仅受拥有多少RAM的限制！），它仍在快速发展：

% 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

这是的完整值fib(100000)：http : //pastebin.com/f6KPGKBg