Algorithme de karatsuba en python

""" -------------- L'algorithme -------------- """

def Karatsuba(P,Q): 
    """ P et Q deux polynômes, taille(P)=taille(Q) (pas nécessairement une puissance de 2). Les polynômes sont donnés par la liste de leurs coefficients, ordonnés de 1 à x^{n-1}. On retourne la liste des coefficients correspondant au produit P*Q"""
    n=len(P)
    if n==1:
        return([P[0]*Q[0]])
    m=n//2
    P0=P[:m] 
    P1=P[m:] #P=P0+X^m P1
    Q0=Q[:m]
    Q1=Q[m:] #Q=Q0+X^m Q1
    T0=Karatsuba(P0,Q0) #de taille 2*m-1
    T1=Karatsuba(P1,Q1) # de taille 2*(n-m)-1 =2*m-1 si n pair, 2*m+1 si n impair. 
    for i in range(m): #on utilise P1 et Q1 pour ne pas allouer de la mémoire supplémentaire.
        P1[i]+=P0[i]
        Q1[i]+=Q0[i]
    T2=Karatsuba(P1,Q1) #de taille 2*(n-m)-1 =2*m-1 si n pair, 2*m+1 si n impair.
    for i in range(2*m-1):
        T2[i]=T2[i]-T1[i]-T0[i]
    if n%2==1: #si n pair, les tableaux T0,T1,T2 sont de la meme taille 2*m-1, sinon T1 et T2 sont de taille 2*m+1.
        T2[-2]=T2[-2]-T1[-2]
        T2[-1]=T2[-1]-T1[-1]
    produit=[0]*(2*n-1) #polynome de longueur n * polynome de longueur n = polynome de longueur 2*n-1. PQ=P0*Q0+(P1*Q0+P0*Q1)*X^m+P1*Q1*X^2m
    for i in range(2*m-1):
        produit[i]+=T0[i]
        produit[i+m]+=T2[i] #décalage correspondant à T2: X^m
        produit[i+2*m]+=T1[i] #décalage correspondant à T1: X^(2*m)
    if n%2==1:
        produit[3*m-1]+=T2[2*m-1]
        produit[3*m]+=T2[2*m]
        produit[4*m-1]+=T1[2*m-1]
        produit[4*m]+=T1[2*m]
    return(produit)

" -------------- Exemples d'exécution -------------- "

from random import randint

N=10
P=[randint(-1000,1000) for _ in range(N)]
Q=[randint(-1000,1000) for _ in range(N)]
print(Karatsuba(P,Q))