Potenciação por Quadrados

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 (x²), por isso o nome "potenciação por quadrados" (do inglês, power by squaring ou exponentiation by squaring).

Índice

• Potenciação com Expoente Inteiro
• Algoritmo de Potenciação por Quadrados
  • Expoente Negativo e Validações
  • Otimizações
  • Análise do Algoritmo
• Códigos
  • Algoritmos em Java
  • Algoritmos em C
• Referências

Potenciação com Expoente Inteiro

Suponhamos que você precise calcular 3¹⁰. O jeito mais óbvio de calcular é

3¹⁰ = 3.3.3.3.3.3.3.3.3.3

3¹⁰ = 9.3.3.3.3.3.3.3.3

3¹⁰ = 27.3.3.3.3.3.3.3

...

3¹⁰ = 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 × xⁿ. 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: x² = x × x. Voltando à potência 3¹⁰, observe que podemos agrupar os fatores em dois grupos iguais:

3¹⁰ = (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:

3¹⁰ = (3.3.3.3.3)²

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:

3¹⁰ = (3.(3.3).(3.3))²

3¹⁰ = (3.(3.3)²)²

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

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

xⁿ = (x^n/2)²

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

xⁿ = x.(x^{(n - 1)/2})²

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

Ir para o índice

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 x^n/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 xⁿ = (x^n/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})² que foi apresentada antes.

Ir para o índice

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:

xⁿ = (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...

Ir para o índice

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/2^k. Já na última iteração, o valor de n será 1 (depois será 0 e o loop pára). Então

n/2^k = 1 ⇒ k = log₂ n

Ou seja, o loop será executado log₂ 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.

Ir para o índice

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^(-n)");
        }
        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 base
        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^(-n)");
        }
        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 base
        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));
    }   
}

Ir para o índice

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^(-n)");
        
        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^(-n)");
        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));
    }
}

Ir para o índice

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 base
    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 base
    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.0, 300));
    printf("pow(2, 300) = %.8f\n", pow(2, 300));
    return 0;
}

Ir para o índice

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.