3DSoftware.com > Programming > Integers > Page 3

Integers  Page 3   Wide Integers   We need large (wide) binary integers represented with a fixed number of bits. We will call these types of integers WideInteger. The number of bits is configured when the wide integer is declared. In this discussion, the length of a WideInteger will be 240 bits.   The 240 bits represent the actual number, not including the sign.  A separate sign flag is used to record the sign of the number, as is done for DecInteger numbers. The number itself is unsigned (not represented in complement form).   In our implementation, each “digit” of a WideInteger number is 30 bits.  Each such digit can have a value in the range [0, 2^30 – 1], not just the [0, 9] range allowed for decimal digits discussed earlier.   Each digit is stored in a digit packet. Each digit packet actually contains 32 bits, but only 30 bits are used to store data. The other 2 bits are cleared (zeroed out) and reserved for use by algorithms that clear those bits when those algorithms are done. Those extra 2 bits are the high order bits of the digit packet: bits 31–30.  The digit itself is stored in bits 29–0 of the digit packet.   We use SIMD for optimization on AMD-based computers. We define a 128-bit simd packet that contains 4 digit packets:

 

Addition   Addition is like the DecInteger addition discussed in the previous page, but now each digit is a 30-bit binary number. Since each digit is binary, carry propagation is simplified at the machine level.   First, the two numbers being added together have their corresponding digit packets added together with the PADDD simd instruction (see AMD64 Architecture Programmer’s Manual Volume 4: 128-Bit Media Instructions for complete listing of simd instructions). The PADDD instruction is for signed numbers, but is performed unsigned here because the high bit of the digit packets will be clear during this operation.   Before the PADDD instruction is invoked, bits 31-30 are clear. Invoking the PADDD instruction causes each digit packet to generate a carry-out in bit 30.  That bit is added as a carry-in to bit 0 of the next more significant digit.   Carrying can be done sequentially (not simd) one digit at a time beginning with the least significant digit packet, or can be done with simd instructions as explained in the next page of this article.

 

—  Page 3  —

« Page 2 Contents Page 4 »

 

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 12:34:48 GMT