Recursive factorial function producing incorrect results on "22!"

Question

I'm making a small factorial function to assist with some math I have to do for a function.

#include<iostream>
using std::cout;
using std::endl;
class HandsShaking{
    private:
    unsigned long long fac(int n){
        return fac(n, 1);
    }

    unsigned long long fac(unsigned long long n, unsigned long long ret){
        if(n == 1){
            return ret;
        }else{
            return fac(n-1, ret*n);
        }
    }

   public:
   unsigned long long countPerfect(unsigned long long n){
        unsigned long long m = n/2;
        cout<<fac(n)<<endl;
        cout<<(fac(m+1)*fac(m))<<endl;
        return fac(n)/(fac(m+1)*fac(m));
    }
};

I'm using tail recursive and unsigned long longs everywhere so I doubt it is am overflow.

I haven't separated the functions and definitions, but my submission (the count perfect function) specifies one file.

The function seems to work for all numbers up to 22 and fails for all numbers after.

What is the range of `unsigned long long`? or `std::numeric_limit::max()`? [It possibly overflows on your system.](https://www.google.co.in/search?client=ubuntu&hs=1vJ&q=22%21+-+2%5E64&oq=22%21+-+2%5E64&gs_l=psy-ab.3...4086.7647.0.7933.8.8.0.0.0.0.398.1180.3-3.3.0....0...1.1.64.psy-ab..5.3.1179...0i8i30k1j0i8i7i10i30k1j0i7i5i10i30k1j0i8i10i30k1j0i8i7i30k1j35i39k1j0i67k1j0i7i30k1.0.DBc-lgYjm74). Similar question: https://stackoverflow.com/questions/236335/when-i-calculate-a-large-factorial-why-do-i-get-a-negative-number — Mohit Jain, Oct 04 '17 at 05:08
22! is greater than 2⁶⁴. Unless `unsigned long long` is 128 bits (or more) on your system (which is extremely unlikely), your computation is overflowing. — Cornstalks, Oct 04 '17 at 05:11
fairly sure its 64 bits 1.8 * 10^19 which puts 22! out of range. problem being i still need fac to work to 50! and i dont know of any larger number types. — Samuel Kurtzer, Oct 04 '17 at 05:13
Then I suggest you look around for a library to help you (or implement your own big integer class). Doing a Google search for "C++ big integer library" should get you started in the right direction. — Cornstalks, Oct 04 '17 at 05:16
50! is 3.041409320171338e64 (unless my linux calculator fails me, but sounds reasonable) and would require about 215 bits to encode as full integer. Just in case you need this in some particular formula, there may be small chance to simplify it to get it back into common integer ranges (like (n+m)!/n! for small m). If you work on some generic maths helper function, then you need to implement (or rather use) arbitrary precision library. (and it's not clear why you are using recursion, as it makes everything worse about this `fac(..)` code from programming point of view, is it some exercise?) — Ped7g, Oct 04 '17 at 11:19

score 0 · Answer 1 · answered Oct 04 '17 at 05:25

You can use Boost.Multiprecision for such tasks.

#include <iostream>

#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;

cpp_int factorial(cpp_int x)
{
    if (x == cpp_int{1}) return cpp_int{1};
    return x*factorial(x-1);
}

int main()
{
    cpp_int n{22};
    std::cout << factorial(n) << '\n';
}

Live example

Recursive factorial function producing incorrect results on "22!"

1 Answers1