The Lucas number computation code currently uses the identity
L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k
Is there a reason this rather complex identity was chosen to
implement?
Wikipedia mentions the identity
L[n+k] = 5*F[n]*F[k] + (-1)^k * L[n-k]
Letting n = k+1, this gives us
L[2k+1] = 5*F[k+1]*F[k] + (-1)^k * L[1]
= 5*F[k+1]*F[k] + (-1)^k
This seems a lot simpler. It can be derived from the current
identity using Cassini's identity for the Fibonacci numbers:
F[k+1]*F[k-1] = F[k]^2 + (-1)^k
L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k
= 5*F[k-1]*(F[k]+F[k+1]) - 4*(-1)^k
= 5*F[k-1]*F[k] + 5*F[k-1]*F[k+1] - 4*(-1)^k
= 5*F[k-1]*F[k] + 5*F[k]^2 + 5*(-1)^k - 4*(-1)^k
= 5*F[k-1]*F[k] + 5*F[k]^2 + (-1)^k
= 5*F[k]*(F[k-1]+F[k]) + (-1)^k
= 5*F[k]*F[k+1] + (-1)^k
Lucas numbers are never congruent to 0 mod 8 (the congruence
is periodic mod 12, with residues (2 1 3 4 7 3 2 5 7 4 3 7)),
so when k is even, the +1 addition will never propagate more
than 3 bits.
It could also be used to compute L[2k] directly:
L[k+k] = 5*F[k]*F[k] + 2*(-1)^k
This would eliminate all iteration in the Lucas code and
let the Fibonacci code take care of everything.
The same proof technique lets us bound the carry propagation
even more tightly. L[2k] == {2, 3, 3} mod 4, so the addition
of 2 never propagates at all; it could be done with |=.
(Subtraction of 2, when k is odd, has no similar guarantee,
but it can't underflow below 0, so it's not a concern either.)
_______________________________________________
gmp-bugs mailing list
[email protected]
https://gmplib.org/mailman/listinfo/gmp-bugs
