Addition of Very Large Numbers

It’s not uncommon to get to a point in mathematics or programming that very large numbers must be dealt with. For the context of this post I will define a very large number (VLN) as any number that exceeds the maximum value of an unsigned 64-bit integer (aka ulong.MaxValue or 18,446,744,073,709,551,615). It’s surprisingly easy to run into a problem that deals with VLNs – often they will show up in programming when we are counting (a lot of) things or performing recursive calculations.

In the post Investigating Basic Combinatorics, I showed that, without any intentional programming, we could not evaluate all ⁿC_n/2 for n >= 21 without exceeding ulong.MaxValue. Even with intentional programming, we saw that ⁿC_n/2 starts to break the VLN barrier when n > 67.

One strategy to get around these constraints is to construct methods that deal with strings instead of numerical data types. Since String.Length has data type Int32, the theoretical character limit of Strings in C# is 2³¹. This means that the theoretical maximum of a number in base 10 that can be expressed by a string is 10²³¹ – 1. If that scale isn’t impressive, consider for a moment that the observable universe contains somewhere between 10⁷⁹ and 10⁸⁰ atoms. Such a scale for significant digits would cost an unprecedented amount of time in processing. For the sake of simplicity, we will generalize these limits and assume that strings do not constrain us to an upper limit for integer values.

In this post, I intend to address a strategy for dealing with the addition of integer type VLNs. Future posts will show how to extend the functionality to work with non-integer rational numbers and address multiplication, division, exponential, and combinatoric operations.

Arithmetic of VLNs is no different than arithmetic of any other set of expressible numbers and we only need to know how to sum two numbers in order to sum several numbers. Most of us learned how to deal with these problems when we were young children. When adding two numbers we start with the units digit and add them together. When the sum of the digits exceeds 9, we keep only units part of the sum and carry over the resulting tens digit. Next, the tens digits get added in the same manner, except that the previous carry over is added to the sum. This process continues until all units have been added together in this manner. If the last summation would have a carry over unit, the carry over is treated as the final sum. (Note: when adding two numbers the carry over can only be 1 or 0.)

We can apply a programmatic approach to the pseudo-algorithm above. If we write an integer as a string, then the last digit of the string will represent the units digit. Since C# uses 0 based indexing, the maximum index is the Length property less 1. We will loop through all the digits of both numbers, starting at with length – 1 index (unit) of each. We have to account for different lengths of numbers, so we will capture the maximum length of the numbers. During iteration, if the count of the current digit exceeds the length of the smaller number, 0 will be assigned to the smaller number’s digit. The carry over will be assigned a value of 1 or 0 for each set of digits depending on if the current sum is greater than 9.

A proposed method looks like the following. Some liberties with verbosity have been taken to ensure readability.

static string AddVeryLongNumbers(string x, string y)
{
  string result = "";

  int xMaxIndex = x.Length - 1;
  int yMaxIndex = y.Length - 1;

  int maxLength = x.Length > y.Length ? x.Length : y.Length;

  int carryOver = 0;

  for (int i = 0; i < maxLength; i++) 
  { 
    var xIndex = xMaxIndex - i; var yIndex = yMaxIndex - i; var xUnit = xIndex >= 0 ? getDigitFromXAtIndex(x, i) : 0;
    var yUnit = yIndex >= 0 ? getDigitFromXAtIndex(y, i) : 0;

    var naturalSum = carryOver + xUnit + yUnit;

    if (i < maxLength - 1) { result = (naturalSum % 10).ToString() + result; carryOver = (naturalSum / 10) > 0 ? 1 : 0;
    }
    else
    {
      result = naturalSum.ToString() + result;
    }
  }
  return result;
}
private static int getDigitFromXAtIndex(string x, int y)
{
  return Convert.ToInt32(x[x.Length - 1 - y].ToString());
}

100,000 tries of adding two numbers with 61 significant digits with this method executes in 2.6432 seconds. The next post in this series will focus on multiplication and exponential operations of very large integers. Armed with such operations, we will be able to explore combinatorics on a more interesting scale without the need for advanced knowledge of mathematics or programming.