Fibonacci f64 - O(1) solution

Published 339d ago

This calculates any arbitrary Fibonacci sequence number in O(1) time, without loops or recursion. Uses the absolute formula to give a best estimate result. Needs an infinite precision math library to give more accurate results.

fn fib(n: f64) -> f64 {
    let sqrt5 = 5f64.sqrt();
    let phi = (1. + sqrt5) / 2.;
    (phi.powf(n) - (1. - phi).powf(n)) / sqrt5
}

fn main() {
    for i in 0..=500 {
        println!("fib({i}) = {:.0}", fib(i as f64));
    }
}