Not to say anything about the central thesis of the post, but the two examples of how deeper mathematical knowledge can lead to better programming are just terrible examples. As someone whose background was originally mathematics and starting programming relatively late, I can very much relate to thinking Binet's formula for Fibonacci numbers or gamma function for factorials might be faster than recursive methods. But when you actually learn about how ints, floats and their arithmetic is implemented at a low level, how cache and memory works etc, you realise that recursive methods for those two problems are actually your best bet, both for speed and accuracy. So ironically, these are examples where knowing much about low level coding and computing architecture helps you more than knowing more advanced mathematics.
Sure, if you need to continually access the same values then you'd want to save them but whether you need to reuse the same values or just do a one off calculation, you still need to compute the value the first time in some way.
For Fibonacci numbers, expressing terms of the sequence as a 2x2 matrix exponentiatied and then exponentiating by repeated squaring let's you get the n-th Fibonacci number in O(log n) multiplications. It's straightforward, if you get an input n and handle arbitrary precision integer arithmetic, you can calculate F_1000 quickly and without much hassle. Compare that to Binet's formula: How many digits of precision will you need to compute the golden ratio to ensure your result from Binet's formula is correct? And how will you compute it to that many digits? And that's not even worrying about the fact that floating point multiplication doesn't correspond exactly to multiplication of real numbers, so you may need to switch to arbitrary precision floating point arithmetic.
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).
I computed Fibonacci(20*10^6) using Binet's formula. The answer has 4179753 digits. I computed sqrt(5) to 4179753 digits and applied the formula. The result was correct.
The time to compute sqrt(5) was 0.23 sec. The time compute the formula (I dropped the insignificant 1-sqrt(5) term) was 2.8 seconds. When I used the built in Mathematica function to compute the Fibonacci number, it took 0.12 seconds.
