A complexidade das operações aritméticas

Vimos na seção anterior que o número de operações (e portanto o tempo) necessário para multiplicar inteiros de N algarismos é aproximadamente (a menos de um fator constante) $N \log N \log\log N$ se utilizarmos um dos algoritmos descritos. Não se conhece nenhum algoritmo que seja assintóticamente mais rápido mas também não se sabe demonstrar que não existe um tal algoritmo. Mostraremos nesta seção que o tempo necessário para realizar qualquer uma das operações abaixo é assintoticamente o mesmo (isto é, difere por uma constante multiplicativa). Note que adições e subtrações são mais rápidas e desprezaremos o tempo exigido por essas operações.

1.

Multiplicar inteiros de N algarismos.

2.

Elevar ao quadrado um inteiro de N algarismos.

3.

Inverter, ou seja, encontrar os primeiros 2N algarismos depois da vírgula de 1/n, onde n tem N algarismos, ou ainda, calcular $\lfloor Q^{2N} / n \rfloor$ (se trabalharmos na base Q).

4.

Fazer a divisão com resto de dois inteiros de N algarismos, i.e., dados n e m encontrar q e r com n = qm + r, $0 \le r < m$.

Estas operações podem ser reduzidas uma às outras com a mesma ordem de grandeza de tempo, i.e., multiplicando o tempo necessário por uma constante. Faremos isto da seguinte forma:

(a)

Quem sabe multiplicar sabe elevar ao quadrado.

(b)

Quem sabe elevar ao quadrado sabe multiplicar.

(c)

Quem sabe multiplicar sabe inverter.

(d)

Quem sabe inverter sabe elevar ao quadrado.

(e)

Quem sabe multiplicar e inverter sabe dividir com resto.

(f)

Quem sabe dividir com resto sabe inverter.

Os itens (a), (e) e (f) são triviais. O item (b) segue de mn = ((m+n)² - (m-n)²)/4. O item (d) segue de x² = (x^-1 - (x+1)^-1)^-1 - x. O item (c) segue do fato que se $x = n/Q^N \in (1/Q, 1]$(x um número real dado com uma certa precisão) e se $y \in [1, Q)$ é uma aproximação para 1/x com k casas de precisão então y' = y(2 - xy) é uma aproximação para 1/xcom aproximadamente 2k casas de precisão. De fato temos y' - 1/x = -x (y - 1/x)²donde $\vert y' - 1/x\vert \le \vert y - 1/x\vert^2$. Este algoritmo pode ser visto como uma aplicação do método de Newton para a função f(t) = -x + 1/t. Note que as primeiras aproximações para 1/x podem ser calculadas com poucos algarismos de precisão, donde as primeiras multiplicações podem ser feitas com poucos algarismos; isto garante que o tempo total para obter N algarismos de 1/xé comparável ao tempo de uma multiplicação de inteiros com N algarismos.