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 integ开发者_JAVA技巧ers that are stored in parts? im making a library that stores a uint128_t as uint64_t UPPER, LOWER.

---

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

• The GNU Multiple Precision Arithmetic Library

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

For Windows, see this link:

• GMP Install Instruction for Windows Platform

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

• How to Install and Run GMP on Windows Using MPIR
• Building GMP library with Visual Studio? (Stackover topic)

---

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

• GMP Basics
• GMP Manual

---

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.

---

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

---

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