mise en œuvre Karatsubas en Python algorithme de multiplication

Question

Je suis en train de mettre en œuvre Karatsuba's Multiplication algorithm en Python

Voici mon code

import math 
# Base 
B=10 
# No. of digits 
n=4 
# Numbers 
x=1234 
y=5678 

def karatsuba(x,y,d): 
    if (x < 10 o r y < 10): 
     return x*y 

    # Partition 
    m=math.floor(d/2) 
    n=math.ceil(d/2) 

    x1=x//B**n 
    x2=x%B**n 

    y1=y//B**n 
    y2=y%B**n 

    a=karatsuba(x1,y1,m) 
    b=karatsuba(x1+x2,y1+y2,m) #Line 25 
    c=karatsuba(x2,y2,n) 

    tot = a*(B**(2*m)) + b*(B**m) + c 

res=karatsuba(x,y,n) 

print('%d * %d = %d' %(x, y, res)) 

Mais comme vous pouvez le voir dans Line 25, lorsque nous effectuons x1+x2 et y1+y2 (en tenant compte x1x2, y1, y2 sont m chiffres) l'une ou l'autre somme peut dépasser m chiffres. Dans ce cas, comment puis-je faire un appel récursif à karatsuba() avec deux nombres ayant un nombre différent de chiffres. Quelqu'un peut-il donner une solution simple à cela.

Answer 1

Cela devrait être une implémentation de travail que j'ai faite pour un cours d'algorithmes:

def karatsuba(x, y): 
    if x < 10 or y < 10: 
     return x * y 
    # get longest digits 
    n = max(math.log10(x) + 1, math.log10(y) + 1) 
    # catch where n is odd 
    n -= n % 2 
    bn = B ** (n // 2) 
    x1, x2 = divmod(x, bn) 
    y1, y2 = divmod(y, bn) 
    ac = karatsuba(x1, y1) 
    bd = karatsuba(x2, y2) 
    # caluclate a+b and c + d subtracting already 
    # calculated ac and bd leaving ad + bc 
    adbc = karatsuba(x1 + x2, y1 + y2) - ac - bd 
    # x . y = 10^n ac + 10^n/2 (ad + bc) + bd 
    return ((B ** n) * ac) + bn * adbc + bd 


res = karatsuba(x, y) 

print('%d * %d = %d' % (x, y, res)) 

Answer 2

Vous n'avez pas besoin de transmettre la taille des chiffres. Si vous l'avez fait de cette façon, votre algorithme ne fonctionnerait que pour des nombres avec des chiffres égaux dans chaque appel récursif. Au lieu d'entrer uppon dans la fonction calculer le nombre de chiffres des deux nombres n = max(len(str(x)), len(str(y))) alors vous padd le plus petit des x, y avec 0s à la fin des chiffres les plus significatifs un procéder à diviser les deux par n/2.