Multiplying together two 32-bit numbers
produces a 64-bit number.
We multiply two 30-bit numbers together to
produce a 60-bit number.
Each 30-bit number is actually a
32-bit number with the two high bits cleared,
and the product is a 64-bit number with the
4 high bits cleared.
Multiplying together two 64-bit numbers,
A and B, produces a 128-bit number AB.
To use 32-bit multiplication,
each 64-bit operand (A and B)
must be split into high and low 32-bit
operands:
|
A1 is the high order 32 bits of A
A0 is the low order 32 bits of A
B1 is the high order 32 bits of B
B0 is the low order 32 bits of B
|
|
A and B become polynomials (with t = 232):
|
A = A1t + A0
B = B1t + B0
|
|
Multiplying polynomials together consists of multipying
each term of one polynomial (one at a time)
with each term of the other polynomial (one at a time)
and summing those products. That sum, which is the product
of multiplying two polynomials, is itself a polynomial.
The product of the polynomials A and B we defined above
is the following polynomial AB:
|
AB = A1B1t2
+ (A1B0 + A0B1)t
+ A0B0
t2 = 264, t = 232
|
|
The first and last terms are adjacent
non-overlapping bit fields so they can
be ORed together instead of added together
(shifting the first term left
64 bits eliminates t²).
The other terms are shifted left
32 bits to eliminate t and
are then added to the result.
In that example, A was a 64-bit number,
B was a 64-bit number, and the product AB
was a 128-bit number.
|
Now we will multiply two 128-bit numbers,
C and D. The product CD will be a 256-bit number.
The numbers to be multiplied are the following polynomials:
|
C = A3t3 + A2t2 + A1t + A0
D = B3t3 + B2t2 + B1t + B0
t3 = 296, t2 = 264, t = 232
An are digit packets of C
Bn are digit packets of D
|
|
The 32-bit digit packets are indexed
n=0 for the low order 32 bits
(bits 31–0), n=1 for bits 63–32, etc.
For example, B1 is the packet of bits 63–32 of D.
The product CD is a 256-bit number:
|
|
CD =
|
A3B3t6
+ ( A3B2 + A2B3 )t5
+ ( A3B1 + A2B2 + A1B3 )t4
+ ( A3B0 + A2B1 + A1B2 + A0B3 )t3
+ ( A2B0 + A1B1 + A0B2 )t2
+ ( A1B0 + A0B1 )t
+ A0B0
|
|
|
[Shaf]
|
Shafarevich, I.R., 2003,
Discourses on Algebra,
p. 27. Note: In the equations for g(x) on that
page, if one of the terms is b1g, that term should be b1x.
|
|
[Barb]
|
Barbeau, E.J.,
Polynomials,
p. 2.
|
|
[Irving]
|
Irving, R.S.,
Integers, Polynomials, and Rings,
p. 222.
|
