large n for factorials

Question

I am trying to solve a very simple task about finding nCk when 1<=n,k<=50. I can't seem to find a way of outputting the result for very large numbers like 50 in C++. My algorithm only works for small integer values.

I implemented a factorial function for the nCk formula, but I can't find a way to solve such task for bigger number, and in 1s.

#include <iostream>
using namespace std;
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int i, n, k;
    long long res, num, den;
    res = num = den = 1;
    cin >> n >> k;
    if (n < k) {
        cout << 0;
        return 0;
    }
    if (n == k || k == 0) {
        cout << 1;
        return 0;
    }
    for (i = 1; i <= k; i++) {
        if ((n - i + 1) % i == 0) {
            res = res * ((n - i + 1) / i);
        }
        else {
            num *= (n - i + 1);
            den *= i;
        }   
    }
    cout << (res*num)/den;
    return 0;
}

That's a very wacky way of writing `std::ifstream ifs{"input.txt"}; ifs >> n >> k;` ... Don't `freopen` standard streams without a good reason. — L. F., Sep 21 '19 at 13:56
You need to either use arrays/vectors in a clever manner to hold each digit and then output it like that, or in my opinion the better way is to use something like [Boost](https://www.boost.org/doc/libs/1_71_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html) — Rietty, Sep 21 '19 at 13:59
Unless the I/O is your main problem, you could presumably just provide a `main` calling `factorial(50)`, and tell us what the actual problem is. Is the result wrong? What _is_ it, and what should it be instead? Or does it crash? What did you try to debug it? — Useless, Sep 21 '19 at 14:00
You do understand that `50!` is too big to be stored in any `long long`, so you will have to figure out some other way to solve your problem. You cannot do it this way, in C++. — Sam Varshavchik, Sep 21 '19 at 14:00
I am voting to reopen this question because it is asking about binomial coefficients (nCk) instead of factorials. The two are related, but not exactly the same. — L. F., Sep 21 '19 at 14:10
I have updated the code, it still doesn't capture for me 50C25, help! — v_head, Sep 21 '19 at 18:40
Why am I being banned asking questions! Please help vote positively! — v_head, Sep 22 '19 at 14:14

score 1 · Answer 1 · answered Sep 21 '19 at 14:01

1

This solution requires some mathematics rather than programming (to solve the problem of overflow).

You have:

n! / (k! * (n - k)!)

You can eliminate common factors easily enough by expanding it. For example:

n = 8, k = 3

8*7*6*5*4*3*2*1 / ((3*2*1) * (5*4*3*2*1))

which expands to

8*7*6*5*4*3*2*1 / 3*2*1*5*4*3*2*1

notice how we can remove 5*4*3*2*1 from both by the rules of division? We then get

8*7*6 / 3*2*1

This will be a lot easier to calculate.

Eventually if you keep getting bigger you will run into issues anyways, so you may need to look into Boost's Multiprecision

answered Sep 21 '19 at 14:01

Water

3,245
3
28
58

Ok, do you think this will work for n=50 without resorting to Boost? – v_head Sep 21 '19 at 14:29
@Papa why not check the Factorial series list? 50! ≈ 3.041409320×10⁶⁴ which far exceeds the maximum `uint64_t` value and even an unsigned 128-bit type if your compiler supports (max ~3.40×10³⁸) – phuclv Sep 21 '19 at 14:36
@Papa Depends on what value of `k` you choose. – Water Sep 21 '19 at 14:39
@phuclv simply our task is to solve it using loop and the only info provided is 1s constraint and the binomial formula. – v_head Sep 21 '19 at 14:39
@Water generally 1<= k <= 50 – v_head Sep 21 '19 at 14:42
@Papa If `k = n/2` (in this case 25) you are probably in trouble. There is another way if you are trying to do this without a library. The idea is to decompose each number into its primes, then track the sum of each prime in the numerator and denominator and then do something similar to my answer. Since the worst case I believe is 50 choose 25 in terms of size, this appears to fit inside a `long` 64-bit type. This means theoretically you should be able to do this method and never overflow (and thus avoid the library). Then again, maybe what I wrote in the answer will work and you can ignore ^. – Water Sep 21 '19 at 14:59
@Water look at L.F said below, he says it's possible without prime method. – v_head Sep 21 '19 at 15:07
@Papa Where exactly does the user mention the prime method? The post (nor the comments) at the time of writing has that. Their post is about using a binomial optimization and then sharing the same info that I've told you as well. – Water Sep 21 '19 at 15:14
@Water I see, sorry! – v_head Sep 21 '19 at 15:15
@Papa It's okay, no need to apologize :) – Water Sep 21 '19 at 15:17
Updated code, with 50C25 not working. – v_head Sep 21 '19 at 18:41

score 0 · Answer 2 · answered Sep 21 '19 at 14:01

0

Your current formula is

binom(n, k) = n! / (n - k)!k!

This formula is OK for mathematics, but not OK for computing. Simplify it:

binom(n, k) = n(n - 1)(n - 2) ... (n - k + 1) / k!

which involves fewer terms. Also note that

binom(n, k) = binom(n, n - k)

which can be used as an optimization if k > n / 2.

Also, if the numbers are too large, you need to use a multi-precision library like GMP.

answered Sep 21 '19 at 14:01

L. F.

19,445
8
48
82

Ok, do you think this will work for n=50 without resorting to GMP? – v_head Sep 21 '19 at 14:29
1

@Papa binom(50, 25) < 2^47. The numerator and denominator are both > 2^83, though. It will work if you carry out the divisions at the right time. Not if you multiply everything together and then divide. – L. F. Sep 21 '19 at 14:38
is the algorithm good above? Or how should I do divisions in the right time, since there is a case of C(6,4), it s (4/4)(5/3)(6/2)(7/1), if you can see it s hard to do division at i time, sometimes the fraction is not divisible. – v_head Sep 21 '19 at 20:22
@Papa Yeah, it's hard to spread out the divisions. The best I can think of is to keep track of an array of divisors and try ... And swap a later divisor when you remove one to make it O(1). – L. F. Sep 22 '19 at 00:51
I ve done an update to do instant division with a simple trick. Still not working. It's in O(k). Can you suggest something. The trick is not comprehensive, but heuristically it's doing some job. It is also required by the program description to use only loops without resorting to arrays. – v_head Sep 22 '19 at 08:27

large n for factorials

2 Answers2