RSS

Trabalhando com BigInt

13 jan

Aloha queridos leitores, firmes como geleia ?! , hoje vou
tentar explanar algo comum, pode ser útil para quem trabalha com
estatística,física,aritmética pesada em geral ou desafios
Eulerianos” aqueles problemas com sigma com valores
com fatoriais monstros,acumulativos e recursivos,onde seu
computador pediria água de tanto serviço.

Quando você tem um número muito grande que ultrapassa a cota de uma
variável “int“, variável muda a casaca para negativo,não tem para
onde mais correr, e agora ? uso “long” certo e se o long virar casaca
também , e se o “long long” não der e nem com “unsigned“, Ho Ho parece
um dragão daqueles de múltiplas cabeças bem como Tiamat do D&D,
tiamat😀
bom obviamente você chegou a epifania de usar “char *“,usar alocação
dinâmica e já veio uma utopia na cabeça,uma possível solução para
nosso paradoxo, então você já sabe o que é um “BigInt“.

#include <stdio.h>

int main()
{
//tente concatenar mais alguns algarismos em X e compile e analise os resultados
 unsigned long long X=1844674407370955161;
 fprintf(stdout,"%lld",X);
 return 0;
}

Não vale o fardo seguir com a insanidade de como fazer do zero,
ainda mais mundo moderno onde muitos problemas já foram solucionados,
olhando em volta tocando uns livros e batendo uma busca no
Google a 2 anos atrás, encontrei o GMPGNU Multiple Precision
Arithmetic Library
“, uma API bem madura que proporciona o trabalho
com uma gamma de funções aritméticas, seja com variáveis integer,float
ou número racional, também conheci a lib para BigInt do OpenSSL mas
achei tão lenta que resolvi não escrever sobre. Quanto a otimização ?
GMP tem várias otimizações em ASM de acordo com a arquitetura do seu
computador, código fonte do GMP assusta até o Chuck Norris

Instalando:
# apt-get install libgmp-dev gmp-doc

Lendo o manual:
$ info gmp

agora que temos material em mãos

bom para usar a lib gmp usamos “gmp.h” e na hora de compilar usamos
o argumento “-lgmp“,vou explanar em algo empírico.

// exemplo by Cooler_
#include <stdio.h>
#include <gmp.h>

int main()
{
// var do gmp para trabalhar com signed int
 mpz_t X;
 unsigned int Y=512;
// inciando
 mpz_init(X);
// mnemônico para atribuição x=y
 mpz_set_ui(X,Y);
// mnemônico para soma x+=y
 mpz_add_ui(X,X,Y);
// 1024^512 qual seria o resultado ?
 mpz_pow_ui (X,X,Y);

 gmp_fprintf(stdout,"%Zd  %s\n",X,"legal");
/*
gmp tem um próprio método de OUTPUT
explicando o format string

     F         mpf_t, float conversions
     Q         mpq_t, integer conversions
     M         mp_limb_t, integer conversions
     N         mp_limb_t array, integer conversions
     Z         mpz_t, integer conversion

para INPUT use o gmp_scanf() e gmp_sscanf()
*/


/*
expoente
mpz_pow (mpz_t ROP, mpz_t BASE, mpz_t EXP)

resto
mpz_mod (mpz_t R, mpz_t N, mpz_t D)

testa se é divisível
int mpz_divisible_p (mpz_t N, mpz_t D)

adição
void mpz_add (mpz_t ROP, mpz_t OP1, mpz_t OP2)

subtração
void mpz_sub (mpz_t ROP, mpz_t OP1, mpz_t OP2)

produto
void mpz_mul (mpz_t ROP, mpz_t OP1, mpz_t OP2)

divisão
void mpz_div (mpz_t ROP, mpz_t OP1, mpz_t OP2)

raiz quadrada
void mpz_sqrt (mpz_t ROP, mpz_t OP)

comparar dois números
int mpz_cmp (mpz_t OP1, mpz_t OP2)
...

OBS: usamos "_ui" com nome da função quando precisamos usar "unsigned int"

*/


// limpando a bagunça
 mpz_clear(X);

 return 0;
}

Agora você pode ficar orgulhoso de conseguir fazer contas que uma calculadora
de mão não conseguiria fazer, evidente que todo conhecimento abre portas…

vamos a um desafio do project euler,algo bem easy
http://projecteuler.net/problem=48

vendo enunciado:
sequência , 1^1 + 2^2 + 3^3 + … 10^10 = 10405071317.
quanto seria até 1000^1000 ops apenas os últimos 10 dígitos

parece ser simples vamos fazer até 10 e pegar os últimos 5 dígitos

#include <stdio.h>
#include <math.h>
//coded by Cooler_
int main()
{
 unsigned long long sum=0;
// agora troque o count por 1000, e o digitos para 10
 short count=10,digitos=5;

 while(count)
 {
  sum+=pow(count,count);
  count--;
 }

 fprintf(stdout,"%lld ,last %d digits is %d\n",sum,digitos,(int)fmod(sum,pow(10,digitos)) );
 return 0;
}

compile e rode o programa e depois modifique como no comentário,
pensou em usar GMP ? e se você fazer de 10000000 ao invés de 1000 ?
como você faria ?

Meus agradecimentos ao utroz,enygmata e o kov do canal ##c-br da freenode
😉

Anúncios
 
4 Comentários

Publicado por em janeiro 13, 2012 em Linguagem C, math

 

Tags:

4 Respostas para “Trabalhando com BigInt

  1. m0nad

    janeiro 14, 2012 at 5:15 am

    Boa, muito bom!

     
  2. Fernando Mercês

    janeiro 14, 2012 at 3:27 pm

    Parabéns, cara! Vivendo e aprendendo. 🙂

     
  3. cooler51

    janeiro 14, 2012 at 8:41 pm

    valeu brothers

     
  4. clandestine

    janeiro 15, 2012 at 11:42 am

    meu orgulho esse menino )))

     

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

 
%d blogueiros gostam disto: