Aritmética de múltipla precisão, em C

Meu amigo e coautor desse blog, o MaRZ, de brincadeira aceitou a minha provocação sobre a linguagem que tem um “Monte de parenteses idiotas e estúpidos” (LISP, Lots of Idiot and Stupid Parentesis) e me mandou esse exemplo:

Falando em lerdeza...

Tente calcular com o seu "C", a potência de 4242 elevado à 4242!
Aqui deu:

$ time clisp <<eof
> (expt 4242 4242)
> eof

Isso ai mostra um numerozão com 15390 algarismos de tamanho. Well…. Challenge Accepted, my friend!

/*
  Este é o mesmo programa, só que em C. Compile com:

  $ cc -O2 -o power power.c -lgmp
*/
#include <stdio.h>
#include <gmp.h>

int main(int argc, char *argv[])
{
  mpz_t r, s;

  mpz_init(r);
  mpz_init(s);

  mpz_set_ui(s, 4242);    /* s = 4242; */
  mpz_pow_ui(r, s, 4242); /* r = pow(s, 4242); */
  mpz_clear(s);           /* não precisamos mais do 's' */
  gmp_printf("%Zd\n", r);
  mpz_clear(r);           /* não precisamos mais do 'r' */

  return 0;
}

Tá bom… é mais “complexo”, mas nem tanto, né?

Não vou colocar o resultado aqui porque vai dar muito trabalho para formatá-lo para caber todo na página.

O que vale a pena notar é que a libgmp (GNU Multiple Precision Library) — instale os pacotes libgmp-dev e libgmp10.doc — implementa a chamada aritmética de múltipla precisão, onde os valores não estão restritos ao tamanho de registradores, mas sim ao tamanho da memória RAM ou do disco. O exemplo acima mostra como usar inteiros sem sinal, mas existem outros “tipos” que lidam com números racionais e ponto flutuante com a “mantissa” ilimitada (porém com limitação no expoente).

Se você tentar calcular pow(4242, 4242), usando long double (a maior precisão possível em ponto flutuante) vai tomar um overflow na cara (provavelmente um valor +\infty), já que o maior inteiro, numa arquitetura 64 bits, é 2^{64}-1 e, usando ponto flutuante, com long double, você consegue valores até o limite superior, aproximado, de 1.18\cdot10^{4932}. O tipo mpz_t é, na verdade, uma estrutura que contém membros alocados dinamicamente (via malloc, por exemplo). Assim, a quantidade de bits para conter o valor cresce à medida que o valor cresce. O processo é lento (em relação a aritmética inteira e em ponto flutuante tradicional), mas não tanto quanto você possa imaginar… Calcular “π”, com 1 bilhão de casas decimais usando o método de Chudnovsky, por exemplo, leva cerca de 1 hora, de acordo com a sua máquina (veja aqui).

Note que, para lidar com “ponto flutuante” de múltipla precisão você terá que usar o tipo mpf_t e as funções que lidam com esse tipo…

É claro que você só vai precisar dessa precisão “infinita” se trabalhar na NASA… mas a dica está ai… ;)

Anúncios

3 comentários sobre “Aritmética de múltipla precisão, em C

  1. Sobre a questão de “jogar” os dados na memória, célula por célula (ou como se diz atom por atom) é a língua franca do Lisp. Não serve somente para quem trabalha na Nasa, mas também para aqueles que queiram, por exemplo usar uma lista ligada, árvore binária, etc Coisas que acabamos tendo que usar stls ou libs externas, pois dão um certo trabalho para montar e depurar, usando algo do tipo “ponteiro”…. Para que referenciar memória e o seu dado for a própria memória?

    Eu vi, no ano passado quando comecei a me tocar destas coisa, que os exemplos tipo call back functions, grafos, listas, recursividade são muito bons, porém deixamos de usá-los com a merecida frequência, pois criam complexidades na depuração, estouros de pilhas, etc. No Lisp estas estruturas são básicas e fluem naturalmente (lembrando que uma lista é uma árvore degenerada e ambas fazem parte do conjunto maior: os grafos)

    Outras coisas também se encaixam, transformações, ordenações, buscas, tomadas de decisão por caminhos mais curtos… Os programas fazem isto o tempo todo (quando o programador percebe o modelo) do contrário… Chuva de ifs e código spaghetti, desestruturado, torto…. Fruto óbvio da deficiência mental do programador (lembrando que mente é dferente de cérebro e que deficiência mental é falha na estrutura da mente e deficiência neurológica é falha no tecido cerebral) Em miúdos, não estou chamando ninguém de doido, mas quem não possui, assim como eu mesmo, falhas mentais, mesmo que pequenas, ao visualizar os problemas?

    1. Lembrete meu: Todo esse lance de linguagem com “muitos parenteses idiotas e estúpidos” e provocações são bem humoradas… Pessoalmente não gosto de LISP desde que eu comecei a aprendê-lo, nos anos 90, com o Auto-Lisp (do Autocad)…

      Quanto ao consumo de memória: O que eu quis dizer é, que se for usar aritmética de múltipla precisão, o consumo aumenta muito. Ao invés de usar 4 ou 8 bytes para armazenamento de um único valor numérico (porém limitado), o exemplo usa mais que 15 kB para um único valor resultante. Dá pra ter uma ideia do consumo se o cálculo for mair elaborado… Por exemplo, um aviso no benchmarking do calculo de PI que citei diz que para calcular a constante com 1 trilão de casas decimais é necessário um HD de alta-performance (e, pelo menos, 4 TB de espaço livre), sem contar com o suporte do SO.

      LISP é bonitinho… é legalzinho… é atraente até, mas do ponto de vista da performance e do uso de recurso, no meu entender, é um monstrengo…

      Não entendi o que seria “fruto óbvio de deficiência mental do programador”, mesmo com a explicação o uso do termo ficou meio, digamos, pesado… ignorância, no sentido literal, acho, seria mais apropriado… Mas, deixando isso de lado, vc sabe, tanto quanto eu, que C++ implementa a STL, que contém muitos algorítmos reusáveis… o que deixa o código “bloated” (termo que vc mesmo gosta de usar).

      De novo, pessoalmente, eu não gosto dessas linguagens que tiram o poder do programador (com garbage collectors e passes de mágica). Que bom que o Stallman gosta… Já experimentei um monte delas (Mumps, PL/1, Forth, Prolog, Lisp) – claro que apenas como curiosidade – E achei apenas três linguagens que valem realmente a pena o investimento: C, Pascal e Assembly… Pascal caiu em desuso…

Deixe um comentário

Faça o login usando um destes métodos para comentar:

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