用 Rust 写一个高效的幂函数

Question

我正在用 Rust 编写一个高效的平方方法。让我们假设 AbstractNumber 的 Mul 特征是一个黑盒子，我们只允许使用安全的、惯用的 Rust。

下面是第一遍，它对较大的索引使用重复平方。我不确定 LLVM 将如何翻译 Rust 算术方法调用，例如 checked_next_power_of_two().

以下看起来合理吗？将 smaller-case 分支拆分成它自己的内联函数会更有效吗？

/// Compute an integer power of this number efficiently with repeated squaring.
pub fn pow(&self, n: u32) -> AbstractNumber {
    let optimization = 5;

    if n < optimization {
        let mut x = Complex::one();

        for _ in 0..n {
            x *= *self;
        }

        x
    } else {
        // l = floor(log_2(n)), r = n - 2^l
        let (l, r) = if n.is_power_of_two() {
            (n.trailing_zeros(), 0)
        } else {
            let p = n.checked_next_power_of_two().unwrap().trailing_zeros() - 1;
            (p, n - 2u32.pow(p))
        };

        let mut x = *self;

        for _ in 0..l {
            x *= x;
        }

        self.pow(r) * x
    }
}

Answer 1

为什么不用num::pow::pow？无论如何，这是它的实现方式：

#[inline]
pub fn pow<T: Clone + One + Mul<T, Output = T>>(mut base: T, mut exp: usize) -> T {
    if exp == 0 { return T::one() }

    while exp & 1 == 0 {
        base = base.clone() * base;
        exp >>= 1;
    }
    if exp == 1 { return base }

    let mut acc = base.clone();
    while exp > 1 {
        exp >>= 1;
        base = base.clone() * base;
        if exp & 1 == 1 {
            acc = acc * base.clone();
        }
    }
    acc
}

它需要 Clone 除了 Mul（和 One，但如果您不是通用的，则不需要）。

顺便说一句，在 Rust 中使用按位运算并没有错或不安全。

用 Rust 写一个高效的幂函数

Writing an efficient power function in Rust

performance

rust

integer-arithmetic