Алгоритм Карацубы для двух полиномов одинаковой степени - PullRequest
Новая
       43

Алгоритм Карацубы для двух полиномов одинаковой степени

0 голосов
/ 11 июля 2019

Я пытаюсь создать алгоритм Карацубы в python для двух полиномов одинаковой степени, который должен возвращать массив коэффициентов результата. 

def karatsuba(a, b):  

    n = len(a)

    aHigh = []
    aLow = []

    bHigh = []
    bLow = []

    c = []

    for i in range(n//2):
        aLow.append(a[i])
        bLow.append(b[i])

    for i in range(n//2):
        aHigh.append(a[n//2+i])
        bHigh.append(b[n//2+i])

    tA = []
    tB = []

    for i in range(n//2):
        tA.append(aLow[i] + aHigh[i])
        tB.append(bLow[i] + bHigh[i])

    cMid = karatsuba(tA, tB)
    cLow = karatsuba(aLow, bLow)
    cHigh = karatsuba(aHigh, bHigh)

    for i in range(n-1):
        c.append(cLow[i])

    c[n-1] = 0

    for i in range(n-1):
        c.append(cHigh[i])

    for i in range(n-1):
        c[n//2 + i] += cMid[i] - (cLow[i] + cHigh[i])

    return c

Я получаюмаксимальная ошибка глубины рекурсии при cMid = karatsuba(tA, tB).У кого-нибудь есть вход?Я был бы очень признателен!

...