Выполнение размножения Карацубы

Question

Недавно я воплотил Карацубу Умножение как личное упражнение. Я написал свою реализацию в Python после pseudocode provided on wikipedia:

procedure karatsuba(num1, num2) 
if (num1 < 10) or (num2 < 10) 
    return num1*num2 
    /* calculates the size of the numbers */ 
    m = max(size_base10(num1), size_base10(num2)) 
    m2 = m/2 
    /* split the digit sequences about the middle */ 
    high1, low1 = split_at(num1, m2) 
    high2, low2 = split_at(num2, m2) 
    /* 3 calls made to numbers approximately half the size */ 
    z0 = karatsuba(low1, low2) 
    z1 = karatsuba((low1+high1), (low2+high2)) 
    z2 = karatsuba(high1, high2) 
    return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0) 

Вот моя реализация питон:

def karat(x,y): 
    if len(str(x)) == 1 or len(str(y)) == 1: 
     return x*y 
    else: 
     m = max(len(str(x)),len(str(y))) 
     m2 = m/2 

     a = x/10**(m2) 
     b = x % 10**(m2) 
     c = y/10**(m2) 
     d = y % 10**(m2) 

     z0 = karat(b,d) 
     z1 = karat((a+b),(c+d)) 
     z2 = karat(a,c) 

     return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0) 

Мой вопрос об окончательном слиянии z0, z1 и z2.
z2 сдвигается м цифры над (где м длина самой большой из двух умножают число).
Вместо простого умножения на 10^(м), алгоритм использует * 10^(2 * м2) *, где м2 является м/2.

Я попытался заменить 2 * m2 с м и получил неправильные результаты. Я думаю, что это связано с тем, как цифры разделяются, но я не совсем уверен, что происходит.

Answer 1

В зависимости от вашей версии Python вы должны или должны заменить / на явный оператор разделения пола //, который здесь подходит; он округляет, гарантируя, что ваши экспоненты останутся целыми числами.

Это очень важно, например, при расщеплении ваших операндов в высоких цифрах (напольной разделив на 10^m2) и низкие цифры (принимая остаточный по модулю 10^m2), это не будет работать с дробной m2.

Он также объясняет, почему 2 * (x // 2) необязательно равно x, а не x-1, если х нечетно. В последней строке алгоритма 2 m2 правильно, потому что то, что вы делаете, дает a и c их нули назад.

Если вы используете более старую версию Python, ваш код может по-прежнему работать, потому что / раньше применялся к целым числам.

def karat(x,y): 
    if len(str(x)) == 1 or len(str(y)) == 1: 
     return x*y 
    else: 
     m = max(len(str(x)),len(str(y))) 
     m2 = m // 2 

     a = x // 10**(m2) 
     b = x % 10**(m2) 
     c = y // 10**(m2) 
     d = y % 10**(m2) 

     z0 = karat(b,d) 
     z1 = karat((a+b),(c+d)) 
     z2 = karat(a,c) 

     return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0) 

Answer 2

я реализовал ту же идею, но я ограничен 2 значного умножение в качестве базового варианта, потому что я могу уменьшить поплавок умножение в функции

import math 

def multiply(x,y): 
    sx= str(x) 
    sy= str(y) 
    nx= len(sx) 
    ny= len(sy) 
    if ny<=2 or nx<=2: 
     r = int(x)*int(y) 
     return r 
    n = nx 
    if nx>ny: 
     sy = sy.rjust(nx,"0") 
     n=nx 
    elif ny>nx: 
     sx = sx.rjust(ny,"0") 
     n=ny 
    m = n%2 
    offset = 0 
    if m != 0: 
     n+=1 
     offset = 1 
    floor = int(math.floor(n/2)) - offset 
    a = sx[0:floor] 
    b = sx[floor:n] 
    c = sy[0:floor] 
    d = sy[floor:n] 
    print(a,b,c,d) 

    ac = multiply(a,c) 
    bd = multiply(b,d) 

    ad_bc = multiply((int(a)+int(b)),(int(c)+int(d)))-ac-bd 
    r = ((10**n)*ac)+((10**(n/2))*ad_bc)+bd 

    return r 

print(multiply(4,5)) 
print(multiply(4,58779)) 
print(int(multiply(4872139874092183,5977098709879))) 
print(int(4872139874092183*5977098709879)) 
print(int(multiply(4872349085723098457,597340985723098475))) 
print(int(4872349085723098457*597340985723098475)) 
print(int(multiply(4908347590823749,97098709870985))) 
print(int(4908347590823749*97098709870985)) 

Answer 3

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

Это относится к тому, как вы разделяете свои номера для рекурсивных вызовов. Если вы решите использовать нечетное n, тогда n//2 будет округлено до ближайшего целого числа, что означает, что ваш второй номер будет иметь длину floor(n/2), и вам нужно будет заполнить первый с нулями floor(n/2). Поскольку мы используем те же самые n для обоих номеров, это применимо к обоим. Это означает, что если вы придерживаетесь оригинального нечетного n для заключительного шага, вы должны заполнить первый семестр исходными n нулями вместо количества нулей, которые возникли бы из комбинации первого дополнения и второго дополнения (floor(n/2)*2)