使用泛型在编译时生成斐波那契数列

Question

在带有模板元编程的 C++ 中，您可以通过这种方式轻松地在编译时计算斐波那契数列。

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; }

但是在 rust 中，据我所知，你不能只通过泛型传递一个常量，我也知道有时 rust 会将一些函数优化为汇编代码中的常量。示例：https : //rosettacode.org/wiki/Compile-time_calculation#Rust

但是问题的常规递归方法并没有优化为常数。

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

好的，到目前为止，我无法理解只是编译器不知道如何优化它，但是我找到了一种方法可以在编译时使用迭代器进行计算！

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

在这一点上，我只想知道为什么会发生这种情况。

Answer 1

算法复杂性

计算斐波那契数列的天真方法具有指数级复杂度

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

你可以像这样想象它：

• fibo(0): 1 个电话。
• fibo(1): 1 个电话。
• fibo(2): 3 次调用 -- fibo(2), fibo(1), fibo(0).
• fibo(3): 5 次调用 -- fibo(3), fibo(2)(值 3), fibo(1).
• fibo(4): 9 次调用 -- fibo(4), fibo(3)（价值 5）和fibo(2)（价值 3）。

然而，迭代器版本完全不同。重写为一个函数，它归结为：

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)
}

它以精确的n + 1步骤执行...提供n >= 0.

但在 C++ 中它有效！

C++ 编译器倾向于将记忆化用于模板实例化和 constexpr 评估。他们不具有对，这是严格意义上的实现细节，但他们出于效率的考虑做。

在这种情况下， 的记忆版本fibo将指数复杂度转换为线性复杂度，这更容易计算。

在 Rust 中做！

可以使用当前的 beta 在编译时在 Rust 中计算斐波那契数，这可以稳定const函数中的分支。

看游乐场：

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]);
}

可能有一个技巧可以在没有分支的情况下在编译时表达计算，允许fibo在稳定的编译时进行计算，但是我不确定 rustc 无论如何都不会执行递归调用。

Answer 2

我查看了第二个代码示例的汇编输出，编译器似乎没有将其优化为常量。很可能，一些非常不同的事情正在发生。

您称之为“经典”递归算法的方法是计算斐波那契数的最糟糕的方法，因为函数调用的数量随 呈指数增长n。迭代方法要好得多，因为它只需要随 线性增长的迭代次数n。对于n = 44，对于递归方法，这相当于大约 10 万亿次函数调用，而对于迭代方法，则需要 44 次循环迭代。当然，后者在运行时出现“即时”，但这并不意味着这里正在发生任何特定的编译器魔术。

（对于真正大的，n你需要任意精度的算术，最好的方法是二进制矩阵供电。）

现在是你的第二个问题，如何让 Rust 在编译时评估它。C++ 中的模板元编程实际上是编译时计算的拐杖，而 Rust 有一个更简单的方法：常量函数。const fns 的某些方面仍在发展中，但在当前的 beta 版本中（大约两周后会稳定发布），您可以用一种相当简单的方式编写 Fibonacci 函数：

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);

（游乐场）

Rust 中也有 const 泛型，但它们不稳定（并且仍然有问题）。有可能你可以做一些类似于 C++ 模板元编程版本的事情，但我没有研究它。