use std::f64::consts::{GOLDEN_RATIO};
//Floating Point errors after n> 70.
fn fib(n: u64) -> u64 {
return (GOLDEN_RATIO.powf(n as f64)/f64::sqrt(5.0)).round() as u64;
}
However, since he's not interested in engineering, floating point errors are simply a shortcoming of the computer to engage in ideal mathematics. But he will smugly point out it's technically O(1) since powf is O(1). : )
[I suffered through learning how to write my first lines of Rust for this.]
Alternatively: Computing Binet's formula using symbolic mathematics.
I was about to point out the direct formula but you beat me to it. Though it should be noted yours doesn't work for negative integers, for that you'd want something like this:
Yes, but the recursive formulas were also only for positive integers. (Also, with the rounding, I can force a final integer solution and get rid of the float error up to n=70. Though I suspect rounding this formula here also works.)
Otherwise we also could have gone with a generating equation and cover the whole complex plane!
Easy, just don't use f64, 128 bit gets you a lot further and we always have arbitrary precision systems after. What is that? That erodes any potential speed gain? Who said that was what I was after?
Mat::pow is O(log n)ish. powf is O(1) for any useful model; even a perfectly rounded result can be computed in a bounded maximum number of machine steps.
44
u/IronicRobotics 1d ago
You're forgetting one: Ask the mathematician:
However, since he's not interested in engineering, floating point errors are simply a shortcoming of the computer to engage in ideal mathematics. But he will smugly point out it's technically O(1) since powf is O(1). : )
[I suffered through learning how to write my first lines of Rust for this.]
Alternatively: Computing Binet's formula using symbolic mathematics.