Programação com números inteiros gigantes

Autor: Elgio Schlemer <elgio.schlemer at gmail.com>

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:

#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 eh %d\n", sizeof(long int));

   printf("Digite um numero 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 iste 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.

Dividir para conquistar

A ULA não suportar informações maiores do que 32 bits (ou 64), não
significa que não se pode ir além disto. Significa apenas que ela
mesmo, a ULA, não consegue lidar com um número maior do que isto de uma
única vez.

Para explicar o conceito, que tal pensarmos em qual o tamanho da nossa ULA?

Você consegue, com a "sua ULA", executar esta operação 059 + 064?

Se você respondeu que SIM, desculpe, mas você errou.

Tipicamente "nossa ULA" é de apenas um decimal. Só conseguimos
lidar com um dígito de cada vez. Quero dizer que desde a primeira série
aprendemos a usar o conceito de dividir para conquistar. É provável que
você, para executar a soma anterior, usou a velha técnica da primeira
série:


  0 5 9
+ 0 6 4   primeira etapa: 9 + 4 = 13
  -----
      3 (e vai um)

    1
  0 5 9
+ 0 6 4   segunda etapa: 5 + 6 + 1(que veio) = 12
  -----
    2 3 (e vai 1)

  1 1
  0 5 9
+ 0 6 4   terceira etapa: 0 + 0 + 1(que veio)
  -----
  1 2 3 (FIM)

Sua ULA é de apenas um dígito! Você precisou decompor as operações complexas em várias menores para conseguir resolver.

O mesmo conceito se aplica para qualquer processador. É
possível, através de programação, fazer uma operação complexa dividindo
ela em operações menores, cada uma suportada pela ULA.

Em um passado distante (2003) eu me aventurei a programar
funções que manipulassem números grandes em C. Eu mesmo defini a
estrutura de dados e as operações. Pode parecer bobagem programar o que
já está programado, mas precisava para entender bem o conceito. Chequei
a implementar o que chamei de BIG_Soma e uma versão péssima de um
BIG_Mul (lenta que doía, pois fazia X*Y somando X nele mesmo Y vezes!).

Na minha modesta e bugada biblioteca, eu defini um número BIG
como um vetor de inteiros. Se quero representar um número de até 128
bits, lá vai um vetor de 4 inteiros (32 * 4 = 128).

O interessante de se usar isto no C é que tudo precisa ser
implementado. Não se pode, por exemplo, imprimir um número grande com
printf! Tenho que eu escrever a minha versão do printf. Como nunca
cheguei a implementar a função BIG_div, também nunca implementei o
BIG_imprime!

Mas deixando esta minha experiência de lado, em diversas
linguagens é possível trabalhar com números de qualquer tamanho.
Algumas de forma incrivelmente fácil, como no caso do python, outras
com um pouco mais de sofrimento, como no caso do C.

Esse Python!

Infelizmente eu não programo em Python, mas se tem uma linguagem que passei a admirar é esta.

Causou-me surpresa enorme ao constatar que o python trabalha
com inteiros de qualquer tamanho de forma natural. Simples, é só usar.
Não precisa declarar nada nem usar funções específicas. Ele pura e
simplesmente já vem com suporte a números inteiros grandes em sua
sintaxe. Maravilha!

Para demonstrar isto, segue uma versão em python de um código que calcula o fatorial de qualquer número:

#!/usr/bin/python
import sys;

for x in sys.argv[1:]:
   fat = 1;
   f = int(x);
   i = 2;

   while i <= f:
      fat = fat * i;
      i = i + 1;

      print "Fatorial de ",f,"eh ",fat;

print "Fim";

Salve este código em seu disco, dê permissão de execução e
pronto, você já pode calcular o fatorial de 6000 do enunciado (se você
não programa em python, tome muito cuidado com as indentações. São
importantes pois são elas que definem o que está dentro ou fora do
laço).

Como não teria sentido encher este capítulo de números, segue um exemplo do cálculo do fatorial de 200:

$ ./fatorial.py 200
Fatorial de 200 eh 78865786736479050355236321393218506229513597768717
326329474253324435944996340334292030428401198462390417721213891963883
025764279024263710506192662495282993111346285727076331723739698894392
244562145166424025403329186413122742829485327752424240757390324032125
740557956866022603190417032406235170085879617892222278962370389737472
0000000000000000000000000000000000000000000000000
$

O Python foi capaz de calcular o fatorial de 80.000 em 50s
usando um processador de 2.4Ghz, sendo que a resposta deste fatorial
gera um número com 357.507 dígitos! Esta aí uma linguagem que eu
respeito!

Das linguagens que pesquisei, Python é a única que tem suporte
a inteiros gigantes nativo. Veja, das que eu pesquisei. Existem muitas
e inúmeras linguagens, mas no Java e no C este suporte não é nativo.

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):

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);
     }
  }
}

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
  }
}

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.

Comigo é no C Ansi

Assim como o Java, o C não possui suporte a números gigantes em
sua sintaxe. Se fosse C++ a solução seria semelhante ao Java, ou seja,
através do uso de alguma classe que manipule estes inteiros. Mas no C
Ansi tudo é função e uma biblioteca precisa ser usada para isto.

Uma das mais fantásticas bibliotecas que conheço é a OpenSSL.
Ela tem tudo o que diz respeito a criptografia. Se alguém precisa
adicionar qualquer tipo de cifra em seus programas, não precisa sair
programando, basta usar a biblioteca OpenSSL que já estão prontas para
uso todas as funções necessárias.

Como muitos algoritmos de criptografia necessitam manipular
inteiros além da capacidade da ULA, a biblioteca OpenSSL implementou
suporte a números gigantes internamente. Usar apenas a parte de números
big pode ser feito inserindo-se a biblioteca bn.h do OpenSSL.

Assim como no Java, que também não tem suporte a estes números
em sua sintaxe, toda a manipulação destes números deve ser feita
usando-se funções apropriadas, como no exemplo comentado do código que
calcula o fatorial.

#include <stdio.h>
#include <openssl/bn.h>

int main(int argc, char *argv[])
{
   BIGNUM *fat; // declaração de uma variável Big
   BN_ULONG a, f; // apenas um long int normal
   char *resp;
   int i;

   /* Primeiro tem que alocar as variáveis BIGNUM */
   fat = BN_new();

   for (i = 1; i < argc; i++) {
      printf("Calculando fatorial de %s\n", argv[i]);

      /* convertendo string em long int */
      f = atoll(argv[i]);

      /* forma de atribuir 1 a uma variável BIGNUM */
      BN_dec2bn(&fat, "1");

      for (a = 2; a <= f; a++) {
         BN_mul_word(fat, a);
      }

      /* gerando uma string imprimível do resultado */
      resp = BN_bn2dec(fat);

      /* impressão do resultado (agora é uma string) */
      printf("Fatorial de %s = %s\n", argv[i], resp);
   }
}

Para poder compilar o programa em C anterior é necessário ter
instalado as bibliotecas OpenSSL para desenvolvimento. No caso do
Ubuntu deve-se instalar o pacote ssl-devel (e, evidentemente, ter
instalado todos os pacotes de desenvolvimento básico pois o Ubuntu vem
até sem gcc!). Na compilação é necessário ligar com a lib ssl:

$ gcc fatorialBIG.c -lssl -o fatorialBIG

Esta biblioteca, assim como o Java, possui funções para
realizar as operações, seja de comparação, atribuições, conversão de e
para string. Particularmente as operações aritméticas são extremamente
completas para dar suporte aos algoritmos de criptografia. Só não
encontrei a implementação do cálculo da raiz quadrada.

Na versão do código em C, usando a biblioteca bn.h, um fatorial de 80.000 levou 18 segundos para executar.

Conclusão

Eu até tentei, no passado, construir a minha biblioteca, mas foi
um fracasso. O meu BIG_Add eu até implementei com eficiência, mas o
BIG_mul era um terror. Nunca nem tentei implementar a divisão, módulo e
tudo o mais.

O fato é que já existem bibliotecas muito boas e completas
para C, bem como classes para as linguagens visuais. OpenSSL não é uma
biblioteca para números grandes. É uma biblioteca para fornecer
algoritmos de criptografia para os desenvolvedores. Porém, como muitos
algoritmos exigem cálculos com números além da capacidade da ULA, uma
coleção de funções eficientes que manipulam tais números foi também
criada.

Não foi minha intenção, em nenhum momento, a de realizar algum
comparativo de desempenho entre as linguagens que citei, até porque
cada especialista em determinada linguagem pode ter artifícios para
otimizar o código. No entanto, só para ter uma pequena comparação,
realizei alguns testes com as três linguagens, python, java e C.

Nestes meus testes observei que um tempo considerável é gasto
na impressão do resultado, já que o mesmo, em alguns casos, possui
centenas de milhares de dígitos. Assim, nas três linguagens, eu
realizei os seguintes testes:

  • com impressão da resposta, ou seja, o programa imprime o fatorial na tela;
  • sem a impressão da resposta, isto é, o programa apenas calcula e nada imprime.

A medição do tempo também poderia ser realizada dentro do
programa, pegando o tempo antes e depois do laço que calcula o
fatorial, mas como isto exigiria mais linhas de código, optou-se em
usar o time do Linux
para medir quanto tempo o programa levou para iniciar e terminar. Para
cada linguagem se mediu o tempo para calcular os fatoriais de 2.500,
5.000, 10.000, 20.000, 40.000 e 80.000. A Tabela a seguir resume os
resultados obtidos.

Linux: Programação com números inteiros gigantes

Não
considere esta tabela como uma avaliação precisa e científica, pois é
apenas uma ideia. Principalmente os fatoriais menores resultaram em
valores tão pequenos que pode-se considerar como sendo zero. Uma
avaliação mais precisa deveria levar em consideração processos em
execução no momento da avaliação e a obtenção de vários valores,
permanecendo com o melhor deles. Contudo ela serviu para mostrar que
neste cálculo de fatorial, uma vez que a resposta é um número muito
grande, o maior tempo foi gasto na conversão ou preparação dos dados e
sua posterior impressão na tela.


http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes

4 comentários sobre “Programação com números inteiros gigantes

  1. BOA NOITE, GOSTEI MUITO DO SEU POSTE, BOM É O SEGUINTE NÃO INTENDO MUITO DE PROGRAMAÇÃO, POREM EU GOSTARIA DE VER UM PROGRAMA DESSES QUE VOCÊ CITOU NO ARTIGO, QUE CAUCULA MUITO NUMEROS, EU SEMPRE TIVE CURIOSIDADES DE DESCOBRIR QUANTAS CASAS TEM EM MINHA CIDADE POR EXEMPLO, QUE NO CASO É SAO PAULO… BOM GOSTARIA DE SABER SE VC NÃO TEM COMO ME ENVIAR ESSE PROGRAMA AI PARA EU CALULCAR ALGUMAS COISAS QUE DESEJO, DESDE JA AGRADEÇO,,, ATT. GILDO MENEZES

  2. Gostaria que me ajudasse. Criei um programa que precisa calcular numeros grandes. Mas isto não ocorre porque é um linguagem de programação que não possui suporte para numeros inteiros grandes. Enfim, preciso de reprogramar em uma linguagem que me permita obter números com mais de 10 milhões de casas. O que me recomenda? Desde já, obrigado!

  3. Pingback: Dynamic Fibonacci: Além da recursividade – diogommartins

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s