Karatsuba algorithm with Excel VBA 15.04.2009Someone posted in
my favorite german office forum - - 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