RSS

Arquivo da categoria: math

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
😉

Anúncios
 
4 Comentários

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

 

Tags:

A magia dos Bits

Antes de entender a magia dos bits vamos ver algo leve, claro em
linguagem C , bem como dar uma introdução ao entendimento de bits
e seu funcionamento em variáveis.

Captura de Tela 2014-07-14 às 21.14.21

Uma variável do tipo “int” tem 4bytes ou seja 32bits

se você faz:

 "int var = 3;"

Então temos:

4bytes = 32bits
cada octeto é um byte, meio octeto pode-se chamar de nibble.
“…00000000 00000000 00000011”

cada casa de número binário contamos como um bit
bit nada mais é que mnemônico para “Binary digiT”

Para saber número de bytes de uma variável usamos operador “sizeof(var)”
que nos retorna o valor em bytes da variável.

Se desejamos saber valor binário de um número fazemos divisão por 2
e enquanto o resto da divisão for diferente de “1” fazemos a divisão
no final pegamos os restos ao contrário para ser o resultado final

número 12 para binário logo:

12 | 2
12 +------                   1100 <-- resultado ao contrário
 0  6    | 2              -------------
         +-----
    0      3  | 2
              +-----
          1     1

Resultado 1100,repare que só temos um nibble ou seja um semiocteto
metade de 1 byte ou seja 4bits, lembra 1byte é 8 bits.

façamos então um programa para automatizar a tarefa de converter
decimal para binário

#include <stdio.h>

int main()
{
 int bin[8],num=0,counter=0;

 puts("Dec2Bin\n digite um numero");
 scanf("%d",&num);

//para somente quando a divisão der "1"
 while(num!=1)
 {
//pegamos o resto da divisão ou se tiver um resultado é 1 se não é 0
  bin[counter]=(num%2)?1:0;
//dividimos num por 2 e armazenamos em num para pegar o próximo resto
  num/=2;
  counter++;
 }
 bin[counter]=num;

//mostramos o array ao contrário
 printf("\nResultado: ");
 while(counter!=-1)
 {
  printf("%d",bin[counter]);
  counter--;
 }
 printf("\n");

 return 0;
}

continuando, tem outra forma melhor de se fazer isso, mas não
é hora de abordar isso agora.

Introdução Escovação de Bits “BitWise”
=======================================

Quando dizemos escovação de bits é uma mera referência ao trabalho
de manipular bits para se obter certos resultados. pessoal que trabalha
com microcontrolador seja AVR,PIC por muitas vezes tem que fazer tal
manipulação. Quando queremos desempenho escovação de bits pode nos
ajudar também embora o compilador já otimize muitas das tarefas.Outra
utilização é em tratamento de imagens e manipulação das mesmas,OpenCV
mesmo obriga você usar sempre que não existe uma solução pronta…

Bit Shifting “deslocamento de bit”
======================================

Deslocar um bit nada mais é que mudar o bit da sua posição original
para se chegar num certo resultado,chamamos esta técnica de bit shift
é um mnemônico do assembly “shl,shr”(shifiting left,shifiting right),
vamos a um exemplo de deslocamento para esquerda:

 int var = 3;
 var <<= 1;

 o nosso 3

  0011

 recebeu um deslocamento para esquerda

  0110

resultou em “6”, pode dar uma ilusão de aritmética de produto ou de
adição por ele mesmo, mas foi o resultado do deslocamento, forma
matemática correta segundo o livro do K&R para explanar nossa expressão
do exemplo seria “2*3¹”.

agora vamos ver deslocamento para direita:

 int var = 100;

 temos então 1100100

 var >>= 2; 

 removemos os dois últimos digitos 

  11001

nos resulta “25”,forma matemática para tal é a seguinte “(100/2)²”
você me diz 25mil, cadê os zeros ? como disse remove os dois últimos
dígitos.

Mascaramento de Bit
======================

OR

Vamos ao operador “|” tem o mnemonico “OR” em assembly, vamos entender seu impacto

 x=26|19;

   11010
 | 10011
 ---------
   11011   ==  27

AND

Agora o “&” mnemônico com “AND” em assembly

 x=26&19;

   11010
 & 10011
 ---------
   10010 == 18

NOT

O “~” é mnemônico com “NOT” ou seja ele é uma negação, fazendo um efeito inverso
do seu valor carregado, ou seja onde está 1 fica zero e vice e versa.

 x=~26; 

  11010
   flip
  00101

resultado seria -27, Como mas por que não 5 ? lembra que falei um “int” é
4 bytes equivale a 32bits, então

0000 0000 0001 1010

1111 1111 1110 0101

agora sim,eu fiz em nibble para não precisar escrever muito…

XOR

O “^” é mnemônico para o XOR

 x=26^19;

   11010
 ^ 10011
 ---------
   01001  == 9

veja se a tabela ne ajuda

,---,---,--------,
| a | b |  a ^ b |  pode-se fazer SWAP sem usar uma terceira variável
|---|---|--------|  exemplo:
| 0 | 0 |   0    |
| 0 | 1 |   1    |  int A=4,B=7;
| 1 | 0 |   1    |  A^=B; B^=A; A^=B;
| 1 | 1 |   0    |  // "A" agora vale 7
'---'---'--------'
 alguns usam XOR em criptografia também...

Escovando Bits
================

Vamos usar bitwise para obter “desempenho” vejamos
alguns códigos com bitwise


// programa para verificar se é impar ou par
main(int argc,char *argv[]){printf("%s\x0a",(!((atoi(argv[1]))&1))?"Par":"impar");}
// Isso = "x&1" usa mesma lógica disso "x%2"
// se retornar 0 é por que o último num binário é ZERO ou seja PAR...

// Sempre que precisar verificar se um número é multiplo
// fazer
resto = num & (divisor - 1);
x = 122 % 6;
//forma mais rápida
x = 122 & (6 - 1);

/*
se quiser fazer casting de float para Int
invés de fazer Casting de Float para Int assim "x = int(3.142)",
faça assim "x=3.142>>0;", melhora desempenho em 10%
*/
//operações ternárias são rapidas mas bit a bit são mais</b>
//invés
i = x < 0 ? -x : x;
//faça
i = (x ^ (x >> 31)) - (x >> 31);

//Comparando dois inteiros
x = a * b > 0;
//melhor forma
x = a ^ b >= 0;

//Comparar duas variáveis ver qual é a maior e menor
gamma = y ^ ((x ^ y) & -(x < y)); // gamma=menor(x, y)
gamma = x ^ ((x ^ y) & -(x < y)); // gamma=maior(x, y)

//Determinar se um inteiro é uma potência de 2
x = v && !(v & (v - 1));
//vai retornar verdadeiro ou falso 😉

//média para int
int a=6,b=8; printf("%d\n",((a&b)+(a^b)>>1));

//verificar se a posição "n" em bit é "1"
if( n & 1 << i ) 

lembra do nosso código simples de converter decimal para binário
vamos fazer um usando escovação de bits 🙂

// retirado da header beer.h https://github.com/CoolerVoid/C/edit/master/beer.h
char * dec2bin(int n, char * string)
{
 int i;
 static int size = 8 * sizeof(int);

  for(i = size - 1; i >= 0; i--, n >>= 1)
   string[i] = (01 & n) + '0';

 string[size] = '\0';
 return string;
}

calcular raiz quadrada escovando bit por que não…

// retirado da header beer.h https://github.com/CoolerVoid/C/edit/master/beer.h
int bit_sqrt(int num)
{
//so 32 is sizeof(int)<<3
 int num0=num,result=0,tbit=1<<((sizeof(int)<<3)-2);

 if(num<=0)
 {
  printf("error bit_sqrt(), num = %d ",num);
  return -1;
 }

 while(tbit>num0)
  tbit>>=2;
 while(tbit^0)
 {
  if(num0>=result+tbit)
  {
   num0-=result+tbit;
   result=(result>>1)+tbit;
  }else
   result>>=1;
  tbit>>=2;
 }
 return result;
}

não se compara esta função a de APIs como GMP,OpenSSL
mesmo por que é uma função simples muito menos a “math.h”,
foi mais para ilustrar.

posso usar bitwise em strings ?
se for um ponteiro por que não

// return reverse string
char *strrev(char *str)
{
 char *p1, *p2;

 if(! str || ! *str)
  return str;
 for(p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
 {
  *p1 ^= *p2;
  *p2 ^= *p1;
  *p1 ^= *p2;
 }
 return str;
}

esse assunto é gigante vou ficar por aqui, por final
sugiro que leiam caso queiram se aprofundar no assunto
de bitwise , o livro “hacker’s delight”

hackers delight

2d175-hackers_delight

 
9 Comentários

Publicado por em novembro 24, 2011 em hacking, Linguagem C, math