在 python class 中实现 karatsuba 递归函数，错误
Implementing karatsuba recursion function in python class, errors
之前我 post 就这个主题提出了一个问题，并且得到了很好的回答。 然而，关于 class 中的递归，我仍然有一些不明白的地方。在上面的链接问题中，如果我向递归子例程添加前缀 self.，我会得到与下面 class 输出中产生的完全相同的错误（此 post 中的第三个代码块).我明白为什么会这样； object.karatsuba() 仅将 self 作为其输入，但编码的方法还要求 2，因此出现错误。
请查看下面的代码，然后看看我对第三个代码块后的解决方案的直觉。
例如：我有一个 karatsuba 乘法的工作实现，它不想在 class 中工作。标准 class 房间乘法在 class 中工作得很好，但是...
这是 class:
之外的工作代码
def zeroPad(numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsubaMultiplication(x ,y):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
x = str(x)
y = str(y)
#base case for recursion
if len(x) == 1 and len(y) == 1:
return int(x) * int(y)
if len(x) < len(y):
x = zeroPad(x, len(y) - len(x))
elif len(y) < len(x):
y = zeroPad(y, len(x) - len(y))
n = len(x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
a = int(x[:j])
b = int(x[j:])
c = int(y[:j])
d = int(y[j:])
#recursively calculate
ac = karatsubaMultiplication(a, c)
bd = karatsubaMultiplication(b, d)
k = karatsubaMultiplication(a + b, c + d)
A = int(zeroPad(str(ac), AZeroPadding, False))
B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
这是在第 39 行失败的 class 中的代码：
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
a = int(self.x[:j])
b = int(self.x[j:])
c = int(self.y[:j])
d = int(self.y[j:])
#recursively calculate
ac = self.karatsuba(a, c)
bd = self.karatsuba(b, d)
k = self.karatsuba(a + b, c + d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
错误的 class 版本生成以下输出：
x = 234523546643636
y = 325352354534656
x = Karatsuba(x,y)
x.karatsuba()
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-5-aa1c267478ee> in <module>()
4 x = Karatsuba(x,y)
5
----> 6 x.karatsuba()
<ipython-input-1-1d1e9825dcc5> in karatsuba(self)
37 d = int(self.y[j:])
38 #recursively calculate
---> 39 ac = self.karatsuba(a, c)
40 bd = self.karatsuba(b, d)
41 k = self.karatsuba(a + b, c + d)
TypeError: karatsuba() takes 1 positional argument but 3 were given
我最初的直觉是遵循最上面一段链接问题中概述的解决方案：
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
self.a = int(self.x[:j])
self.b = int(self.x[j:])
self.c = int(self.y[:j])
self.d = int(self.y[j:])
#recursively calculate
# ac = self.karatsuba(self.a, self.c)
# bd = self.karatsuba(self.b, self.d)
ac = Karatsuba(self.a, self.c)
ac.karatsuba()
bd = Karatsuba(self.b, self.d)
bd.karatsuba()
k = Karatsuba(self.a + self.b, self.c + self.d)
k.karatsuba()
# k = self.karatsuba(self.a + self.b, self.c + self.d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
x = 234523546643636
y = 325352354534656
x = Karatsuba(x,y)
x.karatsuba()
这解决了位置参数错误，但我遇到了一个新问题：
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-34-a862504dede9> in <module>()
59
60 x = Karatsuba(x,y)
---> 61 x.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
51 # k = self.karatsuba(self.a + self.b, self.c + self.d)
52
---> 53 A = int(self.zeroPad(str(ac), AZeroPadding, False))
54 B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
55 return A + B + bd
ValueError: invalid literal for int() with base 10: '<__main__.Karatsuba object at 0x108142ba8>00'
此时我卡住了。
当我输入这个问题时，我发现自己正在以不同的方式查看我的代码，即思考如何最好地清楚地解释我的问题，
思考 ValueError，我发现了问题。
我在先前链接的问题中遵循了 abarnert 提供的直觉是正确的。问题在于函数的其余部分如何需要递归子例程中的值；正如您从 ValueError 中看到的那样，传递的是递归子例程的内存位置，而不是子例程生成的值。然后解决方案很简单：将 ac.karatsuba() 修改为 ac = ac.karatsuba(), etc... 瞧！
我认为这个（以及之前链接的问题）对于那些试图理解如何在 python classes 中实现递归的人来说是一个很好的教程。
希望大家点个赞给我投个赞！
这是有效的 class 代码：
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
self.a = int(self.x[:j])
self.b = int(self.x[j:])
self.c = int(self.y[:j])
self.d = int(self.y[j:])
#recursively calculate
# ac = self.karatsuba(self.a, self.c)
# bd = self.karatsuba(self.b, self.d)
ac = Karatsuba(self.a, self.c)
ac = ac.karatsuba()
bd = Karatsuba(self.b, self.d)
bd = bd.karatsuba()
k = Karatsuba(self.a + self.b, self.c + self.d)
k = k.karatsuba()
# k = self.karatsuba(self.a + self.b, self.c + self.d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
之前我 post 就这个主题提出了一个问题，并且得到了很好的回答。 self.，我会得到与下面 class 输出中产生的完全相同的错误（此 post 中的第三个代码块).我明白为什么会这样； object.karatsuba() 仅将 self 作为其输入，但编码的方法还要求 2，因此出现错误。
请查看下面的代码，然后看看我对第三个代码块后的解决方案的直觉。
例如：我有一个 karatsuba 乘法的工作实现，它不想在 class 中工作。标准 class 房间乘法在 class 中工作得很好，但是...
这是 class:
之外的工作代码def zeroPad(numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsubaMultiplication(x ,y):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
x = str(x)
y = str(y)
#base case for recursion
if len(x) == 1 and len(y) == 1:
return int(x) * int(y)
if len(x) < len(y):
x = zeroPad(x, len(y) - len(x))
elif len(y) < len(x):
y = zeroPad(y, len(x) - len(y))
n = len(x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
a = int(x[:j])
b = int(x[j:])
c = int(y[:j])
d = int(y[j:])
#recursively calculate
ac = karatsubaMultiplication(a, c)
bd = karatsubaMultiplication(b, d)
k = karatsubaMultiplication(a + b, c + d)
A = int(zeroPad(str(ac), AZeroPadding, False))
B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
这是在第 39 行失败的 class 中的代码：
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
a = int(self.x[:j])
b = int(self.x[j:])
c = int(self.y[:j])
d = int(self.y[j:])
#recursively calculate
ac = self.karatsuba(a, c)
bd = self.karatsuba(b, d)
k = self.karatsuba(a + b, c + d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
错误的 class 版本生成以下输出：
x = 234523546643636
y = 325352354534656
x = Karatsuba(x,y)
x.karatsuba()
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-5-aa1c267478ee> in <module>()
4 x = Karatsuba(x,y)
5
----> 6 x.karatsuba()
<ipython-input-1-1d1e9825dcc5> in karatsuba(self)
37 d = int(self.y[j:])
38 #recursively calculate
---> 39 ac = self.karatsuba(a, c)
40 bd = self.karatsuba(b, d)
41 k = self.karatsuba(a + b, c + d)
TypeError: karatsuba() takes 1 positional argument but 3 were given
我最初的直觉是遵循最上面一段链接问题中概述的解决方案：
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
self.a = int(self.x[:j])
self.b = int(self.x[j:])
self.c = int(self.y[:j])
self.d = int(self.y[j:])
#recursively calculate
# ac = self.karatsuba(self.a, self.c)
# bd = self.karatsuba(self.b, self.d)
ac = Karatsuba(self.a, self.c)
ac.karatsuba()
bd = Karatsuba(self.b, self.d)
bd.karatsuba()
k = Karatsuba(self.a + self.b, self.c + self.d)
k.karatsuba()
# k = self.karatsuba(self.a + self.b, self.c + self.d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd
x = 234523546643636
y = 325352354534656
x = Karatsuba(x,y)
x.karatsuba()
这解决了位置参数错误，但我遇到了一个新问题：
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-34-a862504dede9> in <module>()
59
60 x = Karatsuba(x,y)
---> 61 x.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
44 # bd = self.karatsuba(self.b, self.d)
45 ac = Karatsuba(self.a, self.c)
---> 46 ac.karatsuba()
47 bd = Karatsuba(self.b, self.d)
48 bd.karatsuba()
<ipython-input-34-a862504dede9> in karatsuba(self)
51 # k = self.karatsuba(self.a + self.b, self.c + self.d)
52
---> 53 A = int(self.zeroPad(str(ac), AZeroPadding, False))
54 B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
55 return A + B + bd
ValueError: invalid literal for int() with base 10: '<__main__.Karatsuba object at 0x108142ba8>00'
此时我卡住了。
当我输入这个问题时，我发现自己正在以不同的方式查看我的代码，即思考如何最好地清楚地解释我的问题， 思考 ValueError，我发现了问题。
我在先前链接的问题中遵循了 abarnert 提供的直觉是正确的。问题在于函数的其余部分如何需要递归子例程中的值；正如您从 ValueError 中看到的那样，传递的是递归子例程的内存位置，而不是子例程生成的值。然后解决方案很简单：将 ac.karatsuba() 修改为 ac = ac.karatsuba(), etc... 瞧！
我认为这个（以及之前链接的问题）对于那些试图理解如何在 python classes 中实现递归的人来说是一个很好的教程。
希望大家点个赞给我投个赞！
这是有效的 class 代码：
class Karatsuba(object):
def __init__(self, x, y):
self.x = x
self.y = y
def zeroPad(self, numberString, zeros, left = True):
"""Return the string with zeros added to the left or right."""
for i in range(zeros):
if left:
numberString = '0' + numberString
else:
numberString = numberString + '0'
return numberString
def karatsuba(self):
"""Multiply two integers using Karatsuba's algorithm."""
#convert to strings for easy access to digits
self.x = str(self.x)
self.y = str(self.y)
#base case for recursion
if len(self.x) == 1 and len(self.y) == 1:
return int(self.x) * int(self.y)
if len(self.x) < len(self.y):
self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
elif len(self.y) < len(self.x):
self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
n = len(self.x)
j = n//2
#for odd digit integers
if (n % 2) != 0:
j += 1
BZeroPadding = n - j
AZeroPadding = BZeroPadding * 2
self.a = int(self.x[:j])
self.b = int(self.x[j:])
self.c = int(self.y[:j])
self.d = int(self.y[j:])
#recursively calculate
# ac = self.karatsuba(self.a, self.c)
# bd = self.karatsuba(self.b, self.d)
ac = Karatsuba(self.a, self.c)
ac = ac.karatsuba()
bd = Karatsuba(self.b, self.d)
bd = bd.karatsuba()
k = Karatsuba(self.a + self.b, self.c + self.d)
k = k.karatsuba()
# k = self.karatsuba(self.a + self.b, self.c + self.d)
A = int(self.zeroPad(str(ac), AZeroPadding, False))
B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
return A + B + bd