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

>> fibonacci(51)
ans =
    20365011074
>> mod(20365011074, 65536)

ans =

         26754

>> fibonacci(51, 65536)
ans =
    59522

[Walter Roberson]

This is possibly referring to https://www.mathworks.com/matlabcentral/fileexchange/34766-the-fibonacci-sequence/content/FibonacciSequence/fibonacci.m

[John D'Errico]

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]

That's correct. The fibonacci number is computed correctly. The problem arises when the modulo is provided. Thanks!

Answer 1

[John D'Errico]

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.)

[John D'Errico]

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.