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¹⁵⁷ 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

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

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