获取karatsuba乘错了地方

-2

所以，我是新来的蟒蛇从karatsuba乘法伪写了这个代码和我得到某种获取karatsuba乘错了地方

这里的逻辑错误是我使用的伪代码：

procedure karatsuba(num1, num2) 
    if (num1 < 10) or (num2 < 10) 
    return num1*num2 
    /* calculates the size of the numbers */ 
    m = max(size_base10(num1), size_base10(num2)) 
    m2 = m/2 
    /* split the digit sequences about the middle */ 
    high1, low1 = split_at(num1, m2) 
    high2, low2 = split_at(num2, m2) 
    /* 3 calls made to numbers approximately half the size */ 
    z0 = karatsuba(low1,low2) 
    z1 = karatsuba((low1+high1),(low2+high2)) 
    z2 = karatsuba(high1,high2) 
    return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

这里是它的Python代码：

def mul(n1,n2): 

if n1<10 or n2<10: 
    return n1*n2 

l = max(len(str(n1)),len(str(n2))) 
print(l) 
half = l//2 
print(half) 

f1 = int(str(n1)[:half]) 
print("f1",f1) 
l1 = int(str(n1)[half:]) 
print("l1",l1) 
f2 = int(str(n2)[:half]) 
print("f2",f2) 
l2 = int(str(n2)[half:]) 
print("l2",l2) 

c = mul(l1,l2) 
print("c",c) 
b = mul((l1+f1),(l2+f2)) 
print("b",b) 
a = mul(f1,f2) 
print("a",a) 

return ((a*10^(2*half))+((b-a-c)*10^(half))+c) 
var = mul(44,21) 
print(var)

如果有人做了这种算法，任何人都可以建议我在哪里得到它错了吗？

任何帮助，将不胜感激。

来源

2017-10-12 Sahil Sharma

它告诉你用'行了= MUL （f1 + f2）'是有问题的，因为您需要多一个参数才能使用该函数。 – Kanak

'A = MUL（F1 + F2）' – Shadow

非常感谢的快速答复家伙。 –

您的问题可以来自您使用幂运算符。需要注意的是

^是xor操作。

而

**用于幂

>>> 2**3 
8

或者等价地，你可以使用内置的功能pow

>>> pow(2, 3) 
8

来源

2017-10-12 06:30:01 Kanak

获取karatsuba乘错了地方

回答

相关问题