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

问题描述 投票：11回答：8

我有一个函数告诉我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.

在做rtfib(100) 5分钟后我甚至无法得到一个值

PS：我正在使用八度音阶3.8.1

matlab octave fibonacci number-theory
8个回答
15
投票

如果时间很重要（不是编程技术）：

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

Edit

为了使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) = 2ac的问题，而它更常见的fib(1) = 1 , fib(2) = 1，前300个纤维列出here（感谢@Rick T）。

5
投票

看起来像fibonaacci系列跟随golden ratio，正如在一些细节here谈论。

这用于qazxsw poi，我在这里写，只是它的本质 - 

this MATLAB File-exchange code

您可以在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。

5
投票

如果您可以访问MATLAB中的符号数学工具箱，您可以随时从n = 69 just call斐波纳契函数：

MuPAD

这很快：

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

另外，你可以根据需要选择大量的数字（仅限于你有多少RAM！），它仍然非常快：

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

以下是% 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)

2
投票

要达到大数，您可以使用符号计算。以下在Matlab R2010b中有效。

http://pastebin.com/f6KPGKBg
1
投票

一个性能问题是您使用递归解决方案。寻找迭代方法将为您节省每个函数调用的参数传递。正如奥利维尔指出的那样，它会将复杂性降低到线性。

你也可以看看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 。显然，有一个公式可以计算斐波纳契数列的第n个成员。我测试了最多50个元素。对于更高的n值，它不是非常准确。

1
投票

您可以使用矩阵求幂在O（log n）时间内完成：

here

X ^ n会在右下角给你第n个斐波那契数字; X ^ n可以表示为几个矩阵X ^（2 ^ i）的乘积，因此例如X ^ 11将是X ^ 1 * X ^ 2 * X ^ 8，i <= log_2（n）。并且X ^ 8 =（X ^ 4）^ 2等，因此最多2 * log（n）个矩阵乘法。

0
投票

在Python中实现快速Fibonacci计算可以如下。我知道这是Python而不是MATLAB / Octave，但它可能会有所帮助。

基本上，我们不是用O（2n）一遍又一遍地调用相同的Fibonacci函数，而是将Fibonacci序列存储在带有O（n）的列表/数组中：

X = [0 1
     1 1]

#!/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()) 的输出如下：

n=12

我测试了enter image description here，n=100，300的运行时，代码非常快，我甚至不必等待输出。

0
投票

加速Fibonacci函数的递归实现的一种简单方法是认识到，用1000的定义代替，

f(n-1)

这种简单的转换大大减少了计算系列中数字所需的步骤数。

如果我们从OP的代码开始，稍微纠正：

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

并应用我们的转型：

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

然后我们看到计算系列中第20个数字的速度提高了30倍（使用Octave）：

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

当然>> 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. 还要快60倍：0.00706792秒。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.