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 × 10157 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 `1038`

• 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 `109 + 7 or 1000000007` is used because It is 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 Case    if number<=1 {        return 1;    }
// Recursive Case    return (number * factorial_recursive(number-1, divisor) ) % divisor;}```

Program with Driver Code

```use std::io::stdin;
fn factorial_recursive(number : i128, divisor: i128) -> i128{
// Base Case    if number<=1 {        return 1;    }
// Recursive Case    return (number * factorial_recursive(number-1, divisor) ) % divisor;}
// Driver Code
pub fn main() {
// Read and parse number to i128    let 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 factorial    let 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 i128    let mut factorial : i128 = 1;
// Multiply factorial by all numbers from 1 to the given number    for i in 1..(number+1) {        factorial*=i;        // Find remainder        factorial%=divisor;    }
// Return factorial    return 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