I don't think it's too hard to get the sqrt(5) to a high enough degree of precision. (Probably could use Newton-Raphson.) On my computer it takes about 0.05 s

I don't think it's too hard to get the sqrt(5) to a high enough degree of precision. (Probably could use Newton-Raphson.) On my computer it takes about 0.05 seconds to compute sqrt(5) to one million digits. It takes about 0.01 seconds to multiply two 500,000 digit integers. If you want to computer F_n using Binet's formula I think you need about (log(F_n)/log(10) + 10) digits for sqrt(5).