If time很重要(不是编程技术):
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.
Because,
fib(93) = 19740274219868223167 > intmax('uint64') = 18446744073709551615
Edit
为了得到fib(n)
up to 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
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一些并发症LongSum
可能看起来没有必要,但事实并非如此!
(所有的事情都与内心有关if
是我想避免的s = a + b - MaxNum
在一个命令中,因为它可能会溢出并在其中存储不相关的数字s
)
Results
tic;fib(159);toc; Elapsed time is 0.009631 seconds.
ans = 1226132595394188293000174702095995
tic;fib(183);toc;
已用时间为 0.009735 秒。
纤维 (183) = 127127879743834334146972278486287885163
不过,你必须要小心sprintf
.
我还用三个 uint64 做到了这一点,我可以达到,
tic;fib(274);toc;
经过的时间为 0.032249 秒。
答=1324695516964754142521850507284930515811378128425638237225
(这几乎是相同的代码,但如果您有兴趣,我可以分享它)。
Note我们有fib(1) = 1 , fib(2) = 2
根据问题,虽然更常见的是fib(1) = 1 , fib(2) = 1
, 列出前 300 个小纤维here(感谢@Rick T)。