Home > Software engineering >  Is it possible to find fact(400000000) / fact(30000000) using an algorithm?
Is it possible to find fact(400000000) / fact(30000000) using an algorithm?

Time:12-07

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.

  • Related