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/