I made a program to multiply two strings and I expected 1000*10 = 10000
, but I am getting 100000
. I don't know where my logic is wrong. I also tried replacing m2
with m1
in the expression ((val3 val4) * 10**(m2))
but nothing works, and when I try to multiply 120 * 10
, I get 300
.
def Multiply_Recursive(a, b):
if len(a) == 1 or len(b) == 1:
return str(int(a)*int(b))
else:
m = max(len(a),len(b))
m2 = m // 2
m1 = len(b) // 2
A = int(a[0:m2])
B = int(a[m2:len(a)])
C = int(b[0:m1])
D = int(b[m1:len(b)])
val1 = int(Multiply_Recursive(str(A),str(C)))
val2 = int(Multiply_Recursive(str(B),str(D)))
val3 = int(Multiply_Recursive(str(A),str(D)))
val4 = int(Multiply_Recursive(str(B),str(C)))
return str(val1 * 10**(2*m2) ((val3 val4) * 10**(m2)) val2)
num = Multiply_Recursive("1000","10")
print(num)
CodePudding user response:
In the final formula you assume that m2
digits occur at the right of the split point, and that this number of digits is the same for both splits. Neither is generally true.
Also, as the definition of m
depends on the larger input, it could lead to an out-of-range number of digits represented by m2
, when a
is much smaller than b
.
You could fix this like this:
Define
m2
like this:m2 = len(a) // 2
Split the input in such a way that
m1
andm2
are the number of digits after the split point, not before. So split like this:A = int(a[:-m2]) B = int(a[-m2:]) C = int(b[:-m1]) D = int(b[-m1:])
Change the final formula taking into account that
m1
andm2
can be different. So for instance there should not be2*m2
, butm1 m2
, ...Etc:return str(val1 * 10**(m1 m2) val3 * 10**m2 val4 * 10**m1 val2)
The real Karatsuba algorithm will make sure to choose m1
and m2
so they are the same, and it will not convert strings to integer unless it is certain the size of the strings is limited. It also needs one less recursive call.
CodePudding user response:
The naming is not helpful - just using ah, al, bh, bl:
def multiply_recursive(a, b):
""" Return the product of a and b.
All numbers are passed as their decimal string representations.
"""
if not a or not b:
return "0"
if len(a) == 1 or len(b) == 1:
return str(int(a)*int(b))
#
m = max(len(a), len(b))
m2 = m // 2
# different split points not suitable for common scaling of "mixed products" below
# m1 = len(b) // 2
# low parts are remainders: split from least significant end!
ah = a[0:-m2]
al = a[-m2:].lstrip("0")
bh = b[0:-m2]
bl = b[-m2:].lstrip("0")
# print(ah, al, bh, bl, sep=',')
ahbh = int(multiply_recursive(ah, bh))
albl = int(multiply_recursive(al, bl))
ahbl = int(multiply_recursive(ah, bl))
albh = int(multiply_recursive(al, bh))
product = str(ahbh * 100**m2 (ahbl albh) * 10**m2 albl)
# print(product)
return product
num = multiply_recursive("1000","10")
print(num)