Karatsuba algorithm with Excel VBA
15.04.2009
Someone posted in my favorite german office forum - Office-Lösung - a new game:“Let's multiply, starting with 2, the result with itself and so on”.
Have you ever tried to multiply large numbers in Excel? Well, Excel uses a number precision of 15 digits, beyound the numbers are rounded. Thus, formulas are not suitable. Can VBA do the job? Yes, but only partially since the data types are restricted too. In addition, we have also to consider the computing time for multiplying large numbers.
If you search the Internet, you’ll quickly find some interesting procedures for multiplying large numbers. One of them is the “Karatsuba algorithm” which significantly reduces the multiplication of two n-digit numbers. The algorithm replaces some multplications by additions.
And how does it work? The basic step of Karatsuba's algorithm is a formula that allows us to compute the product of two large numbers using three multiplications of smaller numbers plus some additions and digit shifts. The Karatsuba algorithm is an example of the “divide and conquer” algorithm which works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly.
Example
Let’s imagine that we want multiply the numbers 123456789 and 98765. The result will be 12193258259412. First, we note that the two numbers have different numbers of digits (9 and 5 digits). So, let’s first prepend some zeros to the two numbers:
Number_1 = 0123456789 Number_2 = 0000098765As surely noticed, I also prepended to Number _1 one zero. Both have now 10 digits, this number can be easily divided by 2. Now, we split the numbers into for 5 digits long numbers:
Number_1_1 = 01234 and Number_1_1 = 56789 Number_2_1 = 00000 and Number_2_2 = 98765If we assume that N equals to 5, we can use following procedure to compute our base numbers:
Number_1 = Number_1_1 * 10 ^ N + Number _1_2 Number_2 = Number_2_1 * 10 ^ N + Number _2_2In our example:
Number_1 = 01234 * 10 ^ 5 + 56789 = 0123456789 Number_2 = 00000 * 10 ^ 5 + 98765 = 0000098765The algorithm initially performs three sub-products, which obey the following rule:
P_1 = Number_1_1 * Number_2_1 P_2 = Number_1_2 * Number_2_2 P_3 = (Number_1_1 + Number_1_2) * (Number_2_1 + Number_2_2)In our example:
P_1 = 01234 * 00000 = 0 P_2 = 56789 * 98765 = 5608765585 P_3 = (01234 + 56789) * (00000 + 98765) = 5730641595At this point, we can use the same rule for calculating P_1, P_2 and P_3. A computer program can perform this task recursively. At the end we should obtain small numbers which we can normaly multiply.
What's missing is the calculation rule to re-assemble the numbers:
Result = P_1 * 10 ^ 2N + (P_3 - P_2 - P_1) * 10 ^ N + P_2You will get exactly 12193258259412 for our example, which corresponds to the desired result.
Implementation in VBA
As mentionned above, we can’t use the data types Long or Double for multiplying large numbers. So we’ll have to use strings and implement by ourself operators for adding and subtracting. Let’s have a look on the code below:
Public Function mlfpKaratsuba(First As String, Second As String) As String
Dim a As String
Dim b As String
Dim c As String
Dim d As String
Dim r As String
Dim x As String
Dim y As String
Dim z As String
Dim n As Long
Dim p As Long
' Length...
n = mlfhMax(Len(First), Len(Second))
n = n + n Mod 2
n = n / 2
' Check...
If n < 2 Then
' Return...
mlfpKaratsuba = CStr(CLng(CStr(0) & First) * _
CLng(CStr(0) & Second))
' Exit..
Exit Function
End If
' Decompose...
If 2 * n > Len(First) Then
a = Left(String(2 * n - Len(First), CStr(0)) & First, n)
b = Right(First, n)
Else
a = Left(First, n)
b = Right(First, n)
End If
If 2 * n > Len(Second) Then
c = Left(String(2 * n - Len(Second), CStr(0)) & Second, n)
d = Right(Second, n)
Else
c = Left(Second, n)
d = Right(Second, n)
End If
' Recurse...
x = mlfpKaratsuba(a, c)
y = mlfpKaratsuba(b, d)
z = mlfpKaratsuba(mlfhAdd(a, b), mlfhAdd(c, d))
' Calculate...
a = x & String(2 * n, CStr(0))
b = mlfhAdd(y, x)
b = mlfhSubstract(z, b)
b = b & String(n, CStr(0))
' Result...
r = mlfhAdd(a, b)
r = mlfhAdd(r, y)
' Return...
mlfpKaratsuba = r
End Function
In a first step, we calculate the numbers of digits for our two parameters 'First' and 'Second' which are representing our numbers to multiply. Then we compute n, which must be dividable by two. After prepending an appropriate number of zeros to our parameters, we recursively call the Function mlfpKaratsuba() for calculating P_1, P2 and P3 (x, y and z in our code). The functions mlfhAdd() and mlfhSubstract() respectively add and substract numbers represented as strings.To calculate the result, we must remember that the calculation also contains string addi-
tions and subtractions. The high potency of 10 ^ N can be simply made by appending zeros.
You can download our sample project file from our download area. The code writes the results in text files located in the same directory as the workbook.
» Karatsuba algorithm on Wikipedia
» University of Aachen, Germany, German article
» Professor Anatolii Alexeevitch Karatsuba
» Multiplication algorithm on Wikipedia
Blog
News
