0

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?
Liu Bei
  • 565
  • 3
  • 9
  • 19
  • 2
    `fact(400000000)` is ***not*** an *"impossible huge number"* if it is modulo int32. I really don't know how to give you hints without just giving you the answer... except to say this is a very quick/easy calculation. About 5 lines of code ought to do it. – Elliott Dec 06 '22 at 11:22
  • `fact(n)` = `fact(n-1) * n`. Does that help? – Zakk Dec 06 '22 at 11:24
  • @Zakk fact(n) = fact(n-1) * n doesn't help because the algorithm should run fast. In python, math. Factorial(400000000) is extremely slow. Do you have some guides to faster algorithm? – Liu Bei Dec 06 '22 at 11:26
  • 1
    @Zakk and obviously, fact(400000000) is beyond 64-bit integer – Liu Bei Dec 06 '22 at 11:27
  • @LiuBei That's not what was intended to do with that "hint"... – Zakk Dec 06 '22 at 11:27
  • 6
    Hint: (A * B) % M == ((A % M) * (B % M)) % M – Mitch Wheat Dec 06 '22 at 11:34

2 Answers2

1

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.

kaya3
  • 47,440
  • 4
  • 68
  • 97
  • 1
    This is an excellent answer, the only problem I see is that the OP states "...by some int32 value **like** 499555666..." whereas your answer makes sense for exactly that number. Suppose the modulus had been instead a nearby prime? – President James K. Polk Dec 06 '22 at 15:57
  • 1
    @PresidentJamesK.Polk That's indeed a limitation of this method, but at least it will work almost all of the time. Most `N >= a - b` are not prime, for `N < a - b` the method works even if N is not prime, and in the former case it will still work if the range happens to contain N. In the case when N has a prime factor which the range contains no multiple of, the result won't be zero, but there's [still more maths you can do](https://en.wikipedia.org/wiki/Wilson's_theorem) before resorting to brute force. I haven't addressed that because it is not clear that a fully general solution is needed. – kaya3 Dec 06 '22 at 16:14
  • btw. you can get the prime factorization easily with this [Fast exact bigint factorial](https://stackoverflow.com/a/18333853/2521214) and just substract the exponents between `400000!` and `300000!` ... but using `modmul` approach in naive `for` loop will be much easier to implement as this task is still in range of "small" input and output the computing time will not be too big ... – Spektre Dec 07 '22 at 07:32
-1

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.

Zakk
  • 1,935
  • 1
  • 6
  • 17
  • You ignored the fact that the result should be modulo some much smaller integer. – CherryDT Dec 06 '22 at 13:36
  • @CherryDT At first, I didn't see that part. But what does the OP mean by saying that the result should be modulo some int32? – Zakk Dec 06 '22 at 13:54
  • `result = (fact(a) / fact(b)) % n` - The `% n` part allows simplifications which make the calculation feasible. – CherryDT Dec 06 '22 at 14:10
  • @CherryDT So the question is to find that `n`, isn't it? – Zakk Dec 06 '22 at 14:11
  • 1
    No, to find a way to calculate the result given `a`, `b` and `n`. That's how I understand the question, at least. (In the question it's 499555666 but I think that's just an example because they say "an int32 _like_".) – CherryDT Dec 06 '22 at 14:11
  • 1
    Well, that's simple to do, using Mitch Wheat's suggestion: `(a * b) % m == [(a % m) * (b % m)] % m`. – Zakk Dec 06 '22 at 14:13