Расчёт чисел Фибонначи с помощью больших чисел

crates_bigint_fib.rs

// [dependencies]
// num-bigint = "*"
extern crate num_bigint;
// num-traits = "*"
extern crate num_traits;

use num_bigint::BigUint;
use num_traits::{One, Zero};
use std::env;
use std::mem::replace;
use std::process;
use std::time::Instant;

fn fib(n: usize) -> BigUint {
    let mut f0: BigUint = Zero::zero();
    let mut f1: BigUint = One::one();
    for _ in 0..n {
        let f2 = f0 + &f1;
        f0 = replace(&mut f1, f2);
    }
    f0
}

fn main() {
    let args: Vec<String> = env::args().into_iter().collect();
    if args.len() < 2 {
        println!("usage: {} <n>", args[0]);
        process::exit(0);
    }
    let n: usize = match args[1].parse() {
        Ok(value) => value,
        Err(_) => {
            println!("[error] problem with parsing `{}`", args[1]);
            process::exit(0);
        }
    };

    let start = Instant::now();
    let r = fib(n);
    let stop = start.elapsed();

    println!("[{}]: {}", n, r);
    println!("elapsed: {:?}", stop);
}

my_bigint_fib.rs

#![allow(unused_macros)]
use std::env;
use std::fmt;
use std::mem::replace;
use std::ops::Add;
use std::process;
use std::time::Instant;

#[derive(Clone)]
struct BigUInt {
    // не самый лучший вариант представления больших чисел
    digit: Vec<u8>,
}

impl BigUInt {
    fn zero() -> BigUInt {
        BigUInt { digit: vec![0] }
    }

    fn one() -> BigUInt {
        BigUInt { digit: vec![1] }
    }

    fn from_vec<T: Into<Vec<u8>>>(digit: T) -> BigUInt {
        BigUInt {
            digit: digit.into(),
        }
    }

    // функция выравнивания нашего BigUInt
    fn align(&mut self, n: usize) {
        let curr_size = self.digit.len();
        if curr_size < n {
            let mut tmp = vec![0; n - curr_size];
            self.digit.append(&mut tmp);
        }
    }
}

impl fmt::Display for BigUInt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}",
            self.digit
                .iter()
                // числа лежат в обратном порядке
                .rev()
                .map(|&x| (x + 0x30) as char)
                .collect::<String>()
        )
    }
}

impl Add for BigUInt {
    type Output = Self;

    fn add(mut self, mut other: Self) -> Self {
        // выравниваем вектора по большему
        let m_len = self.digit.len().max(other.digit.len());
        self.align(m_len);
        other.align(m_len);

        // оптимизация выделения памяти под результат
        let mut value: Vec<u8> = Vec::with_capacity(m_len + 1);
        // переменная для значения переноса
        let mut carry = 0_u8;

        // складываем значения
        for (a, b) in self.digit.iter().zip(other.digit.iter()) {
            carry += a + b;
            value.push(carry % 10);
            carry /= 10;
        }
        // добавляем значение переноса
        if carry != 0 {
            value.push(carry);
        }

        BigUInt::from_vec(value)
    }
}

// макрос для представления чисел любой длины
// например запишем 12345678901234567890
// let a = big_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
macro_rules! big_vec {
    ($($x:tt)*) => {
        {
            let mut value = vec![$($x)*];
            value.reverse();
            BigUInt::from_vec(value)
        }
    }
}

// надеюсь сам догадаешься что делает функция
fn fib(n: usize) -> BigUInt {
    let mut f0 = BigUInt::zero();
    let mut f1 = BigUInt::one();
    for _ in 0..n {
        let f2 = f0 + f1.clone();
        // спасибо за наводку документации num-bigint
        f0 = replace(&mut f1, f2);
    }
    f0
}

fn main() {
    // не лучший парсинг аргументов
    let args: Vec<String> = env::args().into_iter().collect();
    if args.len() < 2 {
        println!("usage: {} <n>", args[0]);
        process::exit(0);
    }
    let n: usize = match args[1].parse() {
        Ok(value) => value,
        Err(_) => {
            println!("[error] problem with parsing `{}`", args[1]);
            process::exit(0);
        }
    };

    // расчёт с замерами
    let start = Instant::now();
    let r = fib(n);
    let stop = start.elapsed();

    println!("[{}]: {}", n, r);
    println!("elapsed: {:?}", stop);
}

my_biguint_inplace.rs

use std::env;
use std::fmt;
use std::mem::replace;
use std::ops::Add;
use std::process;
use std::time::Instant;

#[derive(Clone)]
struct BigUInt {
    // не самый лучший вариант представления больших чисел
    digit: Vec<u8>,
}

impl BigUInt {
    fn zero() -> BigUInt {
        BigUInt { digit: vec![0] }
    }

    fn one() -> BigUInt {
        BigUInt { digit: vec![1] }
    }

    fn from_vec<T: Into<Vec<u8>>>(digit: T) -> BigUInt {
        BigUInt {
            digit: digit.into(),
        }
    }

    // функция выравнивания нашего BigUInt
    fn align(&mut self, n: usize) {
        let curr_size = self.digit.len();
        if curr_size < n {
            let mut tmp = vec![0; n - curr_size];
            self.digit.append(&mut tmp);
        }
    }
}

impl fmt::Display for BigUInt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}",
            self.digit
                .iter()
                // числа лежат в обратном порядке
                .rev()
                .map(|&x| (x + 0x30) as char)
                .collect::<String>()
        )
    }
}

impl Add for BigUInt {
    type Output = Self;

    // без лишнего выделения памяти
    fn add(mut self, mut other: Self) -> Self {
        // выравниваем вектора по большему
        let m_len = self.digit.len().max(other.digit.len());
        self.align(m_len);
        other.align(m_len);

        // переменная для значения переноса
        let mut carry = 0_u8;

        // складываем значения
        for (a, b) in self.digit.iter_mut().zip(other.digit.iter()) {
            carry += *a + b;
            *a = carry % 10;
            carry /= 10;
        }
        // добавляем значение переноса
        if carry != 0 {
            self.digit.push(carry);
        }

        BigUInt::from_vec(self.digit)
    }
}

// надеюсь сам догадаешься что делает функция
fn fib(n: usize) -> BigUInt {
    let mut f0 = BigUInt::zero();
    let mut f1 = BigUInt::one();
    for _ in 0..n {
        let f2 = f0 + f1.clone();
        // спасибо за наводку документации num-bigint
        f0 = replace(&mut f1, f2);
    }
    f0
}

fn main() {
    // не лучший парсинг аргументов
    let args: Vec<String> = env::args().into_iter().collect();
    if args.len() < 2 {
        println!("usage: {} <n>", args[0]);
        process::exit(0);
    }
    let n: usize = match args[1].parse() {
        Ok(value) => value,
        Err(_) => {
            println!("[error] problem with parsing `{}`", args[1]);
            process::exit(0);
        }
    };

    // расчёт с замерами
    let start = Instant::now();
    let r = fib(n);
    let stop = start.elapsed();

    println!("[{}]: {}", n, r);
    println!("elapsed: {:?}", stop);
}