2 ms·
You could compare against a closed-form solution: let fib2 n = let sq5 = sqrt(5.0) ((1.0 + sq5)/2.0)**(float n)/sq5 |> round |> int
by davidgrenier 4y ago
You could compare against a closed-form solution:
let fib2 n =
let sq5 = sqrt(5.0)
((1.0 + sq5)/2.0)**(float n)/sq5
|> round |> int
- MereInterest 4y agoThe problem is that the closed-form solution is vulnerable to floating-point error. If the calculations are done in float32 (including all intermediate steps), then the 32nd fibonacci number is erroneously given as 2178310, instead of the correct value of 2178309. Using float64 does better, but still has an error at the 71st fibonacci number. (I made a quick plot of the error as a function of N at https://i.imgur.com/bbc9OFC.png https://i.imgur.com/bbc9OFC.png. As soon as the error crossed ±0.5, the rounding results in the wrong result.) These are fine for property-based testing, so long as you restrict yourself to the range in which you have a correct value. But at that point, you might as well just hard-code the first 93 fibonacci numbers (the most that will fit in a uint64_t) and be done with it.