Programação com números inteiros gigantes
Quanto é o fatorial de 5? 120, fácil, não? E quanto é o fatorial de 6000? É um número com 20 mil dígitos. És capaz de escrever um programa que calcule isto? Depois de ler este artigo, você será!
Parte 4: E existe algo que o Java não tenha?
Desafiando alunos a realizarem a quebra do N, cometi, certa vez, a "bobagem" de dizer que Java era lento! Na verdade era epenas uma brincadeira, uma alfinetada como as que faço quando o assunto é sistemas operacionais.
Esta minha brincadeira feriu os sentimentos de um saudoso aluno que se esforçou para me provar que eu estava enganado. Ele nem quis os décimos pontos na prova como prêmio para quem quebrasse o N, mas apenas me enviou um programa em Java e alguns parâmetros extra-terrestres a serem passados para a máquina Virtual Java a fim de otimizá-la.
Resumo da estória: a solução em Java realmente empatou com a solução em C, considerando a mesma lógica. Quem mandou brincar com um arquiteto certificado pela SUN (e acho que se o Diego Pacheco ler isto, terei problemas, pois sei que ele ainda quer mostrar que o Java é melhor! Grande Diego!).
Não passei a programar em Java depois disto, mas tive que ter mais critérios ao fazer meus comentários em sala de aula.
Basicamente em Java basta usar alguma classe que forneça suporte a números Big. Uma delas é justamente a classe BigDecimal.
Como exemplo, segue um código em java para o cálculo de fatoriais (uma adaptação do código fornecido por Diego Pacheco):
Salve este código com o nome Fatorial.java (mesmo nome da classe), compile usando o javac (isto é, gere os bytes codes) e execute com java Fatorial 200:
javac Fatorial.java
$ java Fatorial 200
200 = 7886578673647905035523632139321850622951359776871732
63294742533244359449963403342920304284011984623904177212138919638
83025764279024263710506192662495282993111346285727076331723739698
89439224456214516642402540332918641312274282948532775242424075739
03240321257405579568660226031904170324062351700858796178922222789
623703897374720000000000000000000000000000000000000000000000000
Como o Java não tem suporte nativo a números grandes, tudo precisa ser feito através de métodos. Isto é, não é possível comparar duas variáveis em um laço apenas com um < ou >. É necessário executar um método próprio para isto, como:
Todas as demais operações são métodos, como a de soma, multiplicação e divisão. Somente as linguagens que tem suporte nativo em sua sintaxe, como é o caso do python, permitem usar as operações aritméticas normais. No entanto o Java, assim como o Python, consegue imprimir o valor sem a necessidade de expressar algum método especial. A impressão é feita normalmente como qualquer número.
A versão em Java, sem otimizações na invocação da máquina Virtual, demorou 1m15s para executar o fatorial de 80.000.
Esta minha brincadeira feriu os sentimentos de um saudoso aluno que se esforçou para me provar que eu estava enganado. Ele nem quis os décimos pontos na prova como prêmio para quem quebrasse o N, mas apenas me enviou um programa em Java e alguns parâmetros extra-terrestres a serem passados para a máquina Virtual Java a fim de otimizá-la.
Resumo da estória: a solução em Java realmente empatou com a solução em C, considerando a mesma lógica. Quem mandou brincar com um arquiteto certificado pela SUN (e acho que se o Diego Pacheco ler isto, terei problemas, pois sei que ele ainda quer mostrar que o Java é melhor! Grande Diego!).
Não passei a programar em Java depois disto, mas tive que ter mais critérios ao fazer meus comentários em sala de aula.
Basicamente em Java basta usar alguma classe que forneça suporte a números Big. Uma delas é justamente a classe BigDecimal.
Como exemplo, segue um código em java para o cálculo de fatoriais (uma adaptação do código fornecido por Diego Pacheco):
import java.math.BigDecimal;
public class Fatorial {
public static void main(String[] args) {
// Para cada argumento do main
for (String n: args){
// converte string para inteiro
int f = Integer.parseInt(n);
// Inicializa fat com 1. Não se pode apenas atribuir, deve-se
// usar um método para isto, no caso o construtor já tem esta opção
BigDecimal fat = new BigDecimal("1");
for (int j = 2; j <= f; j++) {
// usando o método multiply da classe BigDecimal
fat = fat.multiply(new BigDecimal(j));
}
System.out.println(f + " = " + fat);
}
}
}
public class Fatorial {
public static void main(String[] args) {
// Para cada argumento do main
for (String n: args){
// converte string para inteiro
int f = Integer.parseInt(n);
// Inicializa fat com 1. Não se pode apenas atribuir, deve-se
// usar um método para isto, no caso o construtor já tem esta opção
BigDecimal fat = new BigDecimal("1");
for (int j = 2; j <= f; j++) {
// usando o método multiply da classe BigDecimal
fat = fat.multiply(new BigDecimal(j));
}
System.out.println(f + " = " + fat);
}
}
}
Salve este código com o nome Fatorial.java (mesmo nome da classe), compile usando o javac (isto é, gere os bytes codes) e execute com java Fatorial 200:
javac Fatorial.java
$ java Fatorial 200
200 = 7886578673647905035523632139321850622951359776871732
63294742533244359449963403342920304284011984623904177212138919638
83025764279024263710506192662495282993111346285727076331723739698
89439224456214516642402540332918641312274282948532775242424075739
03240321257405579568660226031904170324062351700858796178922222789
623703897374720000000000000000000000000000000000000000000000000
Como o Java não tem suporte nativo a números grandes, tudo precisa ser feito através de métodos. Isto é, não é possível comparar duas variáveis em um laço apenas com um < ou >. É necessário executar um método próprio para isto, como:
import java.math.BigDecimal;
public class Compara {
public static void main(String[] args) {
BigDecimal zero = new BigDecimal("0");
BigDecimal um = new BigDecimal("1");
BigDecimal grande = new BigDecimal("987654321234567689000000987765");
BigDecimal grande2 = new BigDecimal("987654321234567689000000987765");
int resp;
// Comparando a variável um com a variável zero
resp = um.compareTo(zero);
if (resp == 0){
System.out.println(um + " e " + zero + " SÃO IGUAIS");
}
if (resp > 0){
System.out.println(um + " eh maior que " + zero);
}
if (resp < 0){
System.out.println(um + " eh menor que " + zero);
}
// Comparando a variável um com a variável grande
resp = um.compareTo(grande);
if (resp == 0){
System.out.println(um + " e " + grande + " SÃO IGUAIS");
}
if (resp > 0){
System.out.println(um + " eh maior que " + grande);
}
if (resp < 0){
System.out.println(um + " eh menor que " + grande);
}
// Comparando a variável grande com grande2
resp = grande.compareTo(grande2);
if (resp == 0){
System.out.println(grande + " e " + grande2 + " SÃO IGUAIS");
}
if (resp > 0){
System.out.println(grande + " eh maior que " + grande2);
}
if (resp < 0){
System.out.println(grande + " eh menor que " + grande2);
}
// compareTo tem retorno semelhante ao strcmp do C:
// retorna 0 se iguais
// retorna > 0 se o objeto do método for maior
// retorna < 0 se o objeto do método for menor
}
}
public class Compara {
public static void main(String[] args) {
BigDecimal zero = new BigDecimal("0");
BigDecimal um = new BigDecimal("1");
BigDecimal grande = new BigDecimal("987654321234567689000000987765");
BigDecimal grande2 = new BigDecimal("987654321234567689000000987765");
int resp;
// Comparando a variável um com a variável zero
resp = um.compareTo(zero);
if (resp == 0){
System.out.println(um + " e " + zero + " SÃO IGUAIS");
}
if (resp > 0){
System.out.println(um + " eh maior que " + zero);
}
if (resp < 0){
System.out.println(um + " eh menor que " + zero);
}
// Comparando a variável um com a variável grande
resp = um.compareTo(grande);
if (resp == 0){
System.out.println(um + " e " + grande + " SÃO IGUAIS");
}
if (resp > 0){
System.out.println(um + " eh maior que " + grande);
}
if (resp < 0){
System.out.println(um + " eh menor que " + grande);
}
// Comparando a variável grande com grande2
resp = grande.compareTo(grande2);
if (resp == 0){
System.out.println(grande + " e " + grande2 + " SÃO IGUAIS");
}
if (resp > 0){
System.out.println(grande + " eh maior que " + grande2);
}
if (resp < 0){
System.out.println(grande + " eh menor que " + grande2);
}
// compareTo tem retorno semelhante ao strcmp do C:
// retorna 0 se iguais
// retorna > 0 se o objeto do método for maior
// retorna < 0 se o objeto do método for menor
}
}
Todas as demais operações são métodos, como a de soma, multiplicação e divisão. Somente as linguagens que tem suporte nativo em sua sintaxe, como é o caso do python, permitem usar as operações aritméticas normais. No entanto o Java, assim como o Python, consegue imprimir o valor sem a necessidade de expressar algum método especial. A impressão é feita normalmente como qualquer número.
A versão em Java, sem otimizações na invocação da máquina Virtual, demorou 1m15s para executar o fatorial de 80.000.
Para os iniciantes em C (como eu) isto é de grande ajuda.
Agora finalmente vou conseguir implementar meu código de forma eficiente para tentar vencer seu próximo desafio... :-)
[]s
Cloves Jr