O algoritmo de multiplicação de Karatsuba

A forma de multiplicar inteiros ensinada na escola é simples e conveniente para inteiros relativamente pequenos, mas vejamos seu custo. Para multiplicar dois inteiros de n algarismos na base dprocedemos basicamente a partir da fórmula:

$$(\sum_i a_i d^i)(\sum_j b_j d^j) = \sum_{i,j} a_i b_j d^{i+j}:$$

calculamos (ou olhamos na tabuada) todos os produtos de um algarismo de um dos inteiros com um algarismo do outro, multiplicamos pela potência de d apropriada (o que equivale a acrescentar zeros à direita) e somamos as n²parcelas obtidas. Efetuamos no processo n² multiplicações e um número comparável de somas; assim, o tempo gasto com este algoritmo é aproximadamente A n²para alguma constante positiva A. Se isto fosse o melhor que pudéssemos fazer, o tempo para checar a primalidade de M_p seria aproximadamente A p³. Existem entretanto outros algoritmos de multiplicação: examinemos primeiro um algoritmo relativamente simples, o algoritmo de Karatsuba, usado pela biblioteca gmp (e portanto por nossos programas acima).

Sejam A e B dois inteiros com n algarismos cada um. Se $m = \lceil n/2 \rceil$, podemos escrever A = A₁ d^m + A₀, B = B₁ d^m + B₀ e AB = A₁ B₁ d^2m + (A₁ B₀ + A₀ B₁) d^m + A₀ B₀. Pelo algoritmo anterior, calcularíamos os quatro produtos de inteiros com m algarismos. Entretanto, os produtos A₁ B₀ e A₀ B₁não são necessários individualmente, e podemos calcular sua soma da seguinte forma:

A₁ B₀ + A₀ B₁ = (A₁ - A₀)(B₀ - B₁) + A₁ B₁ + A₀ B₀.

Em outras palavras, podemos escrever

AB = A₁ B₁ (d^2m + d^m) + (A₁ - A₀)(B₀ - B₁) d^m + A₀ B₀ (d^m + 1).

Assim, podemos calcular os três coeficientes com apenas três multiplicações (ao invés de quatro) e algumas somas. Mesmo que o número de somas aumente, já sabemos que somas são rápidas e portanto podemos esperar que este algoritmo represente uma melhora substancial em relação ao anterior.

Mais precisamente, repetimos este processo para diminuirmos o tamanho dos inteiros. Assim, se denotarmos por f(n) o tempo necessário para multiplicar inteiros de n algarismos temos $f(n) \approx 3 f(\lceil n/2 \rceil) + A n$ e provamos facilmente que

$$f(n) \approx A n^\alpha,$$

onde $\alpha = (\log 3)/(\log 2)$.