Rust compact matrix Fibonacci

main.rs

use num_bigint::BigUint;
use num_traits::One;
use num_traits::Zero;

use core::ops::{Mul, MulAssign};

#[derive(Debug, Clone)]
struct FLM {
    step: BigUint,
    ident: BigUint,
}

impl FLM {
    fn sum(&self) -> BigUint {
        return self.step.clone() + self.ident.clone();
    }

    fn pow(&mut self, mut idx: u32) {
        let mut base = self.clone();
        while idx > 0 {
            if idx % 2 == 1 {
                *self *= &base;
            }
            idx /= 2;
            base = base.clone() * base;
        }
    }
}

impl MulAssign<&FLM> for FLM {
    fn mul_assign(&mut self, other: &Self) {
        let s2 = &self.step * &other.step;
        let sum = self.sum();
        self.ident *= &other.ident;
        self.step = sum * other.sum() - &self.ident;
        self.ident += s2;
    }
}

impl Mul for FLM {
    type Output = Self;
    fn mul(self, other: Self) -> Self {
        let s2 = &self.step * &other.step;
        let mut ident = &self.ident * &other.ident;
        let step = self.sum() * other.sum() - &ident;
        ident += s2;
        FLM { step, ident }
    }
}

fn fib(n: u32) -> BigUint {
    let mut step = FLM {
        step: BigUint::one(),
        ident: BigUint::zero(),
    };
    step.pow(n);
    return step.step;
}

fn main() {
    fib(9 << 20);
}