# Modular Factorial

of a number and Program to find modular factorial using Modular Arithmetic in Rust.

## Why do we need Modulo

The program discussed in Finding Factorial Of a Number page finds the factorial of a given number. But factorial of number grows very fast with number. **Factorial of 100 is 9.33 × 10 ^{157}**
So, it becomes impossible to store such large number as number in many languages, like

**C, C++, Rust**etc. ( Though some languages like Python allow number of any length being stored ).

- Largest integer data type in rust is
`i128`

which can store only the numbers of 128 bits which is roughly of order`10`

^{38}

- If we try to store a number beyond this range,
**the number will overflow, and an error will be thrown!.**Like, if we try to find 100!

thread 'main' panicked at 'attempt to multiply with overflow', src/iterative.rs:10:9

Therefore, we must find an alternate to store and use the factorial of larger numbers.

## Using Modulo of Number to store

As we saw above, we can not store the complete number. But we can store it's modulo from a number.

In most programming contest, a specific number is mentioned, generally ** 10** is used because It is

^{9}+ 7 or 1000000007

*safe prime number*.

But we will see a function that generates factorial of a number modulo any other number. Also, it is guaranteed that number will be less than the second number. That is, if we find factorial modulo 13, it is guaranteed that the answer will be less than 13. Hence, it will ensure that the number doesn't overflow.

### Property Used

We take the help of special property in Modular Mathematics, which is called Modular Multiplication Property

**(a x b) mod m = ((a mod m) x (b mod m)) mod m**

Also, we know that **n! = n × (n-1)!**. Therefore,
**n! mod m = ((n mod m) x ((n-1)! mod m)) mod m**

Also, `n mod m = n`

because if n is greater or equal to m, final result will be 0, because n! will already contain m, and hence, it is always divisible by m.

If n is less than m, than n mod m = n always.

Also, (n-1)! is already modulo m. So, no need to find modulo m again.So, finally, we use equation

**n! mod m = ( n x (n-1)! ) mod m**

## Recursive Approach

In the code seen in Finding Factorial of a Number page, we just **return number modulo divisor**

fn factorial_recursive(number : i128, divisor: i128) -> i128{// Base Caseif number<=1 {return 1;}// Recursive Casereturn (number * factorial_recursive(number-1, divisor) ) % divisor;}

Program with Driver Code

use std::io::stdin;fn factorial_recursive(number : i128, divisor: i128) -> i128{// Base Caseif number<=1 {return 1;}// Recursive Casereturn (number * factorial_recursive(number-1, divisor) ) % divisor;}// Driver Codepub fn main() {// Read and parse number to i128let mut input = String::new();stdin().read_line(&mut input).unwrap();let number : i128 = input.trim().parse().unwrap();input.clear();stdin().read_line(&mut input).unwrap();let divisor : i128 = input.trim().parse().unwrap();// Find and print factoriallet factorial = factorial_recursive(number, divisor);println!("Factorial of {} is : {}", number, factorial);}

**Output**

12345

1000000007

Factorial of 12345 is : 579592771

**Time Complexity : O(n)**

**Space Complexity : O(n)**

As you can see, we can easily find factorial of number as large as `12345`

modulo some other number easily.

## Iterative Approach

In this, we multiply all the number from 1 to the given number, and each time store the remainder.

fn factorial(number : i128, divisor: i128) -> i128{// initialize factorial to 1, explicitly type i128let mut factorial : i128 = 1;// Multiply factorial by all numbers from 1 to the given numberfor i in 1..(number+1) {factorial*=i;// Find remainderfactorial%=divisor;}// Return factorialreturn factorial}

**Output**

12345

1000000007

Factorial of 12345 is : 579592771

**Time Complexity : O(n)**

**Space Complexity : O(1)**

**Note :** Iterative approach is more efficient than recursive approach !

## Conclusion

This article covered how to find factorial of very large numbers, using both Iterative and recursive methods in rust.

Here is function for easy access

fn factorial(number : i128, divisor: i128) -> i128{let mut factorial : i128 = 1;for i in 1..(number+1) {factorial*=i;factorial%=divisor;}return factorial}

In the next article, we will see how to find the factorial of multiple numbers.

**Thank You**