3 ms·
If you add a "round to integer" step at the end, it doesn't require arbitrary precision arithmetic. Careful numerical analysis can tell you how many digits of p
by Someone 11y ago
If you add a "round to integer" step at the end, it doesn't require arbitrary precision arithmetic. Careful numerical analysis can tell you how many digits of precision you need to compute fib(n).
I would guess the end result would be similar to that of this method (2n bits being more than sufficient), the difference being that this method puts all the digits before the decimal point.
Also, for large n, you may be able to assume ψ = 0 to speed up computations (given ψ < n, its nth power will get vanishingly small)
But the matrix method is the easiest fast method one can write and prove robust.
(It is not fastest because the trivial binary approach doesn't product optimal addition chains. See https://en.wikipedia.org/wiki/Addition_chain https://en.wikipedia.org/wiki/Addition_chain or (dense writing, as is normal in HAKMEM) http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html)
Also, there is a very simple method for implementing "isFib":
isFib(n) := isSquare(5n^2+4) or isSquare(5n^2-4)
- user2994cb 11y agoMost fast methods for computing fib(n) come down to some variation of repeated squaring, so the time is dominated by the last multiplication (since the number of digits is doubling each time).