How to Handle Large Numbers - Part 1

• Download source - 11.6 KB

Introduction

With increase in computing power, the definition of large numbers too has changed. This led to the creation of plenty of libraries that provide mechanisms to handle numbers that are larger than maximum values for standard data types. But what if they did not exist? This article is an attempt to create one such library.

Disclaimer

The code presented is not optimal or ready for professional use. This is just for showing one possible approach and the mathematics required to handle large numbers. It only does the four basic mathematical operations and is not load tested.

Background

Each base 10 number can be represented as a polynomial of powers of 10. Take a look at the following:

Thus, the number 123.456 can be stored in an array where the index represents powers of 10 associated with the digit. So, this number are be represented as:

int[] digitsBeforeSeparator = new int[3]{1,2,3};
int[] digitsAfterSeparator = new int[3]{4,5,6};

In case of digits after separator, the index is actually one more than actual power of associated with the number (item at index 1 represents 10-2). This will be used to represent all the numbers in the code and mathematical operations will be performed on these arrays.

Using the Code

For the sake of brevity, I have chosen not to include code sections.

Number Class

This class represents the number. It supports creation of objects representing positive decimal and natural numbers. These numbers can be accessed using a property that returns number as string. There is only one accessible constructor that accepts the string input. The method ValidateInput uses Regex to ensure that the input is valid. PrepareArrays method will create arrays from number as shown above. As of now, only period (.) is supported as decimal character. Here is how a number is broken into arrays:

private void PrepareArrays()
        {
            int decimalLocation = -1;
            int numberLength = _value.Length;
            _isDecimal = (decimalLocation = _value.IndexOf('.')) != -1;

            if (_isDecimal)
            {
                _digitsBeforeDecimal = new int[decimalLocation];
                _digitsAfterDecimal = new int[numberLength - decimalLocation - 1];
            }
            else
            {
                _digitsBeforeDecimal = new int[numberLength];
                _digitsAfterDecimal = null;
            }

            for (int index = 0; index < _value.Length; index++)
            {
                if (index == decimalLocation)
                {
                    // Decimal separator
                    continue;
                }
                else if (_isDecimal && index > decimalLocation)
                {
                    _digitsAfterDecimal[index - decimalLocation - 1] = 
                       (int)Char.GetNumericValue(_value[index]);
                }
                else
                {
                    _digitsBeforeDecimal[index] = (int)Char.GetNumericValue(_value[index]);
                }
            }
        }

Addition

This is the simplest of the mathematical operations. Each element in corresponding arrays will be added and stored in separate array as result. Carry over, if any, will be persisted and added to next element set.

Number class provides static method Add that allows to add two numbers. It also overloads the operator +, thus enabling addition of number objects just like integers. Number of digits in the sum can only be one more than the larger of two numbers (assuming that trailing zeros after the decimal point are displayed).

public static Number Add(Number firstNumber, Number secondNumber)
public static Number operator +(Number firstNumber, Number secondNumber)

Usage:

Number first = new Number("12.34");
Number second = new Number("09.56");

 Number sum = first + second;
 // or
 sum = Number.Add(first, second);

Subtraction

This operation too works along the same lines as addition. Each element in the array will be reduced by corresponding element in another array for second number. This operation can return negative numbers.

Number class provides static method Subtract that allows subtracting two numbers. It also overloads the operator - thus enabling subtraction of number objects similar to standard data types.

Number of digits in resulting number could be anything between the number of digits both the numbers. In the code initially, result is assumed to have same number of digits as larger number and later unnecessary elements from result array are removed.

public static Number Add(Number firstNumber, Number secondNumber)
public static Number operator -(Number firstNumber, Number secondNumber)

Usage:

Number first = new Number("12.34"); 
Number second = new Number("09.56"); 
Number difference = first - second; 
// or 
difference = Number.Subtract(first, second);

Multiplication

Multiplying large numbers uses similar approach as in multiplying polynomials. The tricky part here is to identify the number of digits up front in the result. Let us se how polynomials can be multiplied:

Here, you can see that maximum number of digits possible before decimal can only be double of the larger number. Same applies to maximum number of digits possible after decimal. In our case, before decimal we can have 4 digits (from 12.34) and after decimal too we can only have 4 digits (from both the numbers).

Once the digits are multiplied, we need to identify the location they appear in the result. Following shows the mechanism used to get this detail:

Similar to other operations, we have a method and operator as following:

public static Number Multiply(Number firstNumber, Number secondNumber) 
public static Number operator *(Number firstNumber, Number secondNumber)

Usage:

Number first = new Number("12.34"); 
Number second = new Number("09.56"); 
Number product = first * second; 
// or 
product = Number.Multiply(first, second);

What About Division?

Division will require implementation of some complex algorithm. In my opinion, it deserves a dedicated article coming soon.

History

• V 0.0: Initial version