+ 6

[ Solved Temporary ] My recursive function to calculate factorial give negative/zero as output? How can i solve it.

My recursive function to calculate factorial give negative number when I enter 17 ; And for 45 its zero. I searched it on google and got some results about range of bit int(- 2^32 to 2^32). I tried also in long long instead of int but still not get better result. Plz suggest a permanent solution that can applied to all numbers. ¯\_(ツ)_/¯ https://code.sololearn.com/cZxrqFv3saL9/?ref=app https://code.sololearn.com/cK1oYQJuN5BZ/?ref=app

14th Jan 2021, 6:34 PM
Mr. Rahul
Mr. Rahul - avatar
10 Réponses
+ 9
The general outline would be to get the files, make sure to tell your compiler where to find them, and then you can just include the header and implement the algorithm with that class as the integral type for your variables. The link above doesn't make a great impression though, no documentation and quite old as well. Look on GitHub as an alternative. Note none of this will work on SoloLearn, so you'll have to somewhat figure this out on your own. Regarding overflow problems: Since computers are restricted by their memory, it is impossible to implement a factorial that can be applied to all natural numbers. A big integer class would also rely on a (dynamic) buffer, it is just handled internally, but ultimately limited in the same way. You can't store an infinite amount of data in finite storage.
14th Jan 2021, 7:47 PM
Shadow
Shadow - avatar
+ 5
The largest range you could get by using a native integral type is through unsigned long long, which would be [0, 2^64 - 1], although this is technically platform dependant - std::uint64_t would guarantee this range. That allows to calculate factorials for all numbers in the range [0, 65]. Afterwards, you'll end up with overflow issues again. To circumvent this problem, you would need to implement a custom algorithm operating on arrays, which are able to store more digits and thus larger numbers. Another option could be to use some sort of big integer class, but the standard library has none, so you would have to look elsewhere. The following codes might serve as an inspiration for the former solution: https://code.sololearn.com/cgn3cVHTt5hq/?ref=app https://code.sololearn.com/c05uyb2zjENS/?ref=app
14th Jan 2021, 7:23 PM
Shadow
Shadow - avatar
+ 5
I also once encountered the same problem as urs, what i can suggest u to simply use long double as the return type of the factorial() function, and unsigned as parameter(to simply receive a positive number instead of any negative number). This will allow u to calculate factorial upto 1754, but from 1755, it will show u "inf"(means infinity). And to see the the actual number use to_string() on factorial() function while calling it, because long double values will be shown in e-notations. I hope this helps u to solve ur problem. Happy Sololearning!!☺👍
14th Jan 2021, 8:05 PM
Mohan
Mohan - avatar
+ 4
You're hitting the limits of the data types.
14th Jan 2021, 7:58 PM
Sonic
Sonic - avatar
+ 3
Shadow Sir while roaming on google i found a link of big integer library But no idea about how to implement/use it ; how to set up the library in my IDE (VS Code) https://mattmccutchen.net/bigint/ Above Arsenic's code factorial of HUGE numbers has a limit of only 10000 Means overflow problem is not gonna to be solve for now ¯\_(ツ)_/¯
14th Jan 2021, 7:29 PM
Mr. Rahul
Mr. Rahul - avatar
+ 2
There is a way to make gmp work on soloearn (well, for a certain meaning of word -- it still gives "no output" approximately 9 times of 10, but keep retrying and it will run) Here is a calculation of 100! https://code.sololearn.com/cAzNAIz0vWky/?ref=app
15th Jan 2021, 3:25 PM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
+ 2
Volodymyr Chelnokov I was seeking of something which give me a permanent solution on this topic. But Standard library has no solution i think. May i have to find some library on github to overcome this problem ¯\_(ツ)_/¯
15th Jan 2021, 3:29 PM
Mr. Rahul
Mr. Rahul - avatar
+ 2
Mr. Rahul if you can link with arbitrary library, then gmp together with c++ wrapper gmpxx seems easiest. The only need for jumping through the hoops like my code does is to run it on sololearn, where you cannot give the linker information on what libraries to use.
15th Jan 2021, 3:32 PM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
+ 2
Managed to make the factorial work in c (without "no output", but still with ugly tricks) https://code.sololearn.com/cicWjI025511/?ref=app
16th Jan 2021, 12:32 AM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
+ 1
Volodymyr Chelnokov Ya your code run on sololearn but not always its showing no output many times.
15th Jan 2021, 3:33 PM
Mr. Rahul
Mr. Rahul - avatar