Dados dois inteiros a e b de n bits cada, podemos aplicar o algoritmo de Euclides para obter o mdc(a, b). Ao estudar este algoritmo, Dylan foi desafiado a obter um algoritmo por divisão e conquista para obter mdc(a, b). Ele teve a seguinte inspiração divina:
mdc(a, b)= 2 m d c(a / 2, b / 2), & se a, b são pares m d c(a, b / 2), & se a é ímpar, b é par m d c((a-b) / 2, b), & se a, b são ímpares ãéíéãí
Dessa fez, Dylan precisava ir para a academia, então ele deixou para concluir sua tarefa quando voltasse:
(a) Dylan precisa provar que sua ideia está correta. Prove, matematicamente, que ele tem uma intuição muito boa.
Resposta:
Se a e b são pares, 2 é um divisor comum de a e b. Assim, o m d c(a, b) será igual a duas vezes m d c(a / 2, b / 2). Se a é ímpar e b é par, então 2 não é divisor de a, e portanto, podemos remover 2 da fatoração de b sem problema, dado que não é divisor comum de a e b. Se a e b são ímpares, temos que a-b é par. Além disso, m d c(a, b)=m d c(a-b, b). Portanto, pelo caso anterior temos que m d c(a, b)=m d c(a-b, b)=m d c((a-b) / 2, b).
(b) Escreva um algoritmo recursivo baseado na ideia de Dylan. Resposta:
mdc(a,b):
se a=b então:
retorne a
senão se (a é par & b é par):
retorne 2.mdc(a/2,b/2)
senão se (a é ímpar & b é par):
retorne mdc(a,b/2)
senão se (a é ímpar & b é ímpar & a>b):
retorne mdc((a-b)/2,b)
senão se (a é ímpar & b é ímpar & a<b):
retorne mdc(a,(b-a)/2)
© Qual a relação de recorrência do algoritmo o item 9b? Qual a complexidade deste algoritmo? (Dica: dado um inteiro x com n bits, x / 2 possui n-1 bits).
Resposta:
Assuma que a e b são números com n-bits. Assim, o tamanho de a e b é 2 n bits. Considerando as condições, todos os casos, exceto quando a é ímpar e b é par, diminui o tamanho de a e b para 2 n-2 bits, enquanto quando a é ímpar e b é par diminui para 2 n-1 bits. Cada operação possui tempo constante, dado que estamos multiplicação ou dividindo os números por 2. Para os casos de subtração de dois números n-bits cada, temos c n operações, para c é uma constante. Dessa forma, o pior caso da recorrência é dado por:
ll T(2 n) & =T(2 n-1)+c n T(2 n-1) & =T(2 n-2)+c n T(2 n-2) & =T(2 n-3)+c(n-1) dois operandos possuem n-1 bits T(2 n-3)=T(2 n-4)+c(n-1) cdots & T(2) & =T(1)+c
Assim, T(2 n)=2 c sumi=1^n i. O que implica em O(n^2).
(d) Dylan obteve algum ganho de complexidade em relação ao algoritmo de Euclides? (Dica: lembre da complexidade da multiplicação de dois inteiros de n bits cada, assim como da dica do item 9c).
Resposta:
O algoritmo de Euclides possui complexidade O(n^3). Assim, o algoritmo do item anterior é mais eficiente.

Passo 1

O enunciado pede para validar e implementar uma versão “dividir e conquistar” do cálculo de gcd(a,b) usando apenas subtrações e divisões por 2, e depois analisar a recorrência e comparar com o método clássico de Euclides. Vamos precisar usar propriedades básicas de gcd, especialmente: extração de fator 2 e o fato de gcd(a,b)=gcd(a-b,b).

Passo 2

Prova de corretude:
– Se a e b são pares, escrevemos a=2a' e b=2b'. Então qualquer divisor comum de a,b também divide 2a',2b' e vice-versa, logo:
gcd(a,b)=2;gcd(a',b')
– Se a é ímpar e b=2b' é par, como 2 não divide a, podemos “tirar” o 2 de b sem afetar o gcd:
gcd(a,b)=gcd(a,2b')=gcd(a,b')
– Se a e b são ímpares, então a-b é par e valem ainda as propriedades:
gcd(a,b)=gcd(a-b,b),
e, escrevendo a-b=2c, volta ao caso anterior:
gcd(a,b)=gcd(2c,b)=gcd(c,b)

Passo 3

Algoritmo recursivo em pseudocódigo (supondo entrada a,b>=0):
se a=0 retorne (b);
se b=0 retorne (a);
se a=b) retorne (a);
se a e b são pares então retorne 2timesgcd(a/2,b/2);
se a é ímpar e b é par então retorne gcd(a,b/2);
se a é par e b é ímpar então retorne gcd(a/2,b);
// agora a e b são ímpares
se a>b) retorne gcd((a-b)/2,b) senão retorne gcd(a,(b-a)/2).

Passo 4

Análise de complexidade: Cada chamada faz no máximo uma subtração (custo O(n) para números de n bits) e/ou divisões por 2 (shift de bits, O(1)). Em todo caso a cada recursão o tamanho em bits de algum operando cai em pelo menos 1, gerando a recorrência
T(n)=T(n-1)+O(n)
Somando de 1 até n T(n)=O(n^2).

Passo 5

Comparação com Euclides clássico: O método de Euclides usa divisões (custo M(n), a complexidade de multiplicação/divisão de inteiros de n bits) repetidas O(n) vezes, resultando em O(n,M(n)). Com multiplicação bruta M(n)=O(n^2), isso dá O(n^3), logo o algoritmo “shift-subtraction” de Dylan é O(n^2) e melhora sobre o Euclides tradicional.

Resposta

(a) Usando que gcd(2a,2b)=2gcd(a,b), gcd(a,2b)=gcd(a,b) e gcd(a,b)=gcd(a-b,b), mostra-se que cada caso reduz corretamente o problema.
(b) Pseudocódigo recursivo:
se a=0 retorne b; se b=0 retorne a; se a=b retorne a;
se ambos pares: retorne 2·gcd(a/2,b/2);
se a ímpar e b par: retorne gcd(a,b/2);
se a par e b ímpar: retorne gcd(a/2,b);
caso ambos ímpares: retorne gcd((|a–b|)/2, maior(a,b)).
© Relação de recorrência: T(n)=T(n-1)+O(n) ⇒ complexidade O(n^2).
(d) Sim. O Euclides clássico é O(n,M(n)) (por exemplo O(n^3) com multiplicação quadrática), enquanto o de Dylan é O(n^2), portanto há ganho.

Exercícios relacionados