Is it possible to find fact(400000000) / fact(30000000) using an algorithm?-CodePudding

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.