Karatsuba algorithm in Python

그래서 Karatsuba의 곱셈 알고리즘을 Python으로 구현하고 있습니다. 지금 나는 무한 재귀를 가지고 있으며 그것을 이해할 수 없다. 어떤 아이디어? 필요한 경우 더 많은 코드를 제공 할 것입니다.Karatsuba algorithm in Python

def multiply(self, other): 


    # helper function 
    def split(largeInt, n): 
    least = largeInt._least_significant_digits(n/2) 
    most = largeInt._right_shift(n/2) 
    if debug: assert least.to_int() + (most.to_int() << (LargeInt.base_bits*(n/2))) == largeInt.to_int() 
    return least, most 
    n = max(len(str(self)),len(str(other))) 
    if (n==1): 
    return self.to_int() * other.to_int() 
    else: 
    aR, aL = split(self,n) 
    bR , bL = split(other, n) 
    x1 = aL.multiply(bL) 
    x2 =aR.multiply(bR) 
    a = aL.add(bL) 
    b = aR.add(bR) 
    x3=a.multiply(b) 
    # code for recursive step here 
    #return 1 # change this line with your implementation 
    return x1 * 10**n + (x3-x1-x2) * 10**(n/2) + x2

출처

2012-05-01 Marty Griffin

코드에는 여기에 "TODO : your implementation here"및 "base case for code here"와 같은 주석이 있습니다. 또한 실제 Karatsuba 코드 바로 앞에 'return 2'가 있습니다. 여기에 올바른 코드를 게시 했습니까? –

이 코드는 올바르게 들여 쓰기해야합니다. – deebee

코드에 진단 인쇄 문구를 넣어 두었습니다. 그들은 무엇을 보여줍니까? 무한 재귀에 깊이 빠져 들어가면 어떤 값이'multiply'로 전달됩니까? 당신이 호출하는 큰 정수 방법이 당신이 원하는 것을하는 것이 확실합니까? 'n/2'는 정수 또는 부동 소수점을 생성합니까? 그리고 후자가 나쁘면? –

나는 전달되는 숫자의 최대 길이를 계산하여 고정 시켰습니다.

n = max(len(self.digits),len(other.digits))

출처

2012-05-01 15:04:54

일부 힌트 :

나는 a, b에 대한 당신의 가치를 생각 what you want them to be입니다하지 않습니다.
종종 split은 엄격하게 작은 숫자를 반환하지 않는 경우가 종종 있습니다. _least_significant_digits, _right_shift에 대한 소스를 제공하십시오.
입력 내용 중 길이가 1이지만 다른 길이가 아닌 경우 어떻게됩니까? 이 경우 1 자리 숫자에 대해 분할 반환은 무엇입니까?

출처

2012-05-01 09:42:21 huitseeker

Karatsuba algorithm in Python

답변

관련 문제