Trabalho realizado para a disciplina de FPAA (Fundamentos de Projeto e Análise de Algoritmos) do curso de Engenharia de Software (PUC Minas). O objetivo do trabalho é implementar o algoritmo de multiplicação de inteiros Karatsuba e realizar uma análise de complexidade do mesmo.
O algoritmo de Karatsuba é uma técnica eficiente para multiplicação de números inteiros grandes, introduzida por Anatolii Karatsuba em 1960. Ele melhora a complexidade da multiplicação em comparação ao método tradicional de multiplicação direta.
O algoritmo de Karatsuba funciona com base na abordagem "divide and conquer", quebrando os números em partes menores para reduzir o número de multiplicações. Ele segue os seguintes passos:
- Se os números forem pequenos o suficiente, realiza a multiplicação diretamente.
- Caso contrário, divide os números ao meio, separando as partes de ordem mais alta e mais baixa.
- Faz três chamadas recursivas para multiplicar essas partes menores.
- Usa as multiplicações obtidas para calcular o resultado final, reduzindo o número total de operações comparado ao método tradicional.
Esse processo reduz a complexidade da multiplicação de ( O(n^2) ) para aproximadamente ( O(n^{1.585}) ), tornando-o mais eficiente para números grandes.
def karatsuba(x: int, y: int) -> int:
if x < 10 or y < 10:
return x * y
else:
n = max(len(str(x)), len(str(y)))
half = n // 2
a = x // (10 ** (half)) # A = parte a esquerda de x
b= x % (10 ** (half)) # B = parte a direita de x
c = y // (10 ** (half)) # C = parte a esquerda de y
d = y % (10 ** (half)) # D = parte a direita de y
ac = karatsuba(a, c)
bd = karatsuba(b, d)
ad_plus_bc = karatsuba(a + b, c + d) - ac - bd
return ac * (10 ** (2 * half)) + (ad_plus_bc * (10 ** half)) + bd Para executar o projeto, siga os passos abaixo:
- Python 3 instalado.
- Clone o repositório:
git clone https://github.com/RenatoMAP77/Karatsuba.git
- Acesse o diretório do projeto:
cd src - Execute o script principal:
python app.py
- Insira dois números inteiros para multiplicação e veja o resultado exibido no terminal.
A complexidade ciclomática é uma métrica usada para medir a complexidade do fluxo de controle de um programa. Ela calcula o número de caminhos independentes no código, considerando estruturas como loops (for, while) e condicionais (if, try/except). Quanto maior o valor, mais complexo é o código.
Fórmula:
(
M = E - N + 2P
)
Onde:
- (M): Complexidade Ciclomática
- (E): Número de arestas (transições) no grafo do controle de fluxo
- (N): Número de nós (blocos de código)
- (P): Componentes conectados (geralmente 1 para programas simples)
Com isto explicado podemos partir para o calculo da complexidade ciclomática do algoritmo de Karatsuba. Para isso, vamos considerar o código do algoritmo como um grafo de controle de fluxo, onde os nós são os blocos de código e as arestas são as transições entre eles.
N - Nós:
- Inicio da função
- Verificação do
if - Execução dentro do If (Retorno da multiplicação)
- Cálculo do tamanho
n - Cálculo de
half - Cálculo das partes de
x(aeb) - Cálculo das partes de
y(ced) - Chamada recursiva
karatsuba(a, c) - Atribuição de
ac - Chamada recursiva
karatsuba(b, d) - Atribuição de
bd - Chamada recursiva
karatsuba(a + b, c + d) - Cálculo de
ad_plus_bc - Retorno da multiplicação combinada
E - Arestas:
- Início da função → Verificação do
if ifverdadeiro → Retorno direto da multiplicaçãoiffalso → Cálculo do tamanhon- Cálculo do tamanho
n→ Cálculo dehalf - Cálculo de
half→ Cálculo das partes dex - Cálculo das partes de
x→ Cálculo das partes dey - Cálculo das partes de
y→ Chamadakaratsuba(a, c) - Chamada
karatsuba(a, c)→ Inicio da funcao - Chamada
karatsuba(a, c)→ Atibuição deac - Atribuição de ac → Chamada
karatsuba(b, d) - Chamada
karatsuba(b, d)→ Inicio da funcao - Chamada
karatsuba(b, d)→ Atribuição debd - Atribuição de
bd→ Chamadakaratsuba(a + b, c + d) - Chamada
karatsuba(a + b, c + d)→ Inicio da funcao - Chamada
karatsuba(a + b, c + d)→ Cálculo dead_plus_bc - Cálculo de
ad_plus_bc→ Retorno da multiplicação combinada
Podendo ser melhor representado pela imagem a seguir do grafo de fluxo.
Aplicando a Fórmula:
Usando a fórmula da complexidade ciclomática: ( M = E - N + 2P ) Onde:
- ( E = 16 ) (arestas)
- ( N = 14 ) (nós)
- ( P = 1 ) (um único componente conectado)
( M = 16 - 14 + 2(1) = 4 )
Análise da complexidade temporal
O algoritmo de Karatsuba melhora a eficiência da multiplicação tradicional reduzindo o número de operações necessárias. Em vez de realizar ( O(n^2) ) multiplicações como no método convencional, ele usa um esquema de divisão e conquista para reduzir essa complexidade. A cada nível da recursão, os números são divididos ao meio e três multiplicações menores são realizadas, além de operações adicionais de soma e potência de 10. Isso resulta em uma complexidade de tempo de aproximadamente:
O(n^{1.585})
Esse valor surge porque a cada passo reduzimos o tamanho do problema pela metade, mas realizamos três chamadas recursivas em vez de quatro, como aconteceria na multiplicação tradicional.
Casos de Complexidade
- Melhor caso: Ocorre quando os números são pequenos o suficiente para serem multiplicados diretamente, resultando em O(1) .
- Caso médio e pior caso: Mantêm a complexidade O(n^{1.585}), pois o algoritmo sempre segue a mesma estrutura recursiva.
A complexidade espacial do algoritmo de Karatsuba depende da profundidade da recursão.
-
Em cada chamada, o algoritmo faz 3 chamadas recursivas.
-
A profundidade da recursão é O(log n) (pois a cada passo os números são reduzidos pela metade).
Levando isto em consideração, a complexidade espacial do algoritmo de Karatsuba não foge de O(log n).