I have the following code:
// Expensive clone()
#[derive(Clone)]
struct MyStruct {
coeffs: Vec<u64>,
}
impl MyStruct {
fn mul(&self, rhs: &MyStruct) -> MyStruct {
let res = self
.coeffs
.iter()
.zip(rhs.coeffs.iter())
.map(|(l, r)| l.wrapping_mul(*r))
.collect::<Vec<u64>>();
MyStruct { coeffs: res }
}
fn zero() -> MyStruct {
MyStruct { coeffs: vec![] }
}
}
fn powers_of_x(x: &MyStruct) -> Vec<MyStruct> {
let mut powers = vec![MyStruct::zero(); 256];
let mut calculated = vec![0u64; 256];
for i in (2..257).rev() {
let mut exp = i;
let mut base = x;
let mut res = &MyStruct::zero();
let mut base_deg = 1usize;
let mut res_deg = 0usize;
while exp > 0 {
if exp & 1 == 1 {
res_deg += base_deg;
if calculated[res_deg - 1] == 1 {
res = &powers[res_deg - 1];
} else if res_deg == base_deg {
res = base;
} else {
powers[res_deg - 1] = res.mul(base); // error
res = &powers[res_deg - 1];
calculated[res_deg - 1] = 1;
}
}
exp >>= 1;
if exp != 0 {
base_deg *= 2;
if calculated[base_deg - 1] == 0 {
powers[base_deg - 1] = base.mul(base); // error
calculated[base_deg - 1] = 1;
base = &powers[base_deg - 1];
} else {
base = &powers[base_deg - 1];
}
}
}
}
powers
}
Cloning MyStruct is expensive and I want to minimise number of multiplications (ie calling mul on MyStruct).
powers_of_x calculates powers of x from 2 to 256. The basic idea is the function uses binary exponentiation starting from 256 and caches values so that same values aren't calculated again.
However, as you might notice powers_of_x will not work. I am mutating powers array while borrowing it in res and base. I understand that this is illegal but I am not mutating an index in powers while borrowing it. How can I modify the function such that it isn't illegal anymore and does not introduces additional clones()
