Schreiben einer effizienten Power-Funktion in Rust

Question

Ich schreibe eine effiziente Quadrierung Methode in Rust. Nehmen wir an, dass die Mul Eigenschaft von AbstractNumber eine Blackbox ist und dass wir nur sichere, idiomatische Rust erlauben.

Unten ist ein erster Durchgang, der wiederholte Quadrierung für größere Indizes verwendet. Ich bin mir nicht sicher, wie LLVM Rust arithmetische Methodenaufrufe wie checked_next_power_of_two() übersetzen wird.

Sieht das Folgende vernünftig aus? Wäre es effizienter, den kleineren Zweig in seine eigene Inline-Funktion zu zerlegen?

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

Warum nicht num::pow::pow verwenden? In jedem Fall ist hier, wie es umgesetzt wird:

#[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 
} 

Es erfordert Clone neben Mul (und One, aber das ist nicht nötig, wenn Sie nicht generisch zu sein).

Es gibt übrigens nichts Falsches oder Unsicheres über bitweise Operationen in Rust.