I am trying to calculate a massive number which unsigned long long can't hold. To calculate the number, I need to multiply a bunch of numbers and divide them by another bunch of numbers. The thing is, the numerator and denominator themselves also can't be held by unsigned long long. To handle this, I wrote some code to cancel out factors from both the numerator and denominator. This problem that I'm trying to solve is part of larger coding problem that I'm trying to solve. My program to solve that coding problem works for small test cases, but fails for large test cases. I've deduced that the issue probably lies within my algorithm canceling out the factors. I'm unable to use the debugger for large test cases because I'm trying to calculate thousands of different large numbers, and I'm not sure where my algorithm fails in canceling out the factors of the numbers.

The number I'm trying to calculate looks like n!/(a! * b! * ... * x!), where a b ... x=n. I used std::map to store the numerator. Each key in the map refers to the unique number that occurs in the numerator and the key points to the number of times it occurs. For example, if I had 3! in the numerator, I would have

1->1
2->1
3->1

In the denominator, I have a multiset of the different factors. For example, if the denominator was 2! * 1!, it would look like

1, 1, 2

To cancel out the numbers from the numerator and denominator, I start from the greatest number in the denominator and search for the greatest number in the numerator that can divide it. Using the above two examples, I would start from 2 in the denominator and cancel out the 2 in the numerator. I keep repeating this process until I finish canceling out everything in the denominator.

Here's my code

for (auto l = denominatorMultipliers2.rbegin(); l != denominatorMultipliers2.rend();   l) { //denominatorMultipliers2 holds the factors in the denominator
    auto m = numeratorMultipliers.rbegin(); //search for the greatest number in the numerator that can divide the factor in the denominator
    while (m->first % *l!= 0) {
          m;
    }
    --m->second; //once we find the factor in the numerator, we subtract the number of times it occurs by one
      numeratorMultipliers[m->first / *l]; //sometimes, dividing a factor by another factor yields another number in the numerator, e.g. 4/2->2, so there's going to be another 2 in the numerator. numeratorMultipliers is the std::map that holds the factors in the numerator
    if (m->second == 0) { //if the factor in the numerator occurs 0 times, we delete it from the container
        numeratorMultipliers.erase(std::next(m).base());
    }
}

After canceling out the factors, all that I'm left with is the factors of the numerator. A property of this number that I'm calculating is that all the factors in the denominator will cancel out with the factors in the numerator.
Does anyone see what is wrong with my algorithm?

CodePudding user response：

My guess is for test cases with large values, your algorithm fails because it can't cancel out all the values in the denominator?

That is expected, because all the numbers that you are tracking are not prime. To fully cancel out the denominator against the numerator, you'd need to cancel them partially (i.e., cancel their common factors).

One way to solve this is like this:

1. Run your algorithm until it cannot proceed (i.e., some values in both numerator and denominator cannot be cancelled)
2. Pick a remaining number in denominator, perform Euclid algorithm with each of the remaining numbers in numerator, and cancel out their GCD.
3. Repeat above until all numbers in denominator are cancelled out.

NOTE: I'd advice against direct factorization because for large numbers the complexity may be high. You don't really care about factorizing the numerator numbers (which is the expensive part), but just to find out their GCD with the denominator numbers.