How would you compute the multiplication of two 1024 bit numbers on a microprocessor that is only capable of multiplying 32 bit numbers?
- 1Do you have a specific language? If you're using Java, then check out the BigInteger class in the java.math package. If not, find a similar library for what you're using.childofsoong– childofsoong2015-03-07 00:59:34 +00:00Commented Mar 7, 2015 at 0:59
- Example code: sites.google.com/site/indy256/algo_cpp/bigintStephen C– Stephen C2015-03-07 01:02:30 +00:00Commented Mar 7, 2015 at 1:02
- No, I'm interested in the mathematics behind it, not necessarily the implementation details.Dr. Van Nostrand– Dr. Van Nostrand2015-03-07 01:03:09 +00:00Commented Mar 7, 2015 at 1:03
- Then read about the Karatsuba algorithm: en.wikipedia.org/wiki/Karatsuba_algorithm. Or just generalize from the algorithm you were taught in primary school for doing long multiplication with "words" that represent the 10 possible numbers :-)Stephen C– Stephen C2015-03-07 01:03:30 +00:00Commented Mar 7, 2015 at 1:03
- 1Just multiply like you would manually. The algorithm is basically the same... use base 2^32.thang– thang2015-03-07 01:05:49 +00:00Commented Mar 7, 2015 at 1:05
| Show 2 more comments
2 Answers
The starting point is to realize that you already know how to do this: in elementary school you were taught how to do arithmetic on single digit numbers, and then given data structures to represent larger numbers (e.g. decimals) and algorithms to compute arithmetic operations (e.g. long division).
If you have a way to multiply two 32-bit numbers to give a 64-bit result (note that unsigned long long is guaranteed to be at least 64 bits), then you can use those same algorithms to do arithmetic in base 2^32.
You'll also need, e.g., an add with carry operation. You can determine the carry when adding two unsigned numbers of the same type by detecting overflow, e.g. as follows:
uint32_t x, y; // set to some value uint32_t sum = x + y; uint32_t carry = (sum < x); (technically, this sort of operation requires that you do unsigned arithmetic: overflow in signed arithmetic is undefined behavior, and optimizers will do surprising things to your code you least expect it)
(modern processors usually give a way to multiply two 64-bit numbers to give a 128-bit result, but to access it you will have to use compiler extensions like 128-bit types, or you'll have to write inline assembly code. modern processors also have specialized add-with-carry instructions)
Now, to do arithmetic efficiently is an immense project; I found it quite instructive to browse through the documentation and source code to gmp, the GNU multiple precision arithmetic library.
Comments
look at any implementation of bigint operations
- here are few of mine approaches in C++ for fast bignum square
- some are solely for sqr but others are usable for multiplication...
use 32bit arithmetics as a module for 64/128/256/... bit arithmetics
- see mine 32bit ALU in x86 C++
- use long multiplication with digit base
2^32 - can use also Karatsuba this way
