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
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/
I'm interested in the same subject, and I've found a similar question right here: How to implement big int in C++ I hope it will point you into the right direction!