• Post Reply Bookmark Topic Watch Topic
  • New Topic

Fractorial does not work properly when input is large  RSS feed

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone,


I've written a small program that does factorial by recursion.

I think it works properly for small input like 10, but it stops working properly

if the input becomes large, like 100.

If I try any large input, I get a zero.

I am a complete noob and cannot figure out why I am getting 0s.

Can anyone give me pointers for solving the problem?


Thank you very much in advance!


 
Bartender
Posts: 4568
9
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Factorial is a function that increases very rapidly. It doesn't take that long before you reach values that are too big to fit in a long variable. After that point the values start overflowing.

If you really want to be able to calculate the value of factorials that large you need to use a class that provides unlimited precision arithmetic. Have a look at the BigInteger class.
 
Marshal
Posts: 56600
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you get overflow with longs with arguments over 21. With ints you can't get beyond 12.

And welcome to the Ranch
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you count the number of 0 bits at the right end of numbers, you get one 0 for 2 6 10, you get two 0s for 4 12 and three 0s for 8, etc. etc.
When you have passed sixty‑three 0s, you have sixty‑three 0s at the right of your output because every time you multiply by an even number you add another 0 to the right of the result. The next multiplication by an even number will push the last 1 bit off the left end of the number and you now have sixty‑four 0s in your number. So it prints zero.
 
Dawkins Christopher
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Aha, that is the reason. It just didn't occur to me that overflow would happen so quickly.

So even long isn't big enough. Gotta learn biginteger class.

Thank you so much guys for help and warm welcome!



 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
BigInteger doesn't have a constructor taking an int or a long for its value. You can however create an increasing factor like this:-Since BigInteger is immutable you must use the assignment operator.
 
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yups,

And just in caee you ever have to play the nerdy version of trivial pursuit: common calculators can only calculate up to 69!

Luckely in most factorial calculations you're not just calculation large permutations, but also, variations and combination. Think of it. Calculating variations and combinations might be nice methods to programme too. Just for fun off course.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!