Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Calculando potências em tempo logarítimico

0 votos
34 visitas
perguntada Ago 19 em Ciência da Computação por Caio Oliveira Dantas (16 pontos)  
editado Ago 19 por Caio Oliveira Dantas

Problema 4.2 apresentado no Livro ”Introduction to Recursive Programming“, no Capítulo 4 , página 129.

Implemente uma função recursiva que compute a potência \(b^n\) em tempo logarítmico, para uma base real b, e um inteiro n, que pode ser negativo.

Compartilhe

2 Respostas

0 votos
respondida Ago 19 por Caio Oliveira Dantas (16 pontos)  
editado Ago 19 por Caio Oliveira Dantas

Para ser executado em tempo logarítmico o número de operações realizadas deve crescer menos do que proporcionalmente ao tamanho do input. O algoritmo abaixo faz isso dividindo o expoente por 2 a cada recursão.

def potencia(base, expoente):
    if expoente<0: 
        return potencia(1/base, (-1)*expoente)
    elif expoente == 1:
        return base
    elif expoente == 0:
        return 1
    elif expoente%2==0:
        return potencia(base, expoente/2)**2
    else:
        return base * potencia(base, (expoente-1)/2)**2

if __name__ == "__main__":
    b=float(input('Digite a base: '))
    n=int(input('Digite o expoente: '))
    print(potencia(b, n))
comentou Ago 31 por Fabio Fujita (36 pontos)  
Parabéns pela solução, Caio.
 
O tempo de execução de fato será menor relativamente à execução com tempo linear tradicional, uma vez que se reduz o expoente pela metade a cada etapa da recursão, tornando o problema menor. A conversão feita no primeiro condicional (if expoente<0) basicamente transforma um problema com expoente negativo em um problema com expoente positivo e os demais condicionais implementam o cálculo recursivo de potências em tempo logarítmico.

A única observação que tenho é a de que o condicional "elif expoente==1" é opcional. Implementado, reduz a execução em uma recursão, mas com o tradeoff de fazer a verificação da condição a cada vez que a função potencia for chamada. Caso não tivesse sido implementado, o resultado seria o mesmo. Tenho a impressão de que a decisão de implementar ou não esse condicional dependerá do expoente e do tempo gasto nas verificações dos condicionais versus a execução de uma recursão adicional.
comentou Set 2 por Caio Oliveira Dantas (16 pontos)  
Bem observado Fábio, vou implementar um medidor de tempo de execução para descobrir aproximadamente a partir de qual expoente esse condicional adicional deixa de ser eficiente.
0 votos
respondida Set 2 por Caio Oliveira Dantas (16 pontos)  
editado Set 2 por Caio Oliveira Dantas

Conforme sugestão do Fabio, o algoritmo abaixo testa se a inclusão de uma cláusula condicional que reduz o número de recursões em 1 é temporalmente eficiente. Com base 2 e expoentes de 2 a 999, o tempo de execução é melhor sem a cláusula 22 vezes, melhor com a cláusula 21 vezes e indiferente 955 vezes. Com base 3, os resultados são 26, 23 e 949. Com base 10, são 31, 28 e 939.

Aparentemente a diferença é indetectável mais de 90% das vezes, mas a exclusão da cláusula parece ser levemente vantajosa.

import time
t1=0
t2=0

def potencia1(base, expoente):
    global t1
    if expoente<0: 
        t1=time.time() - start_time1
        return potencia1(1/base, (-1)*expoente)
    elif expoente == 0:
        t1=time.time() - start_time1
        return 1
    elif expoente%2==0:
        return potencia1(base, expoente/2)**2
    else:
        return base * potencia1(base, (expoente-1)/2)**2

def potencia2(base, expoente):
    global t2
    if expoente<0: 
        return potencia2(1/base, (-1)*expoente)
    elif expoente == 1:
        t2=time.time() - start_time2
        return base
    elif expoente == 0:
        t2=time.time() - start_time2
        return 1
    elif expoente%2==0:
        return potencia2(base, expoente/2)**2
    else:
        return base * potencia2(base, (expoente-1)/2)**2

if __name__ == "__main__":
    b=2
    i=0
    j=0
    k=0

    for n in range(2,1000):
        start_time1 = time.time()
        potencia1(b, n)
        start_time2 = time.time()
        potencia2(b, n)
        if t2>t1: 
            i+=1
        elif t2<t1:
            j+=1
        else:
            k+=1

    print(i, j, k)
...