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.
Nenhum comentário:
Postar um comentário