Generate Fibonacci Sequence in Compile-Time using generics

user_13954423 0
Viewed 761

In C++ with template metaprogramming you can calculate the fibonacci sequence in compile-time easily in this way.

template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }

But in rust you cant just pass a constant through a generic as far as I know, also I know that sometimes rust optimizes some funcions to just constants in assmebly code. Example: https://rosettacode.org/wiki/Compile-time_calculation#Rust

But the conventional recursive approach of the problem is not optimized to a constant.

fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}

// Call it with
fibo(45); // It takes around 5 secs, calculated at runtime

Ok, to this point I can undestand that just the compiler does not know how to optimize this, but I found a way to make this calculated at compile time using Iterators!

struct Fibo(u32, u32);

impl Iterator for Fibo {
    type Item = u32;
    fn next(&mut self) -> Option<Self::Item> {
        *self = Fibo(self.1, self.1 + self.0);
        Some(self.0)
    }
}

fn fibo() -> Fibo {
    Fibo(0, 1)
}

// Call it with
fibo().take(45).collect::<Vec<_>>()[44]; // This gets the 45th element calculated at compile-time, instantly

At this point I just want to know why this happens.

rust compile-time generics
3 Answers

Algorithmic Complexity

The naive way of computing the Fibonacci sequence has exponential complexity

fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}

You can visualize it like:

  • fibo(0): 1 call.
  • fibo(1): 1 call.
  • fibo(2): 3 calls -- fibo(2), fibo(1), fibo(0).
  • fibo(3): 5 calls -- fibo(3), fibo(2) (which is worth 3), fibo(1).
  • fibo(4): 9 calls -- fibo(4), fibo(3) (worth 5) and fibo(2) (worth 3).

The iterator version, however, is completely different. Rewritten as a function it boils down to:

fn fibo(n: i32) -> i32 {
    fn rec(i: i32, current: i32, next: i32) -> i32 {
        if i == 0 { current } else { rec(i - 1, next, current + next) }
    }

    rec(n, 0, 1)
}

Which executes in exactly n + 1 steps... providing n >= 0.

But in C++ it works!

C++ compilers tend to use memoization for both template instantiations and constexpr evaluations. They do not have to, this is strictly an implementation detail, but they do for efficiency reasons.

In this instance, a memoized version of fibo turns exponential complexity into linear complexity, which is much easier to compute.

Doing it in Rust!

It's possible to compute fibonacci in Rust at compile-time with the current beta, which stabilizes branches in const functions.

See the playground:

const fn fibo(n: i32) -> i32 {
    const fn rec(i: i32, current: i32, next: i32) -> i32 {
        if i == 0 { current } else { rec(i - 1, next, current + next) }
    }

    rec(n, 0, 1)
}

fn main() {
    const RESULT: usize = fibo(9) as usize;

    let array: [i32; RESULT] = [
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        0, 1
    ];
    
    println!("{}", array[0]);
}

There may be a trick to express the computation at compile-time without a branch, allowing to compute fibo at compile-time on stable, however I am not sure rustc wouldn't perform the recursive call regardless.

user_1471920

I looked at the assembly output of your second code example, and the compiler does not seem to optimise this to a constant. Likely, something very different is going on.

The approach you call the "classic" recursive algorithm is the worst way of computing Fibonacci numbers, since the number of function invocations grows exponentially with n. The iterative approach is much better, since it only requires a number of iterations linearly growing with n. For n = 44, that works out to about ten trillion function invocations for the recursive approach, versus 44 loop iterations for the iterative approach. Of course the latter appears "instant" at run time, but that doesn't mean any particular compiler magic is happening here.

(For really big n you need arbitrary precision arithmetic, and the best approach is binary matrix powering.)

Now for your second question, how to get Rust to evaluate this at compile time. Template metaprogramming in C++ is actually a crutch for compile time computations, and Rust has a far easier approach: constant functions. Some aspects of const fns are still evolving, but in the current beta version (which will be released as stable in about two weeks), you can write the Fibonacci function in a rather straightforward way:

pub const fn fibo(mut n: u64) -> u64 {
    let mut a = 1;
    let mut b = 0;
    while n > 0 {
        let tmp = b;
        b += a;
        a = tmp;
        n -= 1;
    }
    b
}

pub const K: u64 = fibo(93);

(Playground)

There are also const generics in Rust, but they are unstable (and still rather buggy). It is possible that you can do something similar to the C++ template metaprogramming version, but I didn't look into it.

user_2796270 
const fn fibo(n: i32) -> i32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo(n - 1) + fibo(n - 2),
    }
}
const A: i32 = fibo(45);

This code will be computed at compile time.
But it'll take a long time to compile it and it fails to be compiled on the playground. So rust may not optimize it.
You can also see the mir and ir

user_140865810
Related