Programação com números inteiros gigantes
Quanto é o fatorial de 5? 120, fácil, não? E quanto é o fatorial de 6000? É um número com 20 mil dígitos. És capaz de escrever um programa que calcule isto? Depois de ler este artigo, você será!
Parte 5: 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.
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.
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);
}
}
#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.
Para os iniciantes em C (como eu) isto é de grande ajuda.
Agora finalmente vou conseguir implementar meu código de forma eficiente para tentar vencer seu próximo desafio... :-)
[]s
Cloves Jr