3DSoftware.com > Programming > Integers > Page 7

Integers  Page 7   Wide Unsigned Integers   High and Low Multiplication   When you multiply two wide unsigned integers that occupy the same amount of memory (number of bytes), the product takes up twice as much memory. For example, the product of two 32 bit numbers is a 64 bit number.   We listed polynomials for generating such products in the previous page of this article (opens new browser window). We now turn to the problem of working with numbers that all take the same amount of storage space. For example, when multiplying two 32-bit numbers, we want the product to be two 32-bit numbers which can be appended together to form the 64-bit product later. One of those resulting 32-bit numbers is the high order 32 bits of the 64-bit product, and the other is the low 32 bits of the 64-bit product.

 

We showed how to multiply two 128-bit numbers, C and D, to produce a 256-bit number CD. Here is a polynomial for calculating a 160-bit number, X160, that includes the low order 128 bits of CD:

X160  =   ( A3B0 + A2B1 + A1B2 + A0B3 )t3 + ( A2B0 + A1B1 + A0B2 )t2 + ( A1B0 + A0B1 )t  + A0B0

The following equation calculates the 128-bit number, Y128, of the remaining high order bits of CD:

( Y128 )t4  =   A3B3t6 + ( A3B2 + A2B3 )t5 + ( A3B1 + A2B2 + A1B3 )t4

The low order 128 bits of X160 is the low order 128 bits of the product CD. The high order 32 bits of X160 (divided by t^4) is a carry that is added to Y128. The sum of Y128 plus that carry is the high order 128 bits of CD.

 

To multiply two 256-bit numbers, E and F:

X288  =                                ( Y256 )t8  =   ( A7B0 + A6B1 + A5B2 + A4B3 + A3B4 + A2B5 + A1B6 + A0B7 )t7 + ( A6B0 + A5B1 + A4B2 + A3B3 + A2B4 + A1B5 + A0B6 )t6 + ( A5B0 + A4B1 + A3B2 + A2B3 + A1B4 + A0B5 )t5 + ( A4B0 + A3B1 + A2B2 + A1B3 + A0B4 )t4 + ( A3B0 + A2B1 + A1B2 + A0B3 )t3 + ( A2B0 + A1B1 + A0B2 )t2 + ( A1B0 + A0B1 )t  + A0B0      A7B7t14 + ( A7B6 + A6B7 )t13 + ( A7B5 + A6B6 + A5B7 )t12 + ( A7B4 + A6B5 + A5B6 + A4B7 )t11 + ( A7B3 + A6B4 + A5B5 + A4B6 + A3B7 )t10 + ( A7B2 + A6B3 + A5B4 + A4B5 + A3B6 + A2B7 )t9 + ( A7B1 + A6B2 + A5B3 + A4B4 + A3B5 + A2B6 + A1B7 )t8

The low order 256 bits of X288 is the low order 256 bits of the product EF. The high order 32 bits of X288 (divided by t^8) is a carry that is added to Y256. The sum of Y256 plus that carry is the high order 256 bits of EF.     Overflow   To implement a system, of making the total product use the same amount of storage as the operands, involves checking for overflow of multiplication. If the product of two numbers is too large to fit in the storage space allocated for a single number, overflow occurs.   High multiplication (calculation of Y128 and Y256 in the examples above) is not performed, but the factors of the terms that would have been used for high multiplication are compared to zero. If any of the terms for high multiplication would be non-zero, there is overflow.   If the high multiplication coefficients would all be zero, the next step is to perform the low multiplication, which was the calculation of X160 and X288 in the examples above. Each coefficient (factor of t^n) in the polynomial for low multiplication is a partial product. The result (total product) of the low multiplication is the summation of those partial products.   Each partial product is a 64-bit number with 32-bit overlaps of adjacent partial products. The partial products can be converted to 32-bit numbers so that there are no overlaps, and so that the last such number would be the carry to high multiplication. Then, if that carry is zero, there is no overflow, otherwise there is overflow.   To convert a partial product from 64 bits to 32 bits, carry-out (remove) the high 32 bits and use that carry-out (right shifted) as the carry-in for the next digit. Only if the last digit processed is zero would there be no overflow. That is the extra digit that is supposed to be the carry to high multiplication.   In our WideInteger implementation, each digit is 30-bits. For a 240-bit WideInteger, low multiplication has 270 bits (X270), and carries are right shifted 30 bits.

 

—  Page 7  —

« Page 6 Contents

 

Copyright © 2008 by 3D Software. All rights reserved. 3D Software, P.O. Box 221190, Sacramento CA 95822 USA www.3DSoftware.com     Contact us

Thursday, 20-Nov-2008 13:27:18 GMT