Using the idea of divide and conquer and recursion, the traditional integer multiplication is decomposed. Also introduce Karatsuba, how it reduces the number of basic multiplication operations.
One, Primary School Multiplication
?? For example, x=5678, y=1234, multiplication of these two integers is equivalent to For each bit of x, the loop body multiplies the current bit of x with y, and if necessary, generates a carry. The result obtained is shifted by the corresponding number of bits to the left according to the position of the bit in x (equivalent to adding 0 at the end), Add all the results obtained to the final result. Each loop performs 4 multiplications and no more than 4 additions. Therefore, the number of basic operations performed in the loop body is set to 2n (n is the number of digits), then a total of n loops and several additions after the loop ends, so the number of operations performed is approximately It is 2n2. Using Big O notation, the time complexity should be O(n2).
Two, RecIntMult algorithm
?? The same for two n-bit integers x and y. Another representation can be used:
x = 10(n / 2) * a + b
y = 10(n / 2 ) * c + d
x * y = (10(n / 2) * a + b) * (10(n / 2) * c + d)
??? = 10(n) * (a * c) + 10(n / 2) * (a * d + b * c) + b * d
?? where a and c are equivalent to the first n/2 digits of x and y, and b and d are the last n/2 digits of x and y (Assuming n is an even number). Therefore, x * y is converted into a * c, a* d, b * c, b * d four multiplication operations and several addition operations (here multiplication 10(n) is equivalent to the first part) Move left operation). For the four multiplication operations after decomposition, if their digits are greater than 1, then they can continue to be decomposed, and when they are decomposed to one digit, a simple ones digit multiplication can be performed.
?? Assuming that x and y are both four-digit integers, we use a function to express the number of times it performs multiplication, then f(4) = 4 * f(2), f(2) = 4 * f (1), f(1) = 1, then f(4) = 16. It is not difficult to find that the number of n-digit integer multiplication operations is equal to 4 times the number of n/2-digit integer multiplication operations, and recursively down until n = 1, at which time the number of multiplication operations is 1. That is to say, n is divided by 2 until the result is equal to 1, then n is divided several times by 2 and there are several 4 multiplications, then the mathematical formula is expressed as f(n) = 4(log2n). Using Big O notation, the time complexity is O(4(log2n)) = O(n(log2 4)) = O(n2), so the divide-and-conquer algorithm in this way just decomposes the first method into many small integer multiplications, and does not reduce the number of multiplication operations.
Three, Karatsuba algorithm
?? Although the RecIntMult algorithm converts large integers x and y into two-part small integers for calculation, each part Will multiply all parts of another number, so every digit of x will be multiplied by every digit of y, so the actual number of multiplications must be n2.
?? And the idea of Karatsuba algorithm is as follows:
(a + b) * (c + d)-a * c-b * d = a * d + b * c< br> ?x * y = 10(n) * (a * c) + 10(n / 2) * (a * d + b * c) + b * d
???? = 10(n) * (a * c) + 10(n / 2) * ((a + b) * ( c + d)-a * c-b * d) + b * d
?? Karatsuba formula may become longer, but the multiplication of x and y is actually decomposed into a * c, (a + b) * (c + d), b * d three multiplication operations. Although the first step converts a * d + b * c into three multiplication operations, the last two multiplication operations use the calculated results, so the actual calculation of a * d + b * c only requires one multiplication operation. This is also the key for Karatsuba to reduce the number of multiplication operations.
?? Then Karatsuba performs multiplications for n-bit integers as f(n) = 3 * f(n / 2), so the time complexity is actually O(3(log2n)) = O(n(log23)) = O(n1.59)
?? Karatsuba algorithm uses recursion to achieve more performance consumption, when the number of integers is small, it is more efficient to use basic multiplication.