Is there any C++ header that allows me to calculate extremely large numbers?

[GorfTheFrog]

Hello guys,

That is the question. I am not looking for a fast implementation but basically, it should at least be able to do this :
+ Calculate 2^200000 in a minute or less
+ Calculate 20000! in a minute or less

I do not want a C++11 implementation, my complier does not support it. I would be helpful if someone can help me find a proper one. Thanks.

P.S : I am a kid, I know it is a crazy idea, but I really want to know if there is an integer variable that can store a number that is even bigger than what a uint64_t can store. Thank you very much.

[JLBorges]

Header: boost/multiprecision/cpp_int.hpp (benign)
Header with dependency on the GNU GMP library: boost/multiprecision/gmp.hpp (faster, albeit viral)
http://www.boost.org/doc/libs/1_61_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints.html

C++98, cpp_int

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
    boost::multiprecision::cpp_int pow = 1 ;
    for( int i = 0 ; i < 20000 ; ++i ) pow *= 2 ;
    std::cout << "2^20000 has " << pow.str().size() << " digits\n" ;
    
    boost::multiprecision::cpp_int fact = 1 ;
    for( int i = 2 ; i < 20001 ; ++i ) fact *= i ;
    std::cout << "20000! has " << fact.str().size() << " digits\n" ;
}

------ clang++ ------
2^20000 has 6021 digits
20000! has 77338 digits

real	0m0.465s
user	0m0.460s
sys	0m0.000s


--------- g++ --------
2^20000 has 6021 digits
20000! has 77338 digits

real	0m0.540s
user	0m0.528s
sys	0m0.008s

http://coliru.stacked-crooked.com/a/d9497f1b373e144d

C++98, mpz_int

#include <iostream>
#include <boost/multiprecision/gmp.hpp>

int main()
{
    boost::multiprecision::mpz_int pow = 1 ;
    for( int i = 0 ; i < 20000 ; ++i ) pow *= 2 ;
    std::cout << "2^20000 has " << pow.str().size() << " digits\n" ;
    
    boost::multiprecision::mpz_int fact = 1 ;
    for( int i = 2 ; i < 20001 ; ++i ) fact *= i ;
    std::cout << "20000! has " << fact.str().size() << " digits\n" ;
}

------ clang++ ------
2^20000 has 6021 digits
20000! has 77338 digits

real	0m0.106s
user	0m0.076s
sys	0m0.000s


--------- g++ --------
2^20000 has 6021 digits
20000! has 77338 digits

real	0m0.098s
user	0m0.088s
sys	0m0.008s

http://coliru.stacked-crooked.com/a/967800d789d6e279

[GorfTheFrog]

@JLBorges
Thanks very much for your reply.
I see you do 2^20000. How about 2^200000?

[JLBorges]

> How about 2^200000?

About a second or so (x86_64, 3 GHz).

We can go higher than that; 2^1000000 takes about 20 seconds (benign) / 14 seconds (viral)
http://coliru.stacked-crooked.com/a/80dbbd8ee92adea3
http://coliru.stacked-crooked.com/a/9b01426ceb02cef1

[JLBorges]

Faster algorithm ( O( log n ), recursive):

boost::multiprecision::cpp_int pow2( unsigned int p )
{
    if( p == 0 ) return 1 ;
    else if( p == 1 ) return 2 ;
    else return pow2( p/2 ) * pow2( (p+1)/2 ) ;
}

Benign version: 2^1000000 in about 7 seconds
http://coliru.stacked-crooked.com/a/ea635b4f41311d14

Viral version: 2^20000000 in about 7 seconds
http://coliru.stacked-crooked.com/a/c5ac7f3becc26f4e

Multiplication appears to be way faster with the malignant GNU library.

[a k n]

We can make this a bit more faster if we are just calculating a power of two:
(Though this'll not help OP with the factorial one)

http://coliru.stacked-crooked.com/a/547ff802d3201b9f

At this point, most of the time elapsed is taken to convert the number to a decimal string.