Error in nCr code

#include <iostream> using namespace std; int fac(int num) { int factorial = 1; for (int i=2; i<=num; i++) { factorial *= i; } return factorial; } int main() { int n; int r; cout << "We will calculate nCr for you.\n"; cout << "Pls enter the value of n :- "; cin >> n; cout << "Pls enter the value of r :- "; cin >> r; while (n<r || n<0 || r<0) { cout << "FATAL ERROR " << endl; return 0; } int ans = fac(n)/(fac(n-r)*fac(r)); cout << ans << endl; return 0; }

When i wrote this code it is working perfectly for small value of nCr but when i took n as 29 and r as 12 then ans shown was -1 which is clearly wrong and can you pls tell why is it ??

I believe your running into an integer over flow problem. In C and C++ the int type is usually allocated 4 bytes of data to store a number. This gives a limit of -2147483646 to 2147483647

However if we take a look with a calculator, 29! is an incredibly large number in comparison:

29! = 8.841762e+30
*note this is actually an aproximation

Here’s where a road block is hit. The largest type by default in C++ is the unsigned long long int, which is a 64 bit integer of only positive numbers, however this still only gives us the value:

2^64 = 1.8446744e+19

Far too small to contain such a large number. This doesn’t mean it’s impossible to work with large numbers, after all Python can, and Python is written in C++:

import math
print(math.factorial(29))

8841761993739701954543616000000

Here we have a number that is even more exact than our calculators number earlier.


Now we just have to get rather creative.
One way we could do this would be to shift our focus over to pointer arrays, since they can be allocated much more space:

#include <iostream>
#include <stdlib.h>

int main(void) {
  int* a = (int*)malloc(128);
  return 0;
} 

But we still have a lot of logic to work out from there. I don’t have a working example myself right now, but would like to work something out later.
Perhaps bit fiddling would be good, though I’ve never worked on such a large chunk of memory before. Can a 64 bit processor work on something so big, or will it have to be broken down into smaller pieces? Perhaps loops to piece it back together? How do we output? Obviously the traditional casts won’t work. A lot to think about.

I’d recommend doing some googling, I’m sure I’ll have to.

2 Likes

@8-bit-gaming brings up very good points.

Depending on your goals (e.g.: getting better at numerical methods or building your own tools) you may want to look into pre-existing scientific or cryptographic minded library for c++. The GNU MP Bignum Library, this library should be able to give you your large numbers. (for example, here they have charts for calculating pi up to 10^9 digits: GMP Pi computation)

(I’m actually interested in this, I will probably start playing around with it later).

1 Like

thank you very much, this ans gave me insight into it to an extent, the only problem with me is i am still a beginnwer and i have to read a lot on this. Can you pls suggest some resouces whihc can help me in bringing more clarity to the basic concepts ???

At the stage your at it may be best to look more into a prebuilt library like @toastedpitabread recommended. I’ve never been one to use many libraries so I can’t say I have a recommendation. Though there were one or two mentioned above.
If you want to look more into the basics of handling large numbers yourself, you could start here.
Just a quick article I found on using strings to store large numbers.

As for really understanding the basics concepts of the language itself, the majority of that just comes with practice over time.

And to add to what @8-bit-gaming (which was all perfect), try to figure out what you want to be good at: some people make the tools, some people use the tools, some do both (you don’t have to decide now!).

If you want to know how to make accurate maths/science tools, try looking into numerical methods/numerical analysis (Numerical analysis - Wikipedia). And knowledge of C/C++ and maybe even assembly can help a lot here.

If you want to just use the tools, look into libraries in the languages you want to use. C++ will offer better performance, Python is great for when you need to do quick calculations, and R is also great when it comes statistical calculations (there are more, and this is a huge generalization).

For python I highly recommend looking into scipy: https://scipy.org/

1 Like

I used the code given previously to calculate nCr using a different formula.

nCr
= nPr / [ r! ]
= [ n (n-1) (n-2) … (n - r + 1 ) ] / [ r! ]
notice that the numerator has r factors
also, notice that nCr = nCn - r
which is easier to see using the original formula nCr = [ n! ] / [ (n-r)! r! ]

I used much of @divanshugarg06553967’s code, although it runs into some of the same problems (meaning it fails if the numbers get too big).

#include <iostream> using namespace std; long fac(int num) { long factorial = 1; for (int i=2; i<=num; i++) { factorial *= i; } return factorial; } long nPr(int n, int r) { long permutation = 1; for (int i=0; i<r; i++ ) { permutation *= (n-i); } return permutation; } int main() { int n = 29; int r = 12; cout << "We will calculate nCr for you.\n"; //cout << "Pls enter the value of n :- "; cin >> n; //cout << "Pls enter the value of r :- "; cin >> r; if (n<r || n<0 || r<0) { cout << "FATAL ERROR " << endl; return 0; } if (r > (n - r)) { r = n - r; } long ans = nPr(n,r) / fac(r); cout << ans << endl; return 0; }

Although I think that Pascal’s triangle
or the finding combinations using summations of summations algorithms
may be better ways to avoid the numbers getting too big.

(And if you only want an approximate answer, a formula based on the Beta function may work to get a floating point number approximation.)