CODEWITHSUNDEEP
c++mathoperator-overloadinguint
calccrypto
calccrypto

Reputation: 8991

Multiplication and division on integers split into parts

Does anyone know where I might get instructions on how to do multiplication and division (and maybe even modulus) on integers that are stored in parts? im making a library that stores a uint128_t as uint64_t UPPER, LOWER.

Upvotes: 0

Views: 426

Answers (4)

Landei
Landei

Reputation: 54574

Having your numbers splitted that way is an ideal prerequisite for Karatsuba multiplication. Consider:

x = x1 * 2^k + x2
y = y1 * 2^k + y2

Using the school multiplication, you would need 4 multiplications:

x*y = (x1*y1) * 2^(2*k) + (x1*y2 + x2*y1) * 2^k + x2*y2

Karatsuba needs a few more additions, but only 3 multiplications:

p1 = x1 * y1
p2 = x2 * y2
x*y = p1 * 2^(2*k) + ((x1+x2)*(y1+y2) - p1 - p2) * 2^k + p2

Of course the problem is how to deal with overflows.

Upvotes: 1

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361352

Are you familiar with GMP library? Why don't you use it instead of implementing your own?

From the above link, you can download tar.bz file for Unix-based OS.

For Windows, see this link:

It has lots of information and installation file for MinGW, MSVC++, and CgyWin. Download that suits your need. You can also see these link:

After you're done with installation and configuration, you would like to know how to program using GMP, for that browse through these links:

Upvotes: 2

Richard Schneider
Richard Schneider

Reputation: 35477

Take a look at the various Big Integer libraries. Here's one that google found https://mattmccutchen.net/bigint/

Upvotes: 0

parapura rajkumar
parapura rajkumar

Reputation: 24403

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic might be a good start. There are plenty of open source libraries already

Upvotes: 0

Related Questions