Relatório Algoritimos Matrizes Strassen e Karatsuba

Prévia do material em texto

1 INTRODUÇÃO 
 
O desempenho e a rapidez de algoritmos na resolução de problemas é fundamental 
e exigido em diversos casos. Dois desses, é a multiplicação de matrizes de tamanho N x N 
e de números grandes, onde algoritmos como o de Strassen e Karatsuba ganham destaque 
no tempo de execução comparando com os que não são implementados com o método de 
Divisão e Conquista. 
 
 
2 ALGORITMOS DE DIVISÃO E CONQUISTA 
 
 
2.1 KARATSUBA 
 
Método de Multiplicação de Karatsuba é um método para multiplicar números 
grandes eficientemente, descoberto por Anatolii Alexeievitch Karatsuba em 1960 e 
publicado em 1962. 
Este algoritmo reduz a multiplicação de dois números de N dígitos a no 
máximo aproximadamente, e portanto, é mais rápido que o método usual deN 1.5849 
multiplicação longa, que necessita de N² multiplicações de um dígito simples. 
 
 
2.2 STRASSEN 
 
O algoritmo de Strassen, cujo nome é uma referência ao matemático Volker 
Strassen, seu criador, é um alg​oritmo utilizado para realizar a multiplicação de 
matrizes. Ele é assintoticamente mais rápido que o algoritmo tradicional, e é útil na 
prática ao lidar com matrizes grandes. 
A multiplicação usual de matrizes exige aproximadamente 2​N​3 (em que ​N = 
2​n​) operações aritméticas (adições e multiplicações), de modo que sua complexidade 
assintótica é O(​N​3​). 
No caso do algoritmo de Strassen, o número de adições e multiplicações 
necessárias pode ser calculado como segue: seja ​f​(​n​) o número de operações para 
uma matriz 2​n × 2​n​. Então, por meio de uma aplicação recursiva do algoritmo de 
Strassen algorithm, resulta que ​f​(​n​) = 7​f​(​n​-1) + ​l​4​n​, para alguma constante ​l que 
depende do número de adições executadas a cada aplicação do algoritmo. Assim, 
f​(​n​) = (7 + O(1))​n​, ou seja, a complexidade assintótica da multiplicação de matrizes 
de tamanho ​N​ = 2​n​ por meio do método de Strassen é, aproximadamente, N 2.807 
 
3 COMPARAÇÃO DE TEMPO DE EXECUÇÃO 
 
3.1 CONFIGURAÇÃO DO CPU E ENTRADAS 
Para análise e comparação dos algoritmos usou-se entradas (N) na base 2 
(10,100,200,400,800,1600,3200) e uma CPU com as seguintes características: 
1. Processador CORE I5 2.4 GHz 
2. Memória 8GB 
3. Sistema 64 bits 
Como o algoritmo de Karatsuba precisou um número com dígitos maiores 
que o padrão para obter-se um resultado significativo, adotou-se este padrão de 
entrada (100,1000,2000,4000,8000,16000,32000,64000) para N. 
 
 
 
 
 
3.2 SOMA E MULTIPLICAÇÃO DE NÚMEROS GRANDES 
O tempo de execução de um algoritmo de multiplicação e soma de números 
binários de tamanho N é da ordem de O(N²) e O(N) respectivamente. Observando o 
Gráfico 1, a linha azul (multiplicação) cresceu muito mais rápido que a vermelha 
(soma), comprovando na prática que sua ordem é de O(N²). Devido a 
implementação e custo de memória, o gráfico da soma teve uma pequena curvatura, 
deixando de ser exatamente linear, mas não podendo ser comparado com uma 
ordem de O(N²), conforme a tabela a seguir: 
Números Binários 
N Multiplicação t(ms) Soma t(ms) 
10 0,00001 0,001 
100 0,000084 0,002 
200 0,000401 0,004 
400 0,001394 0,007 
800 0,006268 0,014 
1600 0,022036 0,028 
3200 0,088384 0,056 
6400 0,352533 0,112 
Tabela 1: Dados comparativos de tempo(ms) entre soma e multiplicação de números 
binários de tamanho N. 
 
A seguir, o gráfico tempo x n da soma e multiplicação. 
 
Gráfico 1: Gráfico comparação entre Multiplicação e Soma de Números Binários 
Grandes de tamanho N 
 
 
3.3 SOMA E MULTIPLICAÇÃO DE MATRIZES QUADRADAS 
 
Já a multiplicação e soma de matrizes quadradas binárias de tamanho 
, possuem tempo na ordem de O(N³) e O(N²) respectivamente, que pode ser 2N = n 
observado no gráfico 2 e os dados utilizados na Tabela 2. 
 
 
Matrizes quadradas 
N Multiplicação t(ms) Soma t(ms) 
100 0,0053905 0,048213 
200 0,045529115 0,176353 
400 0,337871277 0,692052 
800 2.660,993 2.759,676 
1600 20.669,998 10.696,520 
3200 166.638,655 42.786,932 
Tabela 2: Dados comparativos de tempo(ms) entre soma e multiplicação de matrizes 
binárias de tamanho N X N. 
 
A seguir, o gráfico tempo x n da soma e multiplicação. 
 
Gráfico 2: Comparação entre Multiplicação e Soma de Matrizes Quadráticas Binárias 
de tamanho N x N. 
 
 
 
 
 
3.3 KARATSUBA VS NÚMEROS GRANDES 
 
Karatsuba, por sua vez, não teve um tempo melhor que a multiplicação 
normal até os 8000 dígitos, tendo apenas um desempenho consideravelmente 
melhor a partir de 16000 dígitos em diante, como demonstra o gráfico 3. 
 
Gráfico 3: Comparação do tempo de execução do Karatsuba com a Multiplicação de 
Números grandes Normal. 
 
 
A seguir, a tabela com o tempo de execução e tamanho da entrada N. 
 
N Karatsuba(ms) Números grandes normal(ms) 
100 0,000668 0,000104 
1000 0,025201 0,008826 
2000 0,1273 0,033493 
8000 0,694886 0,543427 
16000 2.042,833 2.167,687 
32000 6.395,938 8.788,254 
64000 18.294,645 34.971,550 
Tabela 3:​ ​Dados comparativos de tempo(ms) entre Strassen e multiplicação de 
números de tamanho N. 
 
 
 
 
3.3 STRASSEN VS MULTIPLICAÇÃO DE MATRIZES 
 
Strassen mostrou-se melhor que a multiplicação apenas para N maiores que 
8000 (Gráfico 4) e com um consumo de memória, como demonstra o Gráfico 5, 
muito maior, limitando o processo de comparação, devido a limitação de memória do 
CPU. 
 
Gráfico 4: Comparação do tempo de execução do Strassen com a Multiplicação de 
Matrizes Grandes NxN 
 
 
A seguir, a tabela com o tempo de execução e tamanho da entrada N. 
 
N Strassen(ms) Multiplicação Matrizes(ms) 
100 0,011099 0,005162 
200 0,077132 0,041026 
400 0,55359 0,218469 
800 3,931115 2,596858 
1600 27,687559 20,420945 
3200 193,950711 168,82589 
8000 3573,2468 4519,9981 
 
 
 
 
 
 
 
 
Notou-se que o consumo de memória no algoritmo de Strassen é excessivo 
se comparado com o algoritmo normal de multiplicação de matrizes, pelo motivo de 
que cada chamada recursiva é necessário alocar uma quantidade de N/2 na 
memória, custando muito para o CPU. Segue abaixo o gráfico: 
 
 
 Gráfico 5: Comparação Uso De Memória Strassen VS Multiplicar Matrizes Normal 
 
 
 
Tabela utilizada para montar o gráfico de memória: 
 
MATRIZES NXN STRASSEN(MB) MULTIPLICA(MB) 
100 1,4 1,4 
200 1,7 1,5 
400 3,3 1,6 
800 14,8 2,1 
1600 115,2 2,2 
3200 765,9 31,3 
 
 
 
 
 
 
 
4 CONCLUSÃO 
 
Com pequenas diferenças, considerando o tipo de implementação e configuração do 
CPU, a execução dos algoritmos propostos atenderam ao esperado. Mostrando que para 
tamanhos muito grandes os algoritmos de Strassen e Karatsuba são mais rápidos que os 
métodos normais. 
Durante o desenvolvimento houve grande dificuldade na implementação do 
Karatsuba pelo fato de alocação de memória de deslocamento de caracteres. A única saída 
encontrada foi transformar o resultado em binários para decimal.