Overflow in 64bit integers
Back to General discussions forum
Hey! How are you? I'm having some trouble understanding why is this overflowing, as the numbers in this specific task should fit in 64 bit integers. Also, I've tried to use unsigned and signed int, but it does not seems to be the problem. If it's indeed overflowing, how can I make a work around?
#include <stdio.h>
unsigned long long factorial(unsigned long long);
int main () {
int num;
scanf("%d", &num);
for(int i = 0; i < num; i++) {
unsigned long long N = 12ULL, K = 12ULL;
scanf("%llu %llu", &N, &K);
unsigned long long nFactorial = factorial(N);
unsigned long long kFactorial = factorial(K);
if(kFactorial != 0 && nFactorial != 0 && N - K > 0) {
unsigned long long ans = (nFactorial) / (kFactorial * (factorial(N - K)));
printf("%llu ", ans);
}
}
}
unsigned long long factorial(unsigned long long n) {
unsigned long long f = 1ULL;
while(n > 0)
f *= n--;
return f;
}
Thanks so much for the help!
Victor, Hi!
Which problem it is about? I guess something about combinations?
Well, it's good you have stuck upon this (you won't in Python, for example, which has endless numbers) - it's valuable to learn that int has limits and factorial grows fast :)))
If it's indeed overflowing, how can I make a work around?
You can easily check it is "indeed overflow" by printing out intermediate values.
As about "work around" - there are multiple ways:
- "stupid way" - either find library or implement "from scratch" long arithmetics, or use language which support it out of the box (e.g. Python, or Java)
- "clever way" - spent 5 minutes calculating combinations manually for smaller numbers and figure out that you really need not calculate full factorials! (I guess this also could be found by googling)
Sorry for not giving out the solution - but you probably would be glad to find it yourself :) Feel free to ask for further hints if necessary!
Hey, Rodion! Thanks for the tip! The problem is 128
Like, I was trying to make this: When we have 5!, then it should be equal to 5*4!, and so on. But in the end, a variable will always have to hold the last value, that is very huge. Or am I thinking wrong? Thanks so much for your time!
When we have 5!, then it should be equal to 5*4!, and so on
well, I know what is factorial and how it is usually calculated :)
but you NEED NOT full factorials
Regard this formula:
(nFactorial) / (kFactorial * (factorial(N - K)))
For example, observe that N! / K! is N * (N-1) * ... * (K+1), which is much less than N!...
well, I know what is factorial and how it is usually calculated :)
Ohh, sorry for not being clear. I was talking about how I was thinking trying to solve the problem.
Now I understand! Thanks, Rodion!
N! / K! is N * (N-1) * ... * (K+1)
Victor, do not use this formula if you are a C/C++ developer. Instead use:
#include <boost/math/special_functions/binomial.hpp>
And that boost library contains not only math namespace and not only functions to handle binomial coefficients, but tons of other useful namespaces and functions, so it would be great if you learn more about it.
Sure, I'll look at it! But why I shouldn't use the formula?
Thanks for the advice, qwerty!
Sorry for not being clear. This formula is good, and you can use this formula to check if function from boost library gives correct results. Just... do not use formula to invent your own wheel. Always try first to find a library solution, and only if you cannot find one, make your own implementation.
You search for a programming job, am I right? Well, when you get employed as programmer, you find yourself that you are not allowed to write a line of code yourself - instead you will work with a lot of libraries and your job will be to find the functions needed for task, and to plug them together.
Plus, of course, to fix the bugs in these functions if needed, and this is the only moment when you are allowed to write code.