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á!
Introdução
Números "gigantes" usado no título é uma tradução de big numbers, do inglês. Usa-se a palavra gigante para deixar claro que é gigante mesmo, muito além do que qualquer variável unsigned long long possa armazenar. Tipicamente números de qualquer tamanho, limitado apenas a sua memória e a sua paciência.
Quando se fala em números, deve-se remeter para o tamanho da palavra que a ULA suporta (Unidade Lógica e Aritmética). Estamos gradativamente abandonando a plataforma de 32 bits, o que significa que os processadores desta plataforma conseguem lidar com números de até 32 bits!
Assim, em 32 bits, o maior inteiro que o processador consegue lidar é 4.294.967.295 e isto apenas se for considerado números inteiros positivos, sem sinal. Como os processadores utilizam a representação complemento de dois para números inteiros, ao permitir que se use sinal a faixa de representação de um inteiro em 32 bits vai de -2.147.483.648 até +2.147.483.647 (com complemento de dois ganha-se uma representação a mais no lado negativo).
Tipicamente um compilador C faz uma variável do tipo long int acompanhar o tamanho da ULA. Assim, o pequeno código em C a seguir poderia trabalhar com números inteiros de 32 bits:
O mais interessante é que em uma arquitetura de 32 bits, apenas o fatorial de 12 pode ser calculado. Se for tentar calcular o fatorial de 13, este daria 6.227.020.800, número que não pode ser representado em 32 bits. Agora se você possui um processador de 64 bits, um sistema operacional de 64 bits e compilar o código em C o usando um gcc para 64 bits, você é um felizardo pois o programa conseguirá calcular o incrível fatorial de 22, pois fatorial de 23 resulta em 25.852.016.738.884.976.640.000 e este valor não cabe em 64 bits. Isto, ainda, considerando o uso dos inteiros sem sinal.
Não pense que você resolve o problema trocando a variável para double. É um erro muito comum pensar que double é apenas um inteiro maior! As respostas até podem bater até certo ponto, mas depois, devido a perda de precisão, os valores estarão errados (Cuidado com números em Ponto Flutuante).
No entanto já existem diversas soluções em várias linguagens que permitem manipular números inteiros de qualquer tamanho. Será descrito aqui o caso do python, Java e o C.
Mas antes um pouco de teoria que não faz mal a ninguém.
Quando se fala em números, deve-se remeter para o tamanho da palavra que a ULA suporta (Unidade Lógica e Aritmética). Estamos gradativamente abandonando a plataforma de 32 bits, o que significa que os processadores desta plataforma conseguem lidar com números de até 32 bits!
Assim, em 32 bits, o maior inteiro que o processador consegue lidar é 4.294.967.295 e isto apenas se for considerado números inteiros positivos, sem sinal. Como os processadores utilizam a representação complemento de dois para números inteiros, ao permitir que se use sinal a faixa de representação de um inteiro em 32 bits vai de -2.147.483.648 até +2.147.483.647 (com complemento de dois ganha-se uma representação a mais no lado negativo).
Tipicamente um compilador C faz uma variável do tipo long int acompanhar o tamanho da ULA. Assim, o pequeno código em C a seguir poderia trabalhar com números inteiros de 32 bits:
#include <stdio.h>
unsigned long int fat (int x)
{
unsigned long int f=1;
int i;
if (x<0){
fprintf(stderr, "Erro. Fatorial de negativo não existe!\n");
return(0);
}
for (i = 2; i <= x; i++)
f = f*i;
/* se x for 0 ou 1, não entrara no laço, retornando 1. Certo, pois fat(0) = 1 e fat(1) = 1 */
return(f);
}
int main()
{
int x;
printf("Tamanho da minha ULA é %d\n", sizeof(long int));
printf("Digite um número positivo: ");
scanf("%d", &x);
printf("Fatorial de %d = %lu\n", x, fat(x));
}
unsigned long int fat (int x)
{
unsigned long int f=1;
int i;
if (x<0){
fprintf(stderr, "Erro. Fatorial de negativo não existe!\n");
return(0);
}
for (i = 2; i <= x; i++)
f = f*i;
/* se x for 0 ou 1, não entrara no laço, retornando 1. Certo, pois fat(0) = 1 e fat(1) = 1 */
return(f);
}
int main()
{
int x;
printf("Tamanho da minha ULA é %d\n", sizeof(long int));
printf("Digite um número positivo: ");
scanf("%d", &x);
printf("Fatorial de %d = %lu\n", x, fat(x));
}
O mais interessante é que em uma arquitetura de 32 bits, apenas o fatorial de 12 pode ser calculado. Se for tentar calcular o fatorial de 13, este daria 6.227.020.800, número que não pode ser representado em 32 bits. Agora se você possui um processador de 64 bits, um sistema operacional de 64 bits e compilar o código em C o usando um gcc para 64 bits, você é um felizardo pois o programa conseguirá calcular o incrível fatorial de 22, pois fatorial de 23 resulta em 25.852.016.738.884.976.640.000 e este valor não cabe em 64 bits. Isto, ainda, considerando o uso dos inteiros sem sinal.
Não pense que você resolve o problema trocando a variável para double. É um erro muito comum pensar que double é apenas um inteiro maior! As respostas até podem bater até certo ponto, mas depois, devido a perda de precisão, os valores estarão errados (Cuidado com números em Ponto Flutuante).
No entanto já existem diversas soluções em várias linguagens que permitem manipular números inteiros de qualquer tamanho. Será descrito aqui o caso do python, Java e o C.
Mas antes um pouco de teoria que não faz mal a ninguém.
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