1
\$\begingroup\$

This is my first rust program. I don't mind this being a strict review.

What I want Reviewed?

  • Idiomatic code.
  • Performance improvements.
  • Clean code!

Program Requirements:

  • Input a unsigned integer and calculate it's factorial.
  • If q is given as input exit application.

Implementation

  • Use a big unsigned int implementation with *=, clone and += implementations. I didn't implement all operators as it is not necessary for factorial.
  • Formatting: rustfmt
  • Lint: clippy - returns false positives regarding %, / etc used in operator traits, no other issue was reported.

Manual Testing Code

I've used below python code to verify my application. It works & there are no compilation errors.

from math import factorial

print(factorial(50))

output:

30414093201713378043612608166064768844377641568960512000000000000

Program Run Output

Enter n to calculate n!, enter q to exit
n = 0
0! = 1
n = 1
1! = 1
n = 2
2! = 2
n = 3
3! = 6
n = 50
50! = 30414093201713378043612608166064768844377641568960512000000000000
n = -1
Invalid input: -1
n = a
Invalid input: a
n = q
Program end.

Code (main.rs)

use std::cmp;
use std::collections::VecDeque;
use std::fmt;
use std::io;
use std::io::prelude::*;
use std::ops;

const BASE: u8 = 10;

#[derive(Debug, Clone)]
struct BigUInt {
    numbers: VecDeque<u8>,
}

impl BigUInt {
    fn _carry_mul(&mut self, digit: u8) {
        let mut temp: u8;
        let mut mul: u8;
        let mut carry: u8 = 0;
        // multiply all numbers
        for i in 0..self.numbers.len() {
            temp = carry + (self.numbers[i] * digit);
            if temp >= BASE {
                mul = temp % BASE;
                carry = temp / BASE;
            } else {
                mul = temp;
                carry = 0;
            }
            self.numbers[i] = mul;
        }

        // process remaining carry
        while carry > 0 {
            temp = carry % BASE;
            self.numbers.push_back(temp);
            carry /= BASE;
        }
    }

    fn _carry_add(&mut self, digit: u8) {
        let mut temp: u8;
        let mut mul: u8;
        let mut carry: u8 = 0;
        // add all numbers
        for i in 0..self.numbers.len() {
            temp = carry + (self.numbers[i] + digit);
            if temp >= BASE {
                mul = temp % BASE;
                carry = temp / BASE;
            } else {
                mul = temp;
                carry = 0;
            }
            self.numbers[i] = mul;
        }

        // process remaining carry
        while carry > 0 {
            temp = carry % BASE;
            self.numbers.push_back(temp);
            carry /= BASE;
        }
    }
}

impl fmt::Display for BigUInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for num in self.numbers.iter().rev() {
            write!(f, "{}", num)?;
        }
        write!(f, "")
    }
}

impl ops::AddAssign<BigUInt> for BigUInt {
    fn add_assign(&mut self, rhs: BigUInt) {
        if rhs.numbers.len() == 1 && rhs.numbers[0] == 0 {
            // do nothing when adding a zero
        } else if rhs.numbers.len() == 1 && rhs.numbers[0] < BASE {
            self._carry_add(rhs.numbers[0]);
        } else {
            let l_count = self.numbers.len();
            let r_count = rhs.numbers.len();
            let count = cmp::min(l_count, r_count);
            let mut carry: u8 = 0;
            let mut temp: u8;

            for i in 0..count {
                temp = carry + self.numbers[i] + rhs.numbers[i];
                self.numbers[i] = temp % BASE;
                carry = temp / BASE;
            }

            if count == l_count {
                // smaller lhs
                for i in count..r_count {
                    temp = carry + rhs.numbers[i];
                    self.numbers.push_back(temp % BASE);
                    carry = temp / BASE;
                }
            } else if count == r_count {
                // smaller rhs
                for i in count..l_count {
                    temp = carry + self.numbers[i];
                    self.numbers[i] = temp % BASE;
                    carry = temp / BASE;
                }
            }

            while carry > 0 {
                temp = carry % BASE;
                self.numbers.push_back(temp);
                carry /= BASE;
            }
        }
    }
}

impl ops::MulAssign<BigUInt> for BigUInt {
    fn mul_assign(&mut self, rhs: BigUInt) {
        if rhs.numbers.len() == 1 && rhs.numbers[0] == 0 {
            self.numbers.clear();
            self.numbers.push_back(0);
        } else if rhs.numbers.len() == 1 && rhs.numbers[0] == 1 {
            // nothing to do
        } else {
            let mut level: BigUInt = self.clone();
            self.numbers.clear();
            self.numbers.push_back(0);
            let mut cur: BigUInt;

            // do first multiplication
            for mul in &rhs.numbers {
                cur = level.clone();
                cur._carry_mul(*mul);

                *self += cur;

                level.numbers.push_front(0);
            }
        }
    }
}

fn new_big_u_int(n: u128) -> BigUInt {
    let mut x = BigUInt {
        numbers: VecDeque::new(),
    };
    let mut temp = n;
    let base = u128::from(BASE);
    while temp > 0 {
        x.numbers.push_back((temp % base) as u8);
        temp /= base;
    }
    x
}

fn factorial(n: u128) -> BigUInt {
    let mut current = new_big_u_int(1);
    for i in 2..=n {
        current *= new_big_u_int(i);
    }
    current
}

fn main() {
    let mut input_text;
    println!("Enter n to calculate n!, enter q to exit");
    loop {
        print!("n = ");
        io::stdout().flush().unwrap();

        input_text = String::new();
        io::stdin()
            .read_line(&mut input_text)
            .expect("failed to read input");

        let trimmed = input_text.trim();

        if trimmed == "q" {
            println!("Program end.");
            break;
        }

        match trimmed.parse::<u128>() {
            Ok(n) => println!("{}! = {}", n, factorial(n)),
            Err(..) => println!("Invalid input: {}", trimmed),
        };
    }
}
\$\endgroup\$
1
\$\begingroup\$

I didn't look if your code was correct, I just look the style:

  • use iterator instead of index access
  • replace write!(f, "") by Ok(())
  • remove most of type : u8 and let the compiler infer the type
  • remove a lot of unnecessary let mut, example let mut temp
  • Add a DecIter that deconstruct a number (need num to be generic)
  • Use zip_longest() from itertools to improve add_assign()
  • Need to add every operation std::ops::Add and std::ops::Mul for example, (that could improve mul_assign() and factorial())
use std::collections::VecDeque;
use std::fmt;
use std::ops;

#[derive(Debug, Clone)]
struct BigUInt {
    numbers: VecDeque<u8>,
}

impl fmt::Display for BigUInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for num in self.numbers.iter().rev() {
            write!(f, "{}", num)?;
        }
        Ok(())
    }
}

struct DecIter<T> {
    n: T,
    base: T,
}

impl<T> Iterator for DecIter<T>
where
    T: Copy,
    T: num::Zero,
    T: ops::Rem<Output = T>,
    T: ops::Div<Output = T>,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if !self.n.is_zero() {
            let next = self.n % self.base;
            self.n = self.n / self.base;
            Some(next)
        } else {
            None
        }
    }
}

trait Dec<T> {
    fn dec(self, base: T) -> DecIter<T>;
}

impl<T> Dec<T> for T {
    fn dec(self, base: T) -> DecIter<T> {
        DecIter { n: self, base }
    }
}

impl BigUInt {
    const BASE: u8 = 10;

    fn carry_mul(&mut self, digit: u8) {
        // multiply all numbers
        let carry = self.numbers.iter_mut().fold(0, |carry, n| {
            let temp = carry + (*n * digit);
            let (carry, next) = if temp >= Self::BASE {
                (temp / Self::BASE, temp % Self::BASE)
            } else {
                (0, temp)
            };
            *n = next;
            carry
        });

        // process remaining carry
        self.numbers.extend(carry.dec(Self::BASE))
    }

    fn carry_add(&mut self, digit: u8) {
        // add all numbers
        let carry = self.numbers.iter_mut().fold(0, |carry, n| {
            let temp = carry + (*n + digit);
            let (carry, next) = if temp >= Self::BASE {
                (temp / Self::BASE, temp % Self::BASE)
            } else {
                (0, temp)
            };
            *n = next;
            carry
        });

        // process remaining carry
        self.numbers.extend(carry.dec(Self::BASE))
    }
}

use itertools::EitherOrBoth::{Both, Left, Right};
use itertools::Itertools;

impl ops::AddAssign<BigUInt> for BigUInt {
    fn add_assign(&mut self, rhs: BigUInt) {
        if rhs.numbers.len() == 1 && rhs.numbers[0] == 0 {
            // do nothing when adding a zero
        } else if rhs.numbers.len() == 1 && rhs.numbers[0] < Self::BASE {
            self.carry_add(rhs.numbers[0]);
        } else {
            self.numbers.resize(rhs.numbers.len(), 0);
            let carry =
                self.numbers
                    .iter_mut()
                    .zip_longest(&rhs.numbers)
                    .fold(0, |carry, i| match i {
                        Both(lhs, rhs) => {
                            let temp = carry + *lhs + rhs;
                            *lhs = temp % Self::BASE;
                            temp / Self::BASE
                        }
                        Left(lhs) => {
                            let temp = carry + *lhs;
                            *lhs = temp % Self::BASE;
                            temp / Self::BASE
                        }
                        Right(_) => unreachable!(),
                    });

            self.numbers.extend(carry.dec(Self::BASE))
        }
    }
}

impl ops::MulAssign<BigUInt> for BigUInt {
    fn mul_assign(&mut self, rhs: BigUInt) {
        if rhs.numbers.len() == 1 && rhs.numbers[0] == 0 {
            self.numbers.clear();
            self.numbers.push_back(0);
        } else if rhs.numbers.len() == 1 && rhs.numbers[0] == 1 {
            // nothing to do
        } else {
            let mut level = self.clone();
            self.numbers.clear();
            self.numbers.push_back(0);

            // do first multiplication
            for mul in &rhs.numbers {
                let mut cur = level.clone();
                cur.carry_mul(*mul);

                *self += cur;

                level.numbers.push_front(0);
            }
        }
    }
}

fn new_big_u_int(n: u128) -> BigUInt {
    BigUInt {
        numbers: n.dec(u128::from(BigUInt::BASE)).map(|x| x as u8).collect(),
    }
}

fn factorial(n: u128) -> BigUInt {
    (2..=n)
        .map(new_big_u_int)
        .fold(new_big_u_int(1), |mut acc, n| {
            acc *= n;
            acc
        })
}

fn main() {
    assert_eq!(
        "30414093201713378043612608166064768844377641568960512000000000000",
        format!("{}", factorial(50))
    );
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.