Recently, I have a question about factorial. The question is to find the division result of 2 factorials of 2 huge numbers. For example, given a=400000000
and b=30000000
, find the result of fact(a) / fact(b)
. Since the result will be enormous, it will be modulo by some int32 value like 499555666.
I am not good at math. I know that fact(400000000)
is impossible huge number.
My question is...
- Is there an algorithm that can find the result?
- Can you give me some hints and guides?
CodePudding user response:
It's possible to find it without writing an algorithm. This is a mathematics problem which you can solve with just a little bit of help from a computer.
What you want to find is a product of a huge range of consecutive numbers, i.e. 30,000,001 to 400,000,000 inclusive, but you want the result modulo N = 499,555,666.
The most obvious thing to note is that N is not in the range of numbers you are multiplying; if it were, then the product would obviously have a factor of N, and therefore it would equal 0 modulo N.
However, N is clearly not prime, so N doesn't have to be in the range for the product to end up having a factor of N. Using a calculator, we get that the prime factorisation is N = 2 × 2,609 × 95,737.
The range from A to B is wide enough that it definitely includes a multiple of 2, a multiple of 2,609 and a multiple of 95,737. So the product will have all three of those factors, and therefore the result will be 0 modulo N.
The only part that needed the computer's help was finding the prime factorisation; the rest is in your head. Actually, we could have done this without even a calculator, by noticing that N has a factor of 2 (because its last digit is 6), and that N/2 is within the range.
CodePudding user response:
Is there an algorithm that can find the result?
Let's start with the definition of a factorial:
n! = 1 x 2 x 3 x ... x (n-1) x n
Now, let a
and b
be two positive integers such that a
> b
. We can write a!
/ b!
as:
a! 1 x 2 x ... x b x (b 1) x ... x a
-- = ---------------------------------
b! 1 x 2 x ... x b
Now, we can simplify the fraction by dividing the numerator and the denominator by 1 x 2 x ... b
, i.e. by b!
:
a!
-- = (b 1) x (b 2) x ... x a
b!
Notice that there are a - b
terms.
Back to your case, you have to calculate 30000001 x 30000002 x ... x 400000000
(370,000,000 terms, that's 370 million operations minus 1). This is a very huge number.
EDIT:
As Mitch Wheat suggested in a comment, you can use this formula
(a1 x a2 x ... x ap) % n = [(a1 % n) x (a2 % n) x ... x (ap % n)] % n
to express the result using modulo n
.