2

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?

Ranoiaetep
  • 5,872
  • 1
  • 14
  • 39
ben chen
  • 25
  • 4
  • `and I'm not sure where my algorithm fails in canceling out the factors of the numbers.` - you could add a test after canceling, that adding that factor back results in the original number. When the test fails, log it, set breakpoint, etc. and you have the test number you need to work backwards to find the cause. If one of the steps for "13" triggers a failure, you know to break when you are about to start working with "13". – Dave S Feb 02 '23 at 19:12
  • 1
    i dont see the issue in your algorithm, but it looks too complicated. You need a single `std::map n` to model the number. For each numerator in the form `a!` you increment all `n[x]` where `x<=a` by 1. For each denominator in the form `b!` you decrement all `n[x]` where `x <= b` by 1. – 463035818_is_not_an_ai Feb 02 '23 at 19:13
  • though for a canonical representation you would factorize the numbers to have only prime factors as keys in the map – 463035818_is_not_an_ai Feb 02 '23 at 19:14
  • 1
    I second Dave S. "My program is too complicated" is no excuse for not testing and not using a debugger. The more complex your program gets the more important is testing and using a debugger – 463035818_is_not_an_ai Feb 02 '23 at 19:16
  • 4
    Back when I was working on autopilots the complexity was such that I would have loved to just declare that the code was too complicated for testing and go for a rootbeer. Sadly the management didn't share my belief that doing so would help mankind with its overpopulation problem. Personally, I just think they were OK with deaths, but not with the possibility of getting sued. – user4581301 Feb 02 '23 at 19:23
  • @DaveS but how would I check if adding the factor back results in the original number if I can't even calculate the original number in the first place? Like if I was trying to calculate 28!/28!, my program would cancel out the 28s in both the numerator and denominator. But if I want to check that 27!/27! is the same as 28!/28!, I can't because c++ can't calculate numbers as big as 27! without integer overflow – ben chen Feb 02 '23 at 19:54
  • Does this answer your question? [Calculate multinomial coefficient](https://stackoverflow.com/questions/22892138/calculate-multinomial-coefficient) – Raymond Chen Feb 02 '23 at 20:07
  • @RaymondChen well even after I cancel out the denominator (or in your case alternate between multiplication and division), I can get a number larger than what unsigned long long can hold. The way I handle that is beyond the scope of this question. I simply want the factors that multiply to the number, not the number itself. – ben chen Feb 02 '23 at 20:10
  • @benchen *I am trying to calculate a massive number which unsigned long long can't hold* -- Have you considered using a multiprecision library, as [this answer uses](https://stackoverflow.com/questions/67630357/c-factorial-of-number-100/67630658#67630658)? – PaulMcKenzie Feb 02 '23 at 20:49
  • @PaulMcKenzie no, I'm not trying to use any external libraries – ben chen Feb 02 '23 at 20:55
  • Well, if you value your time -- the library is header only. All you have to do is include the header, and that's it. It is no different than if you got an answer with the entire code of the library in the answer section. – PaulMcKenzie Feb 02 '23 at 20:59

1 Answers1

0

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.

Edy
  • 462
  • 3
  • 9