Fatorial em Java utilizando BigInteger

Por
|  

Introdução

O objetivo dessa postagem é apresentar uma implementação do algoritmo clássico para o cálculo do fatorial usando a classe BigInteger da linguagem Java.

A motiva√ß√£o para isso reside no fato dos tipos de dados primitivos n√£o serem capazes de representar com precis√£o o fatorial de n√ļmeros muito grandes (lembrando que todas as informa√ß√Ķes aqui presentes s√£o relacionadas √† linguagem Java).

Como exemplo disso temos os tipos de dados primitivos long e double que s√£o usados para representar n√ļmeros inteiros e n√ļmeros de ponto flutuante respectivamente e possuem a maior capacidade de armazenamento de informa√ß√Ķes entre os tipos num√©ricos (ambos de 64 bits). Entretanto, ao se calcular o fatorial a partir de 21 o tipo long n√£o √© capaz de representar o resultado, pois sua capacidade m√°xima √© ultrapassada. Por outro lado, o tipo double, com sua representa√ß√£o em ponto flutuante, √© capaz de armazenar resultados maiores, por√©m com perda de precis√£o. A partir do fatorial de 171 o tipo double j√° n√£o √© mais capaz de representar o resultado.

Com a classe BigInteger n√£o precisamos nos preocupar com problemas como esse j√° que ela permite representar n√ļmeros inteiros com a precis√£o que quisermos. Naturalmente, quanto maior o n√ļmero, mais mem√≥ria ser√° usada para armazen√°-lo e tamb√©m maior ser√° a capacidade de processamento exigida nas opera√ß√Ķes. Logo, o limite depende do hardware que ir√° executar um algoritmo com essa classe.

A Função Fatorial

Antes de tudo, segue a definição de fatorial (você pode pular isso, caso já conheça):

Seja n um n√ļmero inteiro n√£o negativo (isto √©, n √© positivo ou zero). O fatorial de n, denotado por n!, ser√° dado por

isto √©, multiplicamos entre si todos os n√ļmeros inteiros de 1 at√© n assumindo que 0! = 1 e, obviamente, 1! = 1. Tamb√©m podemos representar o fatorial da seguinte forma

Pela definição, é fácil de ver que podemos implementar o fatorial tanto iterativamente como recursivamente.

A Classe BigInteger

Agora que já revisamos a função fatorial é importante conhecer a classe que trabalharemos: BigInteger. Essa classe pertence ao pacote java.math. Nesta postagem, usaremos apenas alguns recursos dela, mas, caso precise de maiores detalhes, você pode consultar a documentação do Java.

Uma no√ß√£o b√°sica de orienta√ß√£o a objetos √© importante para total compreens√£o do algoritmo, pois ao trabalhar com BigInteger trataremos n√ļmeros como objetos (objetos da classe BigInteger, obviamente).

Existem duas formas simples de criar objetos da classe BigInteger: usando o construtor BigInteger(String val), que cria o objeto a partir de uma String; ou usando o m√©todo est√°tico BigInteger.valueOf(long val), que cria o objeto a partir de um n√ļmero do tipo long e retorna-o. Usaremos este √ļltimo. A classe BigInteger tamb√©m possui outros m√©todos construtores, mas n√£o usaremos aqui.

Outro m√©todo importante √© a multiplica√ß√£o entre objetos BigInteger. Ela √© realizada pelo m√©todo multiply(BigInteger), que multiplica o pr√≥prio objeto que chama o m√©todo pelo objeto passado por par√Ęmetro retornando outro BigInteger com o resultado.

Para visualizar o valor de um objeto BigInteger, podemos usar (como de costume) o método toString(), que retorna uma String com o valor do BigInteger e em seguida imprimimos da maneira desejada (campo de texto, prompt de comando, etc).

Também usaremos frequentemente a constante BigInteger.ONE que é basicamente o valor um em BigInteger.

Os Algoritmos

Nossos algoritmos (iterativo e recursivo) do fatorial ter√£o como par√Ęmetro de entrada um n√ļmero inteiro n maior ou igual a zero. A sa√≠da ser√° um objeto da classe BigInteger. Caso n seja zero, os algoritmos retornar√£o BigInteger.ONE.

Na versão iterativa criaremos uma variável temporária inicializando-a com o valor BigInteger.ONE. Em seguida criaremos um loop for cujo índice irá variar de 2 até n (inicia com 2 porque multiplicar por 1 é desperdício). Se n = 1, o loop não será executado e a variável permanecerá com o valor 1. Caso contrário, o loop será executado multiplicando o valor da variável temporária pelo índice e armazenando o resultado (uma referência de um objeto BigInteger) na própria variável. No fim, o algoritmo retorna o valor da variável temporária.

Na vers√£o recursiva, se n n√£o for zero o algoritmo ir√° multiplicar n pelo fatorial de n-1 retornando o resultado, isto √©, o algoritmo chamar√° a si mesmo at√© alcan√ßar o caso b√°sico n = 0. Ap√≥s atingir o caso b√°sico, o algoritmo ir√° de fato realizar as multiplica√ß√Ķes e retornar o resultado.

Ambas as vers√Ķes rodam em tempo linear, O(n), mas a vers√£o iterativa √© um pouco mais eficaz j√° que a vers√£o recursiva precisa de mais mem√≥ria para o empilhamento de chamadas do pr√≥prio algoritmo.

/*
 * Autor: Henrique Felipe
 * https://www.blogcyberini.com/
 * Julho de 2014
 * 
 * Algoritmos simples do fatorial usando BigInteger.
 * Aqui nao focamos em eficiencia.
 * 
 * Os acentos das palavras nos comentarios foram removidos propositalmente
 * para evitar problemas de codificacao.
 */
import java.math.BigInteger;

public class BasicBigIntFactorial1 {
    //Metodo main com teste dos algoritmos
    public static void main(String[] args) {
        System.out.println("50! = "+basicIterativeFactorial(50));
        System.out.println("50! = "+basicRecursiveFactorial(50));
    }
    //Implementacao iterativa do fatorial.
    private static BigInteger basicIterativeFactorial(int n){
        //caso basico, n = 0, retorna imediatamente o valor 1.
        if(n == 0) return BigInteger.ONE;        
        //Inicializa a variavel fatorial com 1. Ela armazenara o valor n!.
        BigInteger factorial = BigInteger.ONE;
        //Multiplica todos os inteiros de 2 até n. Se n = 1, o loop nao e executado.
        for(int i = 2; i <= n; i++){
            //Cria um objeto BigInteger usando o indice i
            BigInteger indice = BigInteger.valueOf(i);
            //Multiplica o BigInteger factorial pelo indice.
            factorial = factorial.multiply(indice);
        }
        return factorial;
    }
    
    //Implementacao recursiva do fatorial.      
    private static BigInteger basicRecursiveFactorial(int n){
        //caso basico, n = 0, retorna imediatamente o valor 1.
        if(n == 0) return BigInteger.ONE;
        //Cria um objeto BigInteger usando o valor n
        BigInteger m = BigInteger.valueOf(n);
        //Multiplica m (valor de n em BigInteger) pelo fatorial de n - 1
        return m.multiply(basicRecursiveFactorial(n - 1));
    }    
}

Conclus√£o

Nesta postagem, vimos os algoritmos cl√°ssicos para c√°lculo de fatorial, onde, ao inv√©s de utilizarmos tipos de dados primitivos para expressar os resultados, utilizamos a classe BigInteger, nos permitindo trabalhar com a precis√£o que quisermos. Naturalmente, existem outras formas de se calcular o fatorial, algumas delas mais eficientes que a forma apresentada aqui. Uma delas, demonstrada por Peter B. Borwein, consiste em expressar o fatorial em termos de seus fatores primos. Tamb√©m existe a f√≥rmula de Stirling que permite fazer uma boa aproxima√ß√£o do fatorial de n√ļmeros grandes. Ambos os casos fogem do escopo desta postagem.

Download dos Códigos

Estou disponibilizando quatro classes em Java, sendo duas delas contendo as implementa√ß√Ķes iterativas e recursivas do fatorial com retorno em double e em long e outras duas contendo implementa√ß√Ķes utilizando a classe BigInteger. Para baixar as classes, acesse o link a seguir (pasta do Google Drive): Fatorial (classes em Java).

Referências

  • [1] Peter B Borwein, On the complexity of calculating factorials, Journal of Algorithms, Volume 6, Issue 3, September 1985, Pages 376-380.
  • [2] DEITEL, P.; DEITEL, H. Java Como Programar. 8ª ed. S√£o Paulo: Pearson Prentice Hall, 2010.
  • [3] CORMEN, Thomas H; et al. Algoritmos - Teoria e Pr√°tica. 3ª edi√ß√£o. S√£o Paulo: Elsevier - Campus, 2012
  • [4] Oracle. Tutorial Primitive Data Types. Dispon√≠vel em: <https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html>. Acesso em: 28 de julho de 2014.
  • [5] Oracle. Documenta√ß√£o da classe BigInteger. Dispon√≠vel em: <https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html>. Acesso em: 28 de julho de 2014.

Siga o blog

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

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