How to implement big integer in c++?? e.g for operations like 10^12 modulo 1000000007
2 Likes
10^12 fits in a long long.
3 Likes
There is no in built library for implementing Big Integer in C++.The max value of integer that fits in a c++ datatype(unsigned long long) is 2^64-1(ie 18446744073709551615).
So if you want to evaluate number bigger than this and you are a c++ coder,
then only way is to store the value in form of character array and perform operation (addition,subtraction,multiplication),on each digits like you did in elementary high school.
But if you are a java coder ,then you are quite lucky,java Maths.BigInteger class http://docs.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html has such features and most of the coder use it these days(and i would also recommend you to use it).Python has also got such feature.Hope this helps!
7 Likes
For modulo operation utilise the theorems: (a%m+b%m)%m=(a+b)%m and (a%mb%m)%m=(ab)%m. If exponent is too high you can do repeated squaring, a^n=(a^(n/2))^2 (n is even).
1 Like