What is Karatsuba Approach for efficient polynomial Multiplication?
Introduction
Polynomial multiplication is a basic concept which is taught to the students since their school life. But, it is very important topic when it comes to computer science field, as in algorithms, is we are supposed to design an algorithm for this polynomial multiplication, then, definitely we all were a simple algorithm which will have a time complexity of O(N² ).
Simple Algorithm of time complexity of O(N²)
The simple algorithm will look like this:
- We have 2 polynomials of of degree (n-1) each.
- Take an array of size 2n-2.
- Run 2 for loops, each will run through 0 to n-1.
- we assign final product array like this, p[i + j] = A[i] * B[j].
Some Improvement in Algorithm
The improvement is that divide and conquer approach was used to solve the problem. Steps are as follows:
- Divide each polynomial in 2 halves: upper and lower.
- For first polynomial we denote upper and lower halves with D1 and D0 respectively. For second polynomial we denote the same by E1 and E0.
- Upper half of each polynomial is in the form: a1* x ^ (n/2 -1) + a2 * x ^ (n/2-2) + ……., where a1, a2…. are coefficients of each term, and are actually like a ((n-1) in subscript), a((n-2) in subscript) and goes till a(n/2 in subscript).
- Lower half of each polynomial is in the form: a1* x ^ (n/2 -1) + a2 * x ^ (n/2–2) + ……., where a1, a2…. are coefficients of each term, and are actually like a ((n/2 -1) in subscript), a((n/2-2) in subscript) and goes till a(0 in subscript).
- Now, to obtain the final multiplied polynomial, we have to do, ( (E1*D1) * (x^n) + (E1*D0 + E0*D1) * (x ^ n/2) + E0D0) < = it represents the final multiplied polynomial.
- Here, we divided the polynomial in the 4 sub problems. So, its recurrence relation will be T(n) = 4*T(n/2) + cn, where c is constant.
- After solving the above relation we get Time complexity as O(N²), at each level the work is 4^i *c * T( n/(2 ^ i) ) => 2 ^i * c * T(n). The algorithm goes till log2(n) levels. Therefore work is c * 4 ^ log2(n) = c * n ^log2(4) = O(N²) [by log property]. [c is constant amount of work]
So, even after so much work, Time Complexity didn’t reduced. After this karatsuba done something to reduce it, and that something is given below.
Karatsuba Algorithm
The above mentioned time complexity was improved by Karatsuba in 7 days, he design an algorithm which leads to the time complexity of O(N ^1.58), which is a very significant improvement.
Get Harshit Dawar’s stories in your inbox
Join Medium for free to get updates from this writer.
He provided the formula to be ( (E1*D1) * (x^n) + ((E1 + E0) * (D0 + D1) - (D1*E1) - (D0*E0)) * (x ^ n/2) + E0D0) < = it represents the final multiplied polynomial.
The above formula contains only 3 multiplications, due to which time complexity of the problem reduces, as at each level the work is 3^i *c * T( n/(2 ^ i) ) => (3/2) ^ i * c * T(n). The algorithm goes till log2(n) levels. Therefore work is c * 3^ log2(n) = c * n ^log2(3) = O(N ^ 1.58) [by log property]. [c is constant amount of work]
I hope the content was simple enough to understand, and it gives you some interesting information!
