Rustで効率的なパワー関数を書く

Question

私はRustに効率的な二乗法を書いています。 の形質がAbstractNumberであることをブラックボックスとし、安全で慣れ親しんだRustのみが許可されているとしましょう。

以下は、より大きなインデックスに対して繰り返し2乗を使用する最初のパスです。私はLLVMがchecked_next_power_of_two()のようなRust算術メソッド呼び出しをどのように変換するのか不明です。

次は妥当なものですか？小文字のブランチを独自のインライン関数に分割する方が効率的でしょうか？

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

それはMulに加えてClone必要です（とOneをしていますが、一般的なされていない場合には不要です）。

ところで、Rustでビット単位の操作を使用することについては何も問題はありません。