如何用泛型整数类型实现Rust斐波那契算法？

问题背景 #

现有一段计算第n个斐波那契数的代码，仅支持i64类型，希望改造为支持任意整数类型的泛型实现。使用num crate的Integer trait尝试实现后，出现整数字面量与泛型类型T的运算错误，例如{integer} * T无实现、count - 1类型不匹配等，手动声明let two: T = 2;或显式使用Mul、Div等trait也无法解决，需寻找正确实现方式。

原i64实现代码 #

pub fn fibonacci(n: i64) -> i64 {
   fib_iter(1, 0, 0, 1, n)
}

fn fib_iter(a: i64, b: i64, p: i64, q: i64, count: i64) -> i64 {
   if count == 0 {
      return b;
   }

   if is_even(count) {
      return fib_iter(a, b, p*p + q*q, 2*p*q + q*q, count / 2);
   }

   fib_iter(b*q + a*q + a*p, b*p + a*q, p, q, count - 1)
}

泛型尝试代码 #

pub fn fibonacci<T: Integer>(n: T) -> T {
   fib_iter(1, 0, 0, 1, n)
}

fn fib_iter<T: Integer>(a: T, b: T, p: T, q: T, count: T) -> T {
   if count.is_zero() {
      return b;
   }

   if count.is_even() {
      return fib_iter(a, b, p*p + q*q, 2*p*q + q*q, count / 2);
   }

   fib_iter(b*q + a*q + a*p, b*p + a*q, p, q, count - 1)
}

报错信息 #

66 |       return fib_iter(a, b, p*p + q*q, 2*p*q + q*q, count / 2);
   |                                         ^ no implementation for `{integer} * T`

...

69 |    fib_iter(b*q + a*q + a*p, b*p + a*q, p, q, count - 1)
   |                                                       ^ expected type parameter `T`, found integer

正确实现方式 #

问题核心在于Rust无法自动将整数字面量转换为泛型类型T，必须通过num提供的trait来构造对应类型的数值实例，同时处理所有权问题。

步骤说明 #

1. 引入所需trait：Integer提供整数运算能力，One和Zero用于获取1和0的实例，Clone用于处理类型所有权转移问题（部分整数类型如BigInt需要克隆）。
2. 用T::one()、T::zero()替代字面量1、0，确保类型匹配。
3. 构造数字2时，通过T::one() + T::one()生成T类型的实例。
4. 所有涉及字面量的运算，替换为T类型实例之间的运算（如count - 1改为count - T::one()）。
5. 对需要重复使用的变量调用clone()，避免所有权被转移导致编译错误。

修正后代码 #

use num::{Integer, One, Zero};

pub fn fibonacci<T: Integer + Clone>(n: T) -> T {
    fib_iter(T::one(), T::zero(), T::zero(), T::one(), n)
}

fn fib_iter<T: Integer + Clone>(a: T, b: T, p: T, q: T, count: T) -> T {
    if count.is_zero() {
        return b;
    }

    if count.is_even() {
        // 计算新的p值：p² + q²
        let p_sq = p.clone() * p;
        let q_sq = q.clone() * q;
        let new_p = p_sq + q_sq;

        // 计算新的q值：2pq + q²
        let two = T::one() + T::one();
        let pq = p.clone() * q;
        let new_q = two * pq + q_sq;

        // count除以2，使用T类型的2
        return fib_iter(a, b, new_p, new_q, count / two);
    }

    // 计算新的a值：bq + aq + ap
    let bq = b.clone() * q.clone();
    let aq = a.clone() * q.clone();
    let ap = a.clone() * p.clone();
    let new_a = bq + aq + ap;

    // 计算新的b值：bp + aq
    let bp = b.clone() * p;
    let aq2 = a * q;
    let new_b = bp + aq2;

    // count减1，使用T类型的1
    fib_iter(new_a, new_b, p, q, count - T::one())
}

验证示例 #

可以用不同整数类型测试：

// 测试i32
assert_eq!(fibonacci(10i32), 55);
// 测试u64
assert_eq!(fibonacci(20u64), 6765);
// 测试BigInt
use num::BigInt;
assert_eq!(fibonacci(BigInt::from(30)), BigInt::from(832040));

内容的提问来源于stack exchange，提问作者xormapmap