Some time ago, there was a very interesting discussion in my favorite German “Office-Lösung” Office forum. A user asked, if it is possible to calculate the value of 80 ^ 200 in Excel. As the precision is limited in Excel to 15 digits, using an Excel formula will lead to result which will be cut from the 16th digit. And, because the default data types in VBA are also limited by their range of values, a simple function in VBA will not work.
Heinz Schweigert, a User of the forum, had the idea if to use my implementation of the Karatsuba algorithm for the calculation of 80 ^200. My application uses strings for representing large numbers and therefore bypasses the limitations mentioned before. And the number of partial multiplications needed for multiplying two large numbers is significantly reduced by the use of the Karatsuba algorithm.
However, the code of my application was originally designed for multiplying large numbers by themselves. But Heinz had fortunately created a customized version of my code for performing an exponentiation and provided the changes to the forum.
This article is the first one of my article series about the implementation in VBA of the base arithmetic functions for large numbers. Then I will put all functions together and create an Excel Add-In, which will be downloadable from this site. And, if I got the time, I will extend the Add-In by new features or more functions in the future. By the way, my goal is not to compute gigantic numbers or beat some speed records but just only to provide fast enough functions for calculating large numbers and being used for normal requirements.
Addition of large numbers in Excel
This article series starts with a function for adding two large numbers. At this point, thanks again to Heinz for providing some ideas for improving my original functions.
As mentioned before, I am using the Karatsuba algorithm for multiplying two large numbers. This algorithm also uses additions; therefore we need a function able to add two numbers represented by strings. The original version of my code performed this addition by adding each digit from right to left. This works fine, but, if we have two strings with a length of 500 digits, the loop will take at least 500 steps.
Many steps can be saved if we firstly split the two numbers in blocks and then add the blocks using the default VBA addition function. For example, if we set the block length to 10 digits, we will reduce the loop to 50 steps.
The figure above shows the logic for two large numbers X and Y. And the sample assumes that the length of one block is 4 digits. As you can see, if we add “2356” and “8574”, we obtain “10930”. The length of the result exceeds in this case the block length and is greater than “9999”. So we may carry to the next block. For example, we then get for the next block “1245 + 2364 = 3609 + 1 = 3610”. As you can see, the logic is relatively simple; let’s have a look on the code:
In a first step, we have to check the arguments “x” and “y” for their lengths and store the greatest length in the variable “lngLength”. The variable “lngPrecision” is corresponding to our block length and either being calculated or set to the maximal block length (defined as constant and set to 10 digits).
For ensuring that we will not run into an error and that the length is divisible by 2, we prepend leadings zeros to our original arguments. After that, we have just to enter the loop for adding each block and, if necessary, consider the carry. The result is store in “strResult”.
Finally we remove all unnecessary leading zeros from the result. That’s all. The next article will present a function for performing a subtraction of two large numbers.