fibonacci - potential bug - Please see the 51st fibonacci number when using modulo 2^16

1 次查看（过去 30 天）
Vishali
Vishali 2017-2-5
编辑： John D'Errico 2017-2-5
>> fibonacci(51)
ans =
20365011074
>> mod(20365011074, 65536)
ans =
26754
>> fibonacci(51, 65536)
ans =
59522
  3 个评论
显示 1更早的评论
John D'Errico
John D'Errico 2017-2-5
编辑：John D'Errico 2017-2-5
I'll look at it in the morning. It may be a problem in the fibonacci code, when a modulus is provided. The fibonacci number is computed correctly.
Vishali
Vishali 2017-2-5
That's correct. The fibonacci number is computed correctly. The problem arises when the modulo is provided. Thanks!

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

John D'Errico
John D'Errico 2017-2-5
编辑：John D'Errico 2017-2-5
Turns out, there was a bug in my fibonacci code, that only surfaced in certain circumstances, when computing the mod internally for odd arguments of a sufficiently large size.
I had made an assumption about a specific Lucas number identity that did not always apply when computing the mods of the Lucas numbers.
I'll update the code in the FEX, but also attach the repaired version to this answer.
fibonacci(51,65536)
ans =
26754
mod(fibonacci(51),65536)
ans =
26754
Code attached, now tested fairly extensively. (Note: oops. Then I attached a version that uses vpij instead of vpi. vpij is my replacement for vpi, but is not available to the public as yet. The attachment here uses vpi.)
  1 个评论
John D'Errico
John D'Errico 2017-2-5
编辑：John D'Errico 2017-2-5
The current version uses a different set of identities for computing the Fibonacci and Lucas numbers when you need only the modulus wrt some number. Sorry about the problem. It took me a few hours to find the problem in the identity, because, well identities are usually exactly that, except when they are not valid. :)
for i = 1:1000
m = ceil(rand*100000);
k = ceil(rand*1000);
if (mod(fibonacci(k),m)-fibonacci(k,m))~= 0
disp('The Sky is falling!')
end
end
No failures detected.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Number Theory 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by