This article is divided into 3 parts, so feel free to skip around to the part you find useful -
Need for the algorithm
Multiplication is an elementary concept known to all of us since a very early age. But multiplication of very large numbers becomes a difficult problem that can't be solved mentally unless you're a mathematical genius and hence we use calculators and computers.Computers too can efficiently multiply numbers but as the length of digits of the number increases, the time complexity also increases along with it quadratically.
To calculate the product of humongous numbers we need a better algorithm. Any algorithm that even slightly increases the runtime will prove to be very beneficial for large values of n, say 100000. Karatsuba multiplication algorithm brings down the number of operations by a factor of one and gives a huge boost.
Intuition and Algorithm
Okay so, to boost up the speed of multiplication we can use the distributive law.Split the numbers into two parts and then multiply them. To demonstrate this we will take an example,
To multiply two numbers, u = 82 and v = 73, we can divide them both in the following way -
u = 8 * 10 + 2
v = 7 * 10 + 3
We can see a general form -
u = x * 10 + y
v = w * 10 + z
u * v = (x * 10 + y) * (w * 10 + z)
u * v = xw * 102 + xz * 10 + yw * 10 + yz
Now if we plug in the values,
82 * 73 = (8*7) * 100 + (8*3) * 10 + (2*7) * 10 + (2*3)
This will give us the result 5986.
This algorithm involves 4 basic multiplication operation. We can ignore anything multiplied by 10 to the power something as it is just a matter of appending 0s. This approach still gives us a time complexity of O(n2) which is same as the conventional grade school approach inspite of doing a lot of work.
Karatsuba multiplication reduces the number of multiplications to 3 which gives us a time complexity of O(nlog3) which is O(n1.58). This may not seem as a huge improvement upfront but even this little improvement saves a lot of time for large values of n.
So in Karatsuba multiplication we calculate,
p1 = x * w
p2 = y * z
p3 = (x + y) * (w + z)
p3 = xw + xz + yw + zy
We can see that we already know the value of xw and yz, hence, we can easily compute xz + yw by subtracting p1 and p2 from p3.
m = p3 - p2 - p1
This allows us to get all the essential values with just 3 basic multiplications rather than 4.
The product now will be given as,
If n is the length of number,
product = 10n * p1 + 10n/2 * m + p2
Implementation
For simplicities sake, this implementation assumes that both the numbers are of same length and the length of digits is only even.Surprisingly, my implementation works perfectly for 2 digit numbers and to some extent for four digit number, i.e. it's giving wrong output for multiplications like 8344 * 4245 but gives the correct output for multiplication 4443 * 4245.
Top Online Casino Site in Indonesia - ClickOrCasino
ReplyDeleteCheck out our reviews on the online casino sites and get the 메리트카지노 best gaming experience. 바카라 ClickorCasino is one of 카지노사이트 the best online casinos in Indonesia!