RSS

Arquivo mensal: janeiro 2012

Trabalhando com BigInt

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
😉

 
4 Comentários

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

 

Tags:

Migrando do excel para algum DB

Vou ser bem retórico, missão aqui é abrir vários arquivos
.xls“(extensão de arquivos do excel) que contenham a mesma
tabela,passar para XML e depois dar parser para dar “INSERT
em algum DB.

Justificativa da missão ,ano passado por 3 vezes eu
peguei freelancer de portar tabelas de “excel” para
algum SGBD, muita gente reclamando para mim que
gostaria de saber como o fazer e tudo mais foi outro
motivo, muitos clientes por falta de tempo e de estudo
preferem usar “excel” do que DB,pessoal de contabilidade
principalmente ,só olham para possibilidade de usar
banco de dados quando se tem milhares de tabelas do excel
para se alterar etc
, Isso é o que mantêm os estagiários em
algumas empresas,mas se perde muito tempo e dinheiro com
isso…
Read the rest of this entry »

 
Deixe um comentário

Publicado por em janeiro 6, 2012 em Banco de dados, Linguagem C, Perl