CODEWITHSUNDEEP
modulo
Beelzeboul
Beelzeboul

Reputation: 45

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

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.

Upvotes: 3

Views: 3575

Answers (4)

Inquisitive
Inquisitive

Reputation: 485

Hint: Use a linked list. Store the number as a group of numbers dynamically. For eg:

112233445566778899001122 => 11223344 55667788 99001122

Now consider the individual unit and start from left to right. Find the reminder and manipulate it to add to the next group and go on.

Now implementation is very easy :)

Edit:

112233445566778899001122/6 =>  11223344 55667788 99001122/6


 11223344/6 =>2

 2*100000000 + 55667788 = 255667788
 255667788/6 => 0
 0*100000000 + 99001122 = 99001122
 99001122/6=>0

 So the reminder is 0.

Remember, the individual unit after manipulation should be under the maximum range int can support.

Upvotes: 0

ta.speot.is
ta.speot.is

Reputation: 27214

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.

Upvotes: 3

jqpubliq
jqpubliq

Reputation: 11904

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.

Upvotes: 0

Greg Hewgill
Greg Hewgill

Reputation: 994351

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.

Upvotes: 2

Related Questions