In the last two articles, we have implemented two VBA functions for adding and subtracting two large numbers represented as strings. Now, it’s time to implement a function able to multiply two large numbers in a very fast way.
The used algorithm for this purpose is the “Karatsuba algorithm”. I had already written an article about this algorithm on my blog on my software website, but I had not transferred the article to this blog. So, firstly some few words about the algorithm.
Functioning of the Karatsuba Algorithmus
The basic idea of this algorithm is to replace multiplications by additions and subtractions and using shift operations. This method leads to a significant reduction of the needed partial multiplications. The principle behind this algorithm is named “divide and conquer”. And the method can also be easily used in recursions. If you browse the net, you will quickly find the more performing algorithm from Schönhage-Strassen, which is based on recursive Fast Fourier transforms. However, this algorithm is more difficult to implement in VBA and the Karatsuba fast enough for our purposes.
The figure above shows two large numbers X and Y for being multiplied by using the algorithm. I have intentionally added a blank in the middle of the numbers for better visualizing the steps.
In a first step, the greatest length of the two numbers is retrieved, in this case for X having 20 digits. Then, zeros are prepended to the shorter number for getting both numbers with the same length. In case the maximal length is odd, we have to add one dummy digit, as we will divide the length by two.
Now, we divide the numbers in 4 parts, each having a length of 10 digits. For example, the results are for X the values X_Left = X_L = 9876256719 und X_Right = X_R = 8712349865.
The Karatsuba algorithm states that the three partial multiplications P_1, P_2 and P3 may be calculated. P_1 equals to X_Left * Y_Left and P_2 equals to X_Right * Y_Right. Before we can calculate P_3, we have to calculate the sums of the left and right parts for X and Y. This means, P_3 equals to (X_Left + X_Right) * (Y_Left + Y_Right).
Once the partial multiplications have been calculated, we can reassemble the parts for getting the result for X * Y. The formula is: Result = P_1 * 10 ^ N + (P_3 – P_2 – P1) * 10 ^ (N/2) + P_2, where N is the maximal length computed before; in our sample 20 digits.
As you have certainly noticed, the algorithm includes a subtraction and some additions. These are the parts where we will use our functions from our previous articles. The multiplications included in the algorithm will be done by recursively call the multiplication function implemented here. So, for calculation X_Left * Y_Left we will make the same steps as for X * Y. The recursion will take place until the numbers are so small, that we can use a normal simple multiplication.
Multiplication of large numbers in Excel
Let’s have a look on the code. In a first step, we store the maximal length of the lengths of the arguments “x” and “y” in the variable “lngLength”. Then we check if the sum of the lengthy for “x” and “y” is smaller than a length can be done with a simple multiplication.
If the simple multiplication is not applicable or fails, then we check if the length can be divided by two. If not, we replace the length by length + 1. Now the arguments can be split into the parts and stored in the variables strArgs_X_L, strArgs_X_R, strArgs_Y_L and strArgs_Y_R. At the same time, we prepend zeros, if necessary.
As we later need the sums of the left and rights parts for “x” and “y” for use in P_3, we calculate the by calling the function “mlfhAdd(…)” and store the results into the variables strTemp_A_1 and strTemp_A_2.
Then, we can calculate the values for P_1, P_2 and P_3 as described before. This is done by recursively calling “mlfhMultiply(…)“, meaning our Karatsuba algorithm. Finally we compute the last formula for getting our result.
That’s all. The next article will present a function for performing an exponentiation and therefore compute the result of 80 ^200, the original problem. Lastly some links providing more information, which may be from interest.