Алгоритм Карацубы в Python

Question

Итак, я реализую алгоритм умножения Карацубы в 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 

Answer 1

Я вычислял максимальную длину передаваемого числа, делая это таким образом, фиксировал его.

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

Answer 2

Некоторые советы:

• Я не думаю, что ваши ценности для a, b, являются what you want them to be.
• Общей ошибкой часто является то, что сплит не возвращает строго меньшие числа: укажите источник для _least_significant_digits, _right_shift.
• Что происходит, когда один из ваших входов имеет длину 1, но не другой? Что в этом случае расколется возврат для 1-значного числа?