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 or (dense writing, as is normal in HAKMEM) 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)