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.
Asked
Active
Viewed 416 times
0
calccrypto
- 8,583
- 21
- 68
- 99
-
2[This question](http://stackoverflow.com/questions/269268/) contains several useful answers. – Björn Pollex May 25 '11 at 21:18
4 Answers
2
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:
- 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:
-
@calccrypto: Of course, you've to download and install it, before using it. – Nawaz May 25 '11 at 21:30
-
install??? i thought it was just decompress, copy into some folder, and link the compiler to it – calccrypto May 25 '11 at 21:31
-
@calccrypto: Yes. That whole process is installation, with configuration and all. – Nawaz May 25 '11 at 21:33
-
-
@calccrypto: Most certainly, you've downloaded the wrong file, or maybe there is some problem with the download. – Nawaz May 25 '11 at 21:36
-
ive downloaded it multiple times, and it never had the .h file. i went out of my way to find it, and managed to fine it. unfortunately, i deleted the entire folder and tar.bz by accident. besides. i could never get mpz_t working – calccrypto May 25 '11 at 21:37
-
please tell me where in the folder after it is extracted, the gmp.h file is located – calccrypto May 26 '11 at 00:09
-
-
@calccrypto: It requires proper installation without which you cannot have `gmp.h` which is created when you install it by running the given installation script. see this : http://gmplib.org/manual/Installing-GMP.html#Installing-GMP – Nawaz May 26 '11 at 00:23
-
@calccrypto: Before using it, must read the GMP Basics : http://gmplib.org/manual/GMP-Basics.html#GMP-Basics – Nawaz May 26 '11 at 00:24
-
@calccrypto: That is what I was suspecting. The `tar.bz` you've download is for unix only, not for windows. Anyway, see my answer. I updated it. – Nawaz May 26 '11 at 04:34
1
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.
Landei
- 54,104
- 13
- 100
- 195
-
In my tests, Karatsuba multiplication was slower unless I had a lot more than two "digits". – Mooing Duck Mar 07 '12 at 17:13
0
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic might be a good start. There are plenty of open source libraries already
parapura rajkumar
- 24,045
- 1
- 55
- 85
0
Take a look at the various Big Integer libraries. Here's one that google found https://mattmccutchen.net/bigint/
Richard Schneider
- 34,944
- 9
- 57
- 73