Potenciação por Quadrados

Por
|  

Nesta postagem, apresento um algoritmo que permite calcular potências com expoente inteiro em tempo logarítmico e a implementação dele nas linguagens de programação Java e C.

Trata-se de um algoritmo de divisão e conquista que calcula uma potência utilizando quadrados (x2), por isso o nome "potenciação por quadrados" (do inglês, power by squaring ou exponentiation by squaring).

Potenciação com Expoente Inteiro

Suponhamos que você precise calcular 310. O jeito mais óbvio de calcular é

310 = 3.3.3.3.3.3.3.3.3.3

310 = 9.3.3.3.3.3.3.3.3

310 = 27.3.3.3.3.3.3.3

...

310 = 59049.

Isto é, 9 multiplicações. Para um expoente inteiro qualquer n, você precisaria computar n - 1 multiplicações utilizando o método descrito. O algoritmo que representa esse método (com uma pequena mudança) é descrito a seguir:

1. potlinear(x, n)
2.      resultado ← 1
3.      para i ← até n
4.           resultado = resultado * x
5.      fim_para
6.      retorne resultado
7. fim_potlinear

Observe que o algoritmo realiza uma multiplicação extra. Isso ocorre porque ele calcula 1 × xn. Entretanto, com ou sem multiplicação extra, o algoritmo potlinear tem complexidade O(n).

Será que é possível realizar o mesmo cálculo com menos multiplicações? A resposta é sim e o cálculo é realizado pelo algoritmo de potenciação por quadrados.

Antes de apresentar o algoritmo, irei expor a ideia por trás dele. Primeiramente, devemos lembrar que o quadrado de um número é realizado utilizando uma única multiplicação: x2 = x × x. Voltando à potência 310, observe que podemos agrupar os fatores em dois grupos iguais:

310 = (3.3.3.3.3).(3.3.3.3.3)

Cada grupo possui 4 multiplicações. Como eles são iguais, então basta calcular o valor de um deles e elevar ao quadrado para saber o resultado:

310 = (3.3.3.3.3)2

Ou seja, agora precisamos de apenas 5 multiplicações: uma multiplicação do quadrado e, dentro dos parênteses, temos mais 4 multiplicações. Portanto, o número total de multiplicações foi reduzido aproximadamente pela metade (antes eram 9 multiplicações).

Obviamente, nada nos impede de repetir o procedimento para as multiplicações que estão dentro dos parênteses. Entretanto, o número de fatores agora é ímpar, portanto não é possível obter dois grupos iguais. Para resolver esse problema, vamos deixar um fator fora do agrupamento:

310 = (3.(3.3).(3.3))2

310 = (3.(3.3)2)2

Agora precisamos de 4 multiplicações para calcular 310: dois quadrados e duas multiplicações.

Em síntese, se o expoente é par, então calculamos

xn = (xn/2)2

Por outro lado, se o expoente é ímpar, então calculamos:

xn = x.(x(n - 1)/2)2

O algoritmo é recursivo, pois o cálculo de xn/2 e de x(n - 1)/2 é realizado reaplicando o mesmo procedimento. O caso base do algoritmo ocorre quando o expoente é igual a zero: x0 = 1 (x ≠ 0).

Algoritmo de Potenciação por Quadrados

O algoritmo que exprime a lógica descrita na seção anterior é apresentado a seguir:

1. potQuad(x, n)
2.      se (n = 0)
3.           retorne 1
4.      fim_se
5.
6.      se (n é par)
7.           p ← potQuad(x, n/2)
8.           retorne p * p
9.      senão
10.          p ← potQuad(x, (n - 1)/2)
11.          retorne x * p * p
12.     fim_se
13.fim_potQuad

Esse é o algoritmo bruto. Na hora de codificá-lo, você precisa fazer validações nos valores de x e n para evitar problemas como elevar zero a zero e elevar zero a números negativos. Além disso, ele não funciona com expoentes negativos, mas apresentarei como resolver esse problema depois. Primeiramente, analisaremos o algoritmo.

As linhas 2-4 avaliam o caso base. Se o expoente n for igual a zero, então ele retornará 1. A linha 6 avalia se o expoente é par. Em caso positivo, uma chamada recursiva é realizada para calcular xn/2 e o valor retornado será armazenado na variável p. Em seguida, na linha 8, o valor p * p é retornado. Observe que esse trecho corresponde à fórmula xn = (xn/2)2, que foi apresentada anteriormente.

Caso o expoente não seja par, então a linha 10 calculará o valor de x(n - 1)/2 recursivamente e armazenará o resultado na variável p. Depois, na linha 11, o algoritmo retorna o valor x * p * p. Isto é, quando o expoente é ímpar o algoritmo calculará a fórmula x.(x(n - 1)/2)2 que foi apresentada antes.

Expoente Negativo e Validações

Para que o algoritmo aceite expoentes negativos, basta adicionar o seguinte trecho de código no início do algoritmo

se (n < 0)
     retorne potQuad(1/x, -n)
fim_se

Esse código corresponde a uma das propriedades da potenciação, que permite converter uma potência com expoente negativo numa potência com expoente positivo invertendo a base:

xn = (1/x)-n.

Como o algoritmo é recursivo, então seria redundante realizar essa conversão e as validações a cada chamada recursiva. O ideal é fazer isso em um método separado e deixar apenas o que é essencial no algoritmo. Faremos isso nas implementações do algoritmo em Java e em C.

Otimizações

Observe que, além das multiplicações, o algoritmo realiza algumas operações aritméticas extras. A subtração na linha 10 é redundante, pois como n é ímpar e a divisão é inteira, então n/2 = (n - 1)/2.

Com essa otimização, as linhas 7 e 10 serão idênticas e, portanto, podemos fatorar o código:

1. potQuad(x, n)
2.      se (n = 0)
3.           retorne 1
4.      fim_se
5.
6.      p ← potQuad(x, n/2)
7.      se (n é par)          
8.           retorne p * p
9.      senão
10.          retorne x * p * p
11.     fim_se
12.fim_potQuad

Também podemos otimizar as divisões por 2. Podemos substituir n/2 por deslocamento de bits à direita que, em geral, requer menos ciclos de processamento do que a divisão: n/2 = n >> 1.

1. potQuad(x, n)
2.      se (n = 0)
3.           retorne 1
4.      fim_se
5.
6.      p ← potQuad(x, n >> 1)
7.      se (n é par)          
8.           retorne p * p
9.      senão
10.          retorne x * p * p
11.     fim_se
12.fim_potQuad

Outra otimização possível está relacionada à verificação da paridade do expoente. Em geral, para checar se um inteiro é par, verificamos se o resto da divisão por 2 é igual a zero: n % 2 == 0. Podemos substituir o trecho n % 2 por n & 1, onde & é o operador lógico bitwise AND (eu não sei como ele é chamado em português). Em geral, a operação n & 1 requer menos ciclos de processamento do que a operação n % 2.

É claro, alguns compiladores já fazem otimizações no código, então você não precisa realizar essas otimizações caso o compilador da sua linguagem já faça isso.

Análise do Algoritmo

O algoritmo de potenciação por quadrados tem a mesma equação de recorrência da busca binária

T(n) = T(n/2) + Θ(1).

A cada chamada recursiva, o expoente é reduzido pela metade e o custo computacional por chamada é Θ(1). Portanto, T(n) = O(log n). Você pode resolver a equação de diversas formas: árvore de recursão, teorema mestre, método de Akra-Bazzi...

Versão Iterativa

Há também uma versão iterativa para o algoritmo, entretanto ela não é tão intuitiva quanto a versão recursiva:

1. potQuadIter(x, n)
2.      p ← 1
3.      enquanto(n > 0)
4.           se (n é ímpar)
5.                p ← p * x
6.           fim_se
7.           x ← x * x
8.           n ← n/2
9.      fim_enquanto
10.     retorne p
11.fim_potQuadIter

O algoritmo iterativo também é O(log n). Na k-ésima iteração, o valor de n será n/2k. Já na última iteração, o valor de n será 1 (depois será 0 e o loop pára). Então

n/2k = 1 ⇒ k = log2 n

Ou seja, o loop será executado log2 n vezes, portanto a complexidade no tempo é O(log n).

Apesar de a complexidade ser a mesma da versão recursiva, em geral os algoritmos iterativos são mais rápidos.

Códigos

Nesta seção, apresento os algoritmos codificados nas linguagens Java e C.

Algoritmos em Java

Versão recursiva:

//Código por Henrique Felipe (GitHub: HenriqueIni)
public class PowerBySquaringRecursive {    
    //VERSÃO SEM OTIMIZAÇÕES
    //x é a base, n é o expoente. Este método apenas faz validações
    public static double potQuad(double x, int n){
        if(x == 0 && n == 0){
            throw new ArithmeticException("It's not possible to compute 0^0");
        }
        if(x == 0 && n < 0){
            throw new ArithmeticException("It's not possible to compute 0 to the power of a negative number");
        }
        if(x == 0) return 0;
        if(n < 0) return potQuadAlg(1/x, -n); //expoente negativo
        return potQuadAlg(x, n);
    }
    //Este método calcula x^n, se x e n forem válidos
    private static double potQuadAlg(double x, int n){
        //caso básico
        if(n == 0) return 1;
        if(n % 2 == 0){//n é par
            double p = potQuadAlg(x, n/2);
            return p * p;
        }else{//n é ímpar
            double p = potQuadAlg(x, (n - 1)/2);
            return x * p * p;
        }
    }
    
    //VERSÃO COM OTIMIZAÇÕES
    //x é a base, n é o expoente. Este método apenas faz validações
    public static double potQuadOpt(double x, int n){
        if(x == 0 && n == 0){
            throw new ArithmeticException("It's not possible to compute 0^0");
        }
        if(x == 0 && n < 0){
            throw new ArithmeticException("It's not possible to compute 0 to the power of a negative number");
        }
        if(x == 0) return 0;
        if(n < 0) return potQuadAlgOpt(1/x, -n);
        return potQuadAlgOpt(x, n);
    }
    //Este método calcula x^n, se x e n forem válidos
    private static double potQuadAlgOpt(double x, int n){
        //Caso básico
        if(n == 0) return 1;
        double p = potQuadAlgOpt(x, n >> 1);
        if((n & 1) == 0){//n é par
            return p * p;
        }else{//n é ímpar
            return x * p * p;
        }
    }
    //Testes
    public static void main(String[] a){        
        System.out.println("potQuad(2, 300) = " + potQuad(2, 300));
        System.out.println("potQuadOpt(2, 300) = " + potQuadOpt(2, 300));
        System.out.println("Math.pow(2, 300) = " + Math.pow(2, 300));
    }   
}
            

Versão iterativa:

//Código por Henrique Felipe (GitHub: HenriqueIni)
public class PowerBySquaringIterative {
    //VERSÃO SEM OTIMIZAÇÕES
    public static double potQuadIter(double x, int n){
        if(x == 0 && n == 0)
            throw new ArithmeticException("It's not possible to compute 0^0");        
        if(x == 0 && n < 0)
            throw new ArithmeticException("It's not possible to compute 0 to the power of a negative number");
        
        if(x == 0)
            return 0;
        if(n < 0)
            return potQuadIter(1/x, -n);
        
        double p = 1;
        int exp = n; //redundante
        double base = x; //redundante
        while(exp > 0){
            if(exp % 2 != 0)
                p *=  base;
            base *= base;
            exp /= 2;
        }
        return p;
    }
    //VERSÃO COM OTIMIZAÇÕES
    public static double potQuadIterOpt(double x, int n){
        if(x == 0 && n == 0)
            throw new ArithmeticException("It's not possible to compute 0^0");
        if(x == 0 && n < 0)
            throw new ArithmeticException("It's not possible to compute 0 to the power of a negative number");
        if(x == 0)
            return 0;
        if(n < 0)
            return potQuadIterOpt(1/x, -n);
        
        double p = 1;
        while(n > 0){
            if((n & 1) != 0)
                p *=  x;
            x *= x;
            n >>= 1;
        }
        return p;
    }
    //Testes
    public static void main(String[] a){        
        System.out.println("potQuadIter(2, 300) = " + potQuadIter(2, 300));
        System.out.println("potQuadIterOpt(2, 300) = " + potQuadIter(2, 300));
        System.out.println("Math.pow(2, 300) = " + Math.pow(2, 300));
    }
}
            

Algoritmos em C

Coloquei todas versões num mesmo arquivo:

//Código por Henrique Felipe (GitHub: HenriqueIni)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//**************ALGORITMOS RECURSIVOS**************
//VERSÃO SEM OTIMIZAÇÕES - x e n precisam ser válidos
double potQuad(double x, int n) {
    if(n < 0)
        return potQuad(1/x, -n);
    //caso básico
    if (n == 0)
        return 1;
    if (n % 2 == 0) {//n é  par
        double p = potQuad(x, n / 2);
        return p * p;
    } else {//n é ímpar
        double p = potQuad(x, (n - 1) / 2);
        return x * p * p;
    }
}
//VERSÃO COM OTIMIZAÇÕES - x e n precisam ser válidos
double potQuadAlgOpt(double x, int n) {    
    if(n < 0)
        return potQuadAlgOpt(1/x, -n);
    //caso básico
    if (n == 0) return 1;
    double p = potQuadAlgOpt(x, n >> 1);
    if ((n & 1) == 0) {//n é par
        return p * p;
    } else {//n é ímpar
        return x * p * p;
    }
}
//**************ALGORITMOS ITERATIVOS**************
//VERSÃO SEM OTIMIZAÇÕES - x e n precisam ser válidos
double potQuadIter(double x, int n) {
    if (n < 0)
        return potQuadIter(1 / x, -n);

    double p = 1;
    int exp = n; //redundante
    double base = x; //redundante
    while (exp > 0) {
        if (exp % 2 != 0)
            p *= base;
        base *= base;
        exp /= 2;
    }
    return p;
}

//VERSÃO COM OTIMIZAÇÕES - x e n precisam ser válidos
double potQuadIterOpt(double x, int n) {
    if (n < 0)
        return potQuadIterOpt(1 / x, -n);

    double p = 1;
    while (n > 0) {
        if ((n & 1) != 0)
            p *= x;
        x *= x;
        n >>= 1;
    }
    return p;
}
//Testes
int main() {
    printf("potQuad(2, 300) = %.8f\n", potQuad(2, 300));
    printf("potQuadAlgOpt(2, 300) = %.8f\n", potQuadAlgOpt(2, 300));
    printf("potQuadIter(2, 300) = %.8f\n", potQuadIter(2, 300));
    printf("potQuadIterOpt(2, 300) = %.8f\n", potQuadIterOpt(2, 300));
    printf("pow(2, 300) = %.8f\n", pow(2, 300));
    return 0;
}
            

Referências

GONÇALVES, L. Notas de aula - Estruturas de Dados I. São Paulo: Universidade Cruzeiro do Sul, 2014.

GONÇALVES, L. Notas de aula - Projeto de Linguagens de Programação. São Paulo: Universidade Cruzeiro do Sul, 2016.

Questão 29 do POSCOMP 2006 sobre Fundamentos da Computação.

Questão do Stackoverflow sobre como checar a paridade de um número: Check whether number is even or odd.

Observações

Foi feita uma correção nos códigos em Java e em C no dia 11 de abril de 2018, pois as funções/métodos otimizados estavam chamando as funções/métodos comuns.


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário