# Factorial Calculator with a basic BigUInt

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;
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, "")
}
}

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 {
} 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()

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),
};
}
}


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) {
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;

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 {
} 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))
);
}