How to find the remainder of large number division in C++?

Question

Hello, I have a question regarding modulus in C++. What I was trying to do was divide a very large number, lets say for example, M % 2, where M = 54,302,495,302,423. However, when I go to compile it says that the number is to 'long' for int. Then when I switch it to a double it repeats the same error message. Is there a way I can do this in which I will get the remainder of this very large number or possibly an even larger number? Thanks for your help, much appreciated.

Answer 1

For large number arithmetic in C++, use the GMP library. In particular, the mpz_mod function would do this.

For a more natural C++ wrapper, the mpz_class class can help by providing operator overloading for multiprecision operations.

Answer 2

You can try storing the number in a "long long" (64 bit integral value), just be aware that if your application is multi-threaded and running on a 32-bit CPU you will need to synchronize between threads when reading/writing this value as it takes 2 clock cycles to read/write.

Alternatively, try a bignum library

If you want to make things interesting, if you are only ever doing modulo 2 you can check the lowest bit and get your answer. If you are only doing up to modulo 255 you can take the lowest 8 (unsigned char) bits and do the operation on them. If you are only doing up to modulo 65535 you can take the lowest 16 bits (unsigned short) and do the operation on them.

Answer 3

ints only range from –2,147,483,648 to 2,147,483,647. Check http://msdn.microsoft.com/en-us/library/s3f49ktz(VS.71).aspx for data type ranges. I recommend a long long.