You are on the Home/Other Tutorials/Project Euler/Large Number Arithmetic page Share Your

# Large Number Arithmetic

Excel and VBA support numbers to a precision of some number of digits. The limit in Excel is 15 significant digits in a number. Enter a 16 digit credit card number and 1234567890123456 will become 1234567890123450. The limit in VBA depends on the data type. Among the common numeric data types Integer, Long, Single, and Double, a variable of type Long can store a number from -2,147,483,648 to 2,147,483,647 whereas a Double data type supports 15 digits of precision: -1.79769313486231E308 to -4.94065645841247E-324 for negative values; 4.94065645841247E-324 to 1.79769313486232E308 for positive values.

Two data types that are not-so-common are Currency and Decimal. The Currency data type stores 19 digits of precision with numbers ranging from -922,337,203,685,477.5808 to 922,337,203,685,477.5807 and the Decimal data type stores 29 digits of precision. From the VBA help file:
"+/-79,228,162,514,264,337,593,543,950,335 for zero-scaled numbers, that is, numbers with no decimal places. For numbers with 28 decimal places, the range is +/-7.9228162514264337593543950335. The smallest possible non-zero number is 0.0000000000000000000000000001."

So, how does one work with numbers that are longer than the longest supported number? The only way to store such a number is as text (a String variable in VBA). To store all 16 characters of a credit card in an Excel cell, first select a cell and set the format to Text. Now, enter the 16 characters of the credit card, i.e., 1234567890123456. Excel will show all 16 characters.

This is good as far as it goes. Unfortunately, since the cell contains text (see the test for ISNUMBER in the below image), it cannot be used for calculation and if you do, Excel will automatically revert to its limit of 15 digits (again, see the image below). The same conceptual limit exists in VBA. Once we reach the limit for a particular data type, VBA will switch to a Double data type and continue to return results to a precision of 15 digits. For example, in the Visual Basic Editor, open the Immediate Window and enter ?2^49. The result will be 562949953421312. Now, enter ?2^50 and the result will be 1.12589990684262E+15, which is 112589906842620. But, that is not exactly accurate since the correct result is 112589906842624, something that requires 16 digits and unavailable in either the Long or the Double data type. One can extend the precision of the result with the use of the decimal data type. To calculate 2^95, use ?cdec(2^cdec(46))*2^cdec(49) to get 39614081257132168796771975168 or 29 digits of precision. But, anything more, i.e., 2^96, exceeds the limit of even the decimal data type, which is 2^96-1.

The only way to calculate results beyond this degree of precision is to build our own algorithms. The key to the algoritmns and associated VBA code will be to break large numbers into smaller numbers that return results within the limit of the decimal data type. Then, we reassemble the component results into the final complete result.

This is the basic building block since addition is a requirement for multiplication. And, it is the easiest to understand. We will look at a small problem to understand the concepts. Consider adding a 4 digit number to another 4 digit number with the requirement that we are not allowed to work with more than 2 digits at a time. So, we cannot directly add 1001 and 1002. Instead, we break the two numbers into 10 and 01 and 10 and 02 respectively, add the components together and put the result together to get 2003

10 01
10 02
-----
20 03

There are three issues to consider in this calculation. First, when we convert 01 and 02 to numbers, they become 1 and 2 and the result is 3, not 03. So, if the result of the addition is less than the length of the original number, we need to pad the result with leading zeros. The second issue is the length of the numbers. To keep matters simple, we will work on numbers of the same length. So, if one number is smaller than the other, we will pad it with leading zeros. The third issue to remember is the carry-over digit. When we add 9 and 9 we get 8 with a carry-over of 1. Consequently, the addition of the next significant digit must include this carry-over. When we get a carryover from the entire number, the carryover digit must be added to the next addition we do with the elements on the left of the numbers.

Here s an example incorporating all the rules. Suppose we want to add the numbers represented by the strings "906002" and "98501" and we can operate only 2 digits at a time. Since one number is smaller than the other, we pad it to the left to get 906002 + 098501.

Now, we look at the first 2 digits on the right. 02 + 01 becomes 3. But, since we started with 2 digits, we pad the result to get the partial result string of 03.

Next, adding 60 and 85 yields 45 with a carry-over of 1. The partial result string is now 4503.

Next, the next addition applies to 90 and 09. We add the carry-over from the previous addition to get 00 with a another carry-over of 1 and a partial result string of 004503.

Finally, since we are at the end of the addition process we simply put the carryover 1 at the left of the result string to get the final result 1004503.

The LargeAdd function implements the same concept except that it works with 28 digit numbers (1 less than the Decimal data type s limit of 29 digits). But, before we get to the implementation of the addition function, we need some constants. The reason for the quotes is that we cannot declare a constant of the data type Decimal. So, we must use an initialization routine to create the constants. If we were creating a class for Large Arithmetic, the below would be the class_initialize code. In addition, the corresponding 3 properties would have just the Get procedures, essentially making them ReadOnly properties. We will use the first two constants in the addition process. The third, cSqrDecMaxLen, is required for the multiplication routine.

```Option Explicit

Public cDecMax As Variant, cDecMaxLen As Integer, cSqrDecMaxLen As Integer

Public Sub Initialize()
Static Initialized As Boolean
If Initialized Then Exit Sub
Initialized = True
cDecMax = _
CDec(Replace("79,228,162,514,264,337,593,543,950,335", ",", ""))
'this is 2^96-1
cDecMaxLen = Len(cDecMax) - 1
cSqrDecMaxLen = cDecMaxLen \ 2
End Sub```

With this initialization code in place, we can now write the LargeAdd function. If both its arguments fit in the decimal data type, it does the addition and returns. If not, it uses the AddByParts routine to do the needful.

```Function Ceil(X As Single) As Long
If X < 0 Then Ceil = Fix(X) Else Ceil = -Int(-X)
End Function

Private Function addByParts(ByVal Nbr1 As String, ByVal Nbr2 As String) _
As String
Dim NbrChunks As Integer
If Len(Nbr1) > Len(Nbr2) Then _
Nbr2 = String(Len(Nbr1) - Len(Nbr2), "0") & Nbr2 _
Else _
Nbr1 = String(Len(Nbr2) - Len(Nbr1), "0") & Nbr1
NbrChunks = Ceil(Len(Nbr1) / cDecMaxLen)
Dim I As Integer, OverflowDigit As String, Rslt As String
OverflowDigit = "0"
For I = NbrChunks - 1 To 0 Step -1
Dim Nbr1Part As String
Nbr1Part = Mid(Nbr1, I * cDecMaxLen + 1, cDecMaxLen)
Rslt = CStr(CDec(Nbr1Part) _
+ CDec(Mid(Nbr2, I * cDecMaxLen + 1, cDecMaxLen)) _
+ CDec(OverflowDigit))
If Len(Rslt) < Len(Nbr1Part) Then
Rslt = String(Len(Nbr1Part) - Len(Rslt), "0") & Rslt
OverflowDigit = "0"
ElseIf I = 0 Then
ElseIf Len(Rslt) > Len(Nbr1Part) Then
OverflowDigit = Left(Rslt, 1): Rslt = Right(Rslt, Len(Rslt) - 1)
Else
OverflowDigit = "0"
End If
Next I
End Function

Function LargeAdd(ByVal Nbr1 As String, ByVal Nbr2 As String) As String
Initialize
If Len(Nbr1) <= cDecMaxLen And Len(Nbr2) <= cDecMaxLen Then
Exit Function
End If
End Function```

## Multiplication of Large Numbers

The idea behind the multiplication of large numbers is similar to that used above in the sense that we implement in code, using strings and the decimal data type, how one does multiplication "by hand." Consider the multiplication of the 2 numbers 1002 and 1001. If we did it one digit at a time, we d get

```    1002
1001
----   1002  0000x 0000xx
1002xxx
-------
1003002```

If we did the multiplication 2 digits at a time, we d get

```    1002   1001   ----   1002
10020xx
-------
1003002
```

Essentially, we multiply the result of each partial multiplication by the powers of 10 of the previous multiplications. The easiest way to do that, of course, is to simply shift the result to the left by as many digits as the earlier powers of 10. In the first example, above, we shifted the result left by 1, 2, and finally, 3 digits in each partial multiplication. In the second example, since we were multiplying by 2 digits at a time, the shift is by 2 digits. The code below implements that concept except that it works on the Decimal data type. The limit for the number of digits in each multiplication ensures that the result fits in the Decimal data type (29 digits).

```Private Function factorOneNbr(ByVal LargeNbr As String, _
ByVal Nbr2 As String) As String
Dim NbrChunks As Integer, I As Integer, _
Nbr1Part As String, PowersOf10 As Integer, _
Rslt As String, FinalRslt As String
FinalRslt = "0"
NbrChunks = Ceil(Len(LargeNbr) / cSqrDecMaxLen) - 1
For I = NbrChunks To 0 Step -1
Nbr1Part = Mid(LargeNbr, I * cSqrDecMaxLen + 1, cSqrDecMaxLen)
Rslt = LargeMult(Nbr1Part, Nbr2)
FinalRslt = LargeAdd(FinalRslt, Rslt & String(PowersOf10, "0"))
PowersOf10 = PowersOf10 + Len(Nbr1Part)
Next I
factorOneNbr = FinalRslt
End Function
Function LargeMult(ByVal Nbr1 As String, ByVal Nbr2 As String) As String
Initialize
If Len(Nbr1) <= cSqrDecMaxLen And Len(Nbr2) <= cSqrDecMaxLen Then
LargeMult = CStr(CDec(Nbr1) * CDec(Nbr2))
Exit Function
End If
If Len(Nbr1) > cSqrDecMaxLen Then
LargeMult = factorOneNbr(Nbr1, Nbr2)
Else
LargeMult = factorOneNbr(Nbr2, Nbr1)
End If
End Function```

## Powers of Large Numbers

To calculate a number to a positive integer power one can simply multiply the number by itself that many times. The code below uses the LargeMult function from above to do just that.

```Function LargePower(ByVal Nbr As String, ByVal Power As Integer)
Dim I As Integer
LargePower = "1"
For I = 1 To Power
LargePower = LargeMult(LargePower, Nbr)
Next I
End Function```

## Factorials of Large Numbers

Given the LargeMult function above, factorials are relatively easy. After all, n! = 1*2* *(n-2)*(n-1)*n. By default, Excel can calculate 169! but fails at 170! The code below lets one extend the result to 32767!, though that might take a while to calculate. Calculating 1000! returns a result with 2,568 digits in just under 10 seconds.

```Function LargeFactorial(ByVal Nbr As Integer) As String
Dim I As Integer, StartTime As Single
'StartTime = Timer
LargeFactorial = "1"
For I = 1 To Nbr
LargeFactorial = LargeMult(LargeFactorial, I)
Next I
'Debug.Print Timer - StartTime
End Function```

## Using the Large functions in Excel

Each of the public functions above (LargeAdd, LargeMult, LargePower, and LargeFactorial) is usable from within VBA itself or as a user defined function (UDF) in Excel. Just keep in mind that the functions operate on strings that contain only numbers and that there are *no* safety checks in any of the functions. So, give any of them badly formatted arguments and the results will be unpredictable.

## Summary

This section introduces some key functions that work with numbers containing more digits that the precision of Excel even VBA. The current functions include LargeAdd, LargeMult, LargePower, and LargeFactorial.

## References

I don t have any first-hand knowledge of this site but I ran across it while searching Google for Excel and VBA large number arithmetic: http://www.precisioncalc.com/