|
Karatsuba Algorithm is a fast multiplication algorithm that efficiently multiplies large numbers by recursively breaking them down into smaller parts.
Examples:
Input: A = 5678 B = 1234
Output: 7006652
Input: A = 1456 B = 6533
Output: 9512048
Using the Naive approach, we can multiply two numeric strings in O(N2) time where N is the length of the strings. A better approach would be to used Karatsuba Algorithm to compute the product in O(N1.59) time.
Working of Karatsuba Algorithm:Assuming that n is the power of 2, rewrite the n-digit numbers in the form of −
A = Al * 10n/2 + Ar [Al and Ar contain leftmost and rightmost n/2 digits of A]
B = Bl * 10n/2 + Br [Bl and Br contain leftmost and rightmost n/2 digits of B]
Therefore, the product A * B can also be represented as follows:
A * B = (Al * 10n/2 + Ar) * (Bl * 10n/2 + Br)
= 10n*Al*Bl + 10n/2* (Al*Br + Bl*Ar) + Ar*Br
= 10n*Al*Bl + 10n/2*((Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br) + Ar*Br [since Al*Br + Bl*Ar = (Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br]
Let us solve 5678 × 1234 using Karatsuba method:
That gives us,
1456 * 6533 = ((14) * 102 + 56) * ((65) * 102+ 33)
= (104 * 14 * 65) + 102 * (14 * 33 + 65 * 56) + 56 * 33
= (104 * 14 * 65) + 102 * ((14 + 56) * (65 + 33) – 14 * 65 – 56 * 33) + (56 * 33)
= 9100000 + 100 * (70 * 98 – 14 * 65 – 56 * 33) + 1848
= 9100000 + 100 * (6860 – 910 – 1848) + 1848
= 9100000 + 410200 + 1848
= 9512048
Implementation of Karatsuba Algorithm in Python:Below is the implementation of Karatsuba Algorithm in Python:
Python
import re
# Function to find the sum of larger
# numbers represented as a string
def findSum(str1, str2):
if len(str1) > len(str2):
str1, str2 = str2, str1
result = ""
n1, n2 = len(str1), len(str2)
str1, str2 = str1.zfill(n2), str2.zfill(n2)
carry = 0
# Perform addition digit by digit from the right
for i in range(n2 - 1, -1, -1):
sum_val = (int(str1[i]) - 0) + (int(str2[i]) - 0) + carry
result = str(sum_val % 10 + 0) + result
carry = sum_val // 10
if carry:
result = str(carry + 0) + result
return result
# Function to find the difference of larger
# numbers represented as strings
def findDiff(str1, str2):
result = ""
n1, n2 = len(str1), len(str2)
str1, str2 = str1.zfill(n2), str2.zfill(n2)
carry = 0
# Perform subtraction digit by digit from the right
for i in range(n2 - 1, -1, -1):
sub = (int(str1[i]) - 0) - (int(str2[i]) - 0) - carry
if sub < 0:
sub += 10
carry = 1
else:
carry = 0
# Append the digit to the result
result = str(sub + 0) + result
return result
# Function to remove all leading 0s
# from a given string
def removeLeadingZeros(s):
pattern = "^0+(?!$)"
s = re.sub(pattern, "", s)
return s
# Function to multiply two numbers
# using the Karatsuba algorithm
def multiply(A, B):
# Base case for small numbers: perform normal multiplication
if len(A) < 10 or len(B) < 10:
return str(int(A) * int(B))
n = max(len(A), len(B))
n2 = n // 2
# Pad the numbers with leading zeros to make them equal in length
A = A.zfill(n)
B = B.zfill(n)
# Split the numbers into halves
Al, Ar = A[:n2], A[n2:]
Bl, Br = B[:n2], B[n2:]
# Recursively compute partial products and sum using Karatsuba algorithm
p = multiply(Al, Bl)
q = multiply(Ar, Br)
r = multiply(findSum(Al, Ar), findSum(Bl, Br))
r = findDiff(r, findSum(p, q))
# Combine the partial products to get the final result
return removeLeadingZeros(findSum(findSum(p + '0' * n, r + '0' * n2), q))
# Driver Code
if __name__ == "__main__":
A = "1456"
B = "6533"
# Multiply the large numbers A and B using the Karatsuba algorithm
print(multiply(A, B))
Time Complexity: O(Nlog 3) or O(N1.59), where N is the maximum among the lengths given strings A and B.
Auxiliary Space: O(N2)
|
Interpolation Search in Python
Linked List of Linked List