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.