Multiplicação de inteiros

Multiplicação de inteiros

Problema: Multiplicar dois números inteiros. Na solução clássica o resultado da multiplicação é obtido pela multiplicação de cada y por cada x com o deslocamentos correspondentes, como por exemplo: 41 x 12 = 2*1 + (2*4)*10 + (1*1)*10 + (1*4)*100 = 2 + 80 + 10 + 400 = 492 Na multiplicação de dois números, são feitas multiplicações por digito, sendo assim tem custo O(n2), sendo n o número de dígitos dos números, pois são necessárias n2 operações. Algoritmo MultiplicacaoForcaBruta(x,y) Entrada : 2 inteiros com valor invertido x e y com n dígitos Saída : o produto de x e y Sejam as funções getDigitos(x,n) retorna o inteiro na n-ésima posição do inteiro x dígitos(x) retorna o número de dígitos de x MultiplicacaoForcaBruta(x,y) 1 total=0; 1 for i = 0 to digitos(y) \\n 2 do multY=0; 3 for j = 0 to digitos(x) \\k=0nk j=0ntj 4 do multY=multY+getDigitos(y,i)*getDigitos(x,j)*10^j; \\k=0n6k 5 total=total+multY*10^i; \\3n 6 return total; Cálculo do custo do algoritmo MultiplicacaoForcaBruta k=0n6k=6nn+12=3n2+3n
Considerando : g(n) = 3n2+3n e f(n) = n2
Devemos provar que g(n) = θ(f(n))
Para isto vamos mostrar que existem constantes positivas n0 e A (A ≠ 0) e B (B ≠ 0), tais que Af(n) ≤ g(n) ≤ Bf(n) para todo n ≥ n0 An2 ≤ 3n2+3n ≤ Bn2 An2- 3n2 ≤ 3n ≤ Bn2-3n2
(A-3)n2 ≤ 3n ≤ (B-3)n2 (A-3)n ≤ 3 ≤ (B-3)n
Portanto como n é uma constante positiva, com n0=1 temos que
(A-3) ≤ 3 ≤ (B-3)
(A-3) ≤ 3 e 3 ≤ (B-3)
6 ≤ B
A ≤ 6
Então para A = 5 e B = 7 e n0>1, a desigualdade Af(n) ≤ g(n) ≤ Bf(n) é verdadeira, concluindo assim que 3n2+3n = θ(n2).

Técnica Dividir e Conquistar: Primeiro algoritmo Sejam X e Y números inteiros de n dígitos. Assuma: X = 10n/2a + b Y = 10n/2c + d a, b, c, d são números de tamanho n/2 dígitos.

XY = (a10n/2 + b) (c10n/2 + d)