Article Preview

COLUMN

Arbitrary Precision Numbers

Storing and performing math on larger numbers with improved accuracy

Issue: 3.1 (September/October 2004)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 13,294
Starting Page Number: 34
Article Number: 3116
Resource File(s):

3116.zip Updated: 2013-03-11 19:07:58

Related Link(s): None

Excerpt of article text...

The numeric types provided by modern computers cannot store a very large range of numbers. Long integers can store, at most, unsigned numbers up to around 4.29 billion, or +/-2.15 billion for signed numbers. Floating point numbers can store larger (and smaller) values than an integer, but their precision is very limited. You cannot rely on floating point numbers being exactly what you think they are. For many numbers, these limitations mean that the built-in numeric types are useless.

Fortunately, smart programmers have come up with an algorithm for "arbitrary precision" numbers, which can be very large or very small while also being extremely precise. The secret to arbitrary precision numbers is to store the number in some kind of string representation in which each digit is specified exactly. For example, a number could be represented by a string of bytes, each containing a value between 0 and 9.

Let's consider the way the BigNumber class, found in the sample project (download instructions reside on page 4), will store the number strings. BigNumber's constructor creates a MemoryBlock of 2 * maxSize bytes, where maxSize is the maximum desired number length, in terms of digit count. The first digit after the decimal point will be stored at the byte position maxSize, and the first digit before the decimal point will be stored at position maxSize-1. See Figure 1 for an example. Note that, although there is space in this structure for 2 * maxSize digits, we will only allow numbers with maxSize digits to be stored.

What about calculations? If you're dealing with numbers, you're likely to need to add, subtract, multiply or divide them. How do you perform these operations on a string? There are many answers to this question, but the one we'll be exploring is the simplest -- grade school math. Yes, that's right, we're going to use the same techniques children learn in grade school!

The Add function is the easiest to write. First, it compares the signs of the numbers. If the signs differ, the operation is converted to an equivalent subtraction and passed off to the Subtract function. Next, the Add function simply begins adding columns of digits from right to left, and this number is added to the corresponding digit in the result. If the resulting digit is greater than 10, then it has 10 subtracted from it, and the next digit to the left in the result is incremented by one. This corresponds to the grade school trick of performing a "carry" operation. If a carry cannot be performed because the next digit is out-of-bounds, then a BigNumberOverflowException is raised.

Finally, when the addition is complete, the Add function tidies up by adjusting the length of the number to ensure it is no more than maxSize digits in length, truncating and rounding if necessary. Note that truncation and rounding only occur on digits after the decimal point. If there are more than maxSize digits before the decimal point, an overflow exception is raised.

...End of Excerpt. Please purchase the magazine to read the full article.