Karotsuba 乘法 - 找不到错误
Karotsuba multiplication - cannot find the error
我正在学习斯坦福大学的算法 MOOC,但遇到了 Karatsuba 乘法算法编程作业。
Karatsuba 乘法只是一种用于两个整数相乘的算法,它比通常的乘法渐近地快。
限制
- 我限制自己只使用个位数乘法和填充数(在末尾加零,即乘以 10 的某个次方),所以有 3 个基本情况
- 我还决定将数字转换为字符串并取几个数字而不是将其除以 10 的某个幂,但我尝试了另一种方法,它没有帮助
- 我还决定推广该算法,即不要假设 number1 和 number2 的长度相似,因此我同时使用 n1 和 n2(参见代码)
- 因为以上几点,我也决定不使用高斯的技巧
我知道,这些限制可能看起来毫无意义,但我将其用作编程练习而不是一些实际的解决方案,因此我主要感兴趣的是发现我的错误而不是寻找一些“更简单的解决方案”。
这是我的代码:
def karatsuba(number1, number2):
n1 = len(str(number1)) # number of digits in the first number
n2 = len(str(number2)) # number of digits in the second number
if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
kara = number1*number2
return kara
elif n1 == 1: # base case number 2 - only one number is single-digit
c = int(str(number2)[:(n2//2)])
d = int(str(number2)[(n2//2):])
kara = 10**((n2+1)//2)*c*number2 + d*number2
return kara
elif n2 == 1: # base case number 3 - only one number is single digit
a = int(str(number1)[:(n1//2)])
b = int(str(number1)[(n1//2):])
kara = 10**((n2+1)//2)*a*number2 + b*number2
return kara
elif n1 != 1 and n2 != 1: # loop
a = int(str(number1)[:(n1 // 2)])
b = int(str(number1)[(n1 // 2):])
c = int(str(number2)[:(n2 // 2)])
d = int(str(number2)[(n2 // 2):])
z1 = karatsuba(a, c)
z2 = karatsuba(a, d)
z3 = karatsuba(b, c)
z4 = karatsuba(b, d)
kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
return kara
这不是 Karatzuba 算法。 Karatzuba 的重点是只进行 3 次递归调用;你做了其中的 4 个。在你的符号中,递归调用应该是
karatzuba(a, c)
karatzuba(b, d)
karatzuba(a + b, c + d)
除此之外,基本情况 2 存在问题:number1
根本不参与。
这些是一些错误,如果您还没有纠正的话。
kara = 10**((n2+1)//2)*c*number1 + d*number1 #in base case 2
kara = 10**((n1+1)//2)*a*number2 + b*number2 #in base case 3. your code has n2+1
传统的 Karatsuba 有 3 个递归。但我明白你为什么要进行 4 次递归。虽然不能说哪个更快。
您在上面的评论中给出的示例的工作代码
def karatsuba(number1, number2):
n1 = len(str(number1)) # number of digits in the first number
n2 = len(str(number2)) # number of digits in the second number
if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
kara = number1*number2
return kara
elif n1 == 1: # base case number 2 - only one number is single-digit
c = int(str(number2)[:(n2//2)])
d = int(str(number2)[(n2//2):])
kara = 10**((n2+1)//2)*c*number1 + d*number1 #a mistake here
return kara
elif n2 == 1: # base case number 3 - only one number is single digit
a = int(str(number1)[:(n1//2)])
b = int(str(number1)[(n1//2):])
kara = 10**((n1+1)//2)*a*number2 + b*number2 #a mistake here
return kara
elif n1 != 1 and n2 != 1: # loop
a = int(str(number1)[:(n1 // 2)])
b = int(str(number1)[(n1 // 2):])
c = int(str(number2)[:(n2 // 2)])
d = int(str(number2)[(n2 // 2):])
z1 = karatsuba(a, c)
z2 = karatsuba(a, d)
z3 = karatsuba(b, c)
z4 = karatsuba(b, d)
kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
return kara
num1 = 3141592653589793238462643383279502884197169399375105820974944592
num2 = 2718281828459045235360287471352662497757247093699959574966967627
k_res = karatsuba(num1,num2)
ac_res = num1*num2
print(k_res)
print(ac_res)
assert k_res==ac_res
我正在学习斯坦福大学的算法 MOOC,但遇到了 Karatsuba 乘法算法编程作业。
Karatsuba 乘法只是一种用于两个整数相乘的算法,它比通常的乘法渐近地快。
限制
- 我限制自己只使用个位数乘法和填充数(在末尾加零,即乘以 10 的某个次方),所以有 3 个基本情况
- 我还决定将数字转换为字符串并取几个数字而不是将其除以 10 的某个幂,但我尝试了另一种方法,它没有帮助
- 我还决定推广该算法,即不要假设 number1 和 number2 的长度相似,因此我同时使用 n1 和 n2(参见代码)
- 因为以上几点,我也决定不使用高斯的技巧
我知道,这些限制可能看起来毫无意义,但我将其用作编程练习而不是一些实际的解决方案,因此我主要感兴趣的是发现我的错误而不是寻找一些“更简单的解决方案”。
这是我的代码:
def karatsuba(number1, number2):
n1 = len(str(number1)) # number of digits in the first number
n2 = len(str(number2)) # number of digits in the second number
if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
kara = number1*number2
return kara
elif n1 == 1: # base case number 2 - only one number is single-digit
c = int(str(number2)[:(n2//2)])
d = int(str(number2)[(n2//2):])
kara = 10**((n2+1)//2)*c*number2 + d*number2
return kara
elif n2 == 1: # base case number 3 - only one number is single digit
a = int(str(number1)[:(n1//2)])
b = int(str(number1)[(n1//2):])
kara = 10**((n2+1)//2)*a*number2 + b*number2
return kara
elif n1 != 1 and n2 != 1: # loop
a = int(str(number1)[:(n1 // 2)])
b = int(str(number1)[(n1 // 2):])
c = int(str(number2)[:(n2 // 2)])
d = int(str(number2)[(n2 // 2):])
z1 = karatsuba(a, c)
z2 = karatsuba(a, d)
z3 = karatsuba(b, c)
z4 = karatsuba(b, d)
kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
return kara
这不是 Karatzuba 算法。 Karatzuba 的重点是只进行 3 次递归调用;你做了其中的 4 个。在你的符号中,递归调用应该是
karatzuba(a, c)
karatzuba(b, d)
karatzuba(a + b, c + d)
除此之外,基本情况 2 存在问题:number1
根本不参与。
这些是一些错误,如果您还没有纠正的话。
kara = 10**((n2+1)//2)*c*number1 + d*number1 #in base case 2
kara = 10**((n1+1)//2)*a*number2 + b*number2 #in base case 3. your code has n2+1
传统的 Karatsuba 有 3 个递归。但我明白你为什么要进行 4 次递归。虽然不能说哪个更快。
您在上面的评论中给出的示例的工作代码
def karatsuba(number1, number2):
n1 = len(str(number1)) # number of digits in the first number
n2 = len(str(number2)) # number of digits in the second number
if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
kara = number1*number2
return kara
elif n1 == 1: # base case number 2 - only one number is single-digit
c = int(str(number2)[:(n2//2)])
d = int(str(number2)[(n2//2):])
kara = 10**((n2+1)//2)*c*number1 + d*number1 #a mistake here
return kara
elif n2 == 1: # base case number 3 - only one number is single digit
a = int(str(number1)[:(n1//2)])
b = int(str(number1)[(n1//2):])
kara = 10**((n1+1)//2)*a*number2 + b*number2 #a mistake here
return kara
elif n1 != 1 and n2 != 1: # loop
a = int(str(number1)[:(n1 // 2)])
b = int(str(number1)[(n1 // 2):])
c = int(str(number2)[:(n2 // 2)])
d = int(str(number2)[(n2 // 2):])
z1 = karatsuba(a, c)
z2 = karatsuba(a, d)
z3 = karatsuba(b, c)
z4 = karatsuba(b, d)
kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
return kara
num1 = 3141592653589793238462643383279502884197169399375105820974944592
num2 = 2718281828459045235360287471352662497757247093699959574966967627
k_res = karatsuba(num1,num2)
ac_res = num1*num2
print(k_res)
print(ac_res)
assert k_res==ac_res