3DSoftware.com: Integers

3DSoftware.com > Programming > Integers > Page 2

Integers Page 2

Decimal Integers (DecInteger)

We need a character-based decimal integer type that is like the Symbolic C++ version 2 “Verylong” class, but more efficient and with less features. We will call this type of number DecInteger. The buffer size for this type of number will not be variable, but will instead be fixed.

The character string buffer for the “Verylong” class was declared as a pointer in Symbolic C++ (p. 452):

char *vlstr;

For DecInteger we make that a fixed buffer than can hold up to 160 decimal digits and a terminating null character (set this to a higher number of digits if necessary):

char vlstr[161];

This way, new and delete are not called when the number of digits changes. Instead, simply do bounds checking.

Addition

This new class performs addition just like the “Verylong” class (p. 458), but does not call new and delete. The variable temp is now defined as a buffer instead of as a pointer (it is no longer created with new):

char temp[161];

The digits are processed sequentially in a for loop. The variable carry is a 32-bit integer that holds the carry-in value for the digit, which is the carry-out value from the previous digit, or zero if there was no previous digit. The variable digitsum is the sum of the corresponding digit of the two large integers plus carry.

If digitsum is greater than 9, the difference becomes the carry-out, otherwise the carry-out is zero. The carry-out is saved to carry, which becomes the carry-in for the next digit, or becomes a new digit if it is non-zero and there is no next digit.

Each digitsum (after the carry-out is subtracted from it) is copied to that digit position in the temp character buffer.

All that is within the for loop. After the for loop, a terminating null is appended to temp, and temp is reversed with an strrev function. Then another DecInteger object instance is declared, initialized with temp and returned as the result of the addition operation.

The following example prints 15:

DecInteger a, b, c;
a = "10";
b = "5";
c = a + b;
c.print();

The print function reverses the string for printing:

void DecInteger::print()
{
   char temp[161];
   strcpy(temp,vlstr);
   strrev(temp);
   if (vlsign)
      printf("-");
   printf("%s",temp);
}

Reversing is necessary when exporting the digits to external formats because integer digits grow in the opposite direction than character strings grow: when a new digit is appended to an integer, that digit is to the left; when a new character is appended to a text string, that new character is to the right. The digits are stored in reverse order internally.

Subtraction

Subtraction is like the “Verylong” class, but with temp as a buffer as we did for addition above. The carry variable becomes borrow and is subtracted when needed from the next digit instead of added to the next digit.

Multiplication

Multiplication is like the “Verylong” class, which did not call new or delete and therefore does not need to have such calls removed.

Multiplying two numbers involves multiplying the first number with each digit of the second number, one at a time until all the digits of the second number are multiplied into the first number. Each intermediate mulitplication (partial product) is added to the variable tempsum which is a DecInteger object and is returned as the product. Each partial product is multiplied by the appropriate power of 10, according to its digit position, before being added to tempsum.

For DecInteger we are adding a new feature to multiplication: if the multiplier is a power of ten (most significant digit 1 and all other digits 0) then the multiplication simply consists of calling mult10() which shifts digits.

Division

Division is like the “Verylong” class, but with temp as a buffer instead of using new and delete for memory allocation, and division by a power of ten becomes shifting.

— Page 2 —

« Page 1

Contents

Page 3 »

Thursday, 20-Nov-2008 12:01:19 GMT