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 2: Dividir para conquistar
A ULA não suportar informações maiores do que 32 bits (ou 64), não significa que não se pode ir além disto. Significa apenas que ela mesmo, a ULA, não consegue lidar com um número maior do que isto de uma única vez.
Para explicar o conceito, que tal pensarmos em qual o tamanho da nossa ULA?
Você consegue, com a "sua ULA", executar esta operação 059 + 064?
Se você respondeu que SIM, desculpe, mas você errou.
Tipicamente "nossa ULA" é de apenas um decimal. Só conseguimos lidar com um dígito de cada vez. Quero dizer que desde a primeira série aprendemos a usar o conceito de dividir para conquistar. É provável que você, para executar a soma anterior, usou a velha técnica da primeira série:
Sua ULA é de apenas um dígito! Você precisou decompor as operações complexas em várias menores para conseguir resolver.
O mesmo conceito se aplica para qualquer processador. É possível, através de programação, fazer uma operação complexa dividindo ela em operações menores, cada uma suportada pela ULA.
Em um passado distante (2003) eu me aventurei a programar funções que manipulassem números grandes em C. Eu mesmo defini a estrutura de dados e as operações. Pode parecer bobagem programar o que já está programado, mas precisava para entender bem o conceito. Cheguei a implementar o que chamei de BIG_Soma e uma versão péssima de um BIG_Mul (lenta que doía, pois fazia X*Y somando X nele mesmo Y vezes!).
Na minha modesta e bugada biblioteca, eu defini um número BIG como um vetor de inteiros. Se quero representar um número de até 128 bits, lá vai um vetor de 4 inteiros (32 * 4 = 128).
O interessante de se usar isto no C é que tudo precisa ser implementado. Não se pode, por exemplo, imprimir um número grande com printf! Tenho que eu escrever a minha versão do printf. Como nunca cheguei a implementar a função BIG_div, também nunca implementei o BIG_imprime!
Mas deixando esta minha experiência de lado, em diversas linguagens é possível trabalhar com números de qualquer tamanho. Algumas de forma incrivelmente fácil, como no caso do python, outras com um pouco mais de sofrimento, como no caso do C.
Para explicar o conceito, que tal pensarmos em qual o tamanho da nossa ULA?
Você consegue, com a "sua ULA", executar esta operação 059 + 064?
Se você respondeu que SIM, desculpe, mas você errou.
Tipicamente "nossa ULA" é de apenas um decimal. Só conseguimos lidar com um dígito de cada vez. Quero dizer que desde a primeira série aprendemos a usar o conceito de dividir para conquistar. É provável que você, para executar a soma anterior, usou a velha técnica da primeira série:
0 5 9
+ 0 6 4 primeira etapa: 9 + 4 = 13
-----
3 (e vai um)
1
0 5 9
+ 0 6 4 segunda etapa: 5 + 6 + 1(que veio) = 12
-----
2 3 (e vai 1)
1 1
0 5 9
+ 0 6 4 terceira etapa: 0 + 0 + 1(que veio)
-----
1 2 3 (FIM)
+ 0 6 4 primeira etapa: 9 + 4 = 13
-----
3 (e vai um)
1
0 5 9
+ 0 6 4 segunda etapa: 5 + 6 + 1(que veio) = 12
-----
2 3 (e vai 1)
1 1
0 5 9
+ 0 6 4 terceira etapa: 0 + 0 + 1(que veio)
-----
1 2 3 (FIM)
Sua ULA é de apenas um dígito! Você precisou decompor as operações complexas em várias menores para conseguir resolver.
O mesmo conceito se aplica para qualquer processador. É possível, através de programação, fazer uma operação complexa dividindo ela em operações menores, cada uma suportada pela ULA.
Em um passado distante (2003) eu me aventurei a programar funções que manipulassem números grandes em C. Eu mesmo defini a estrutura de dados e as operações. Pode parecer bobagem programar o que já está programado, mas precisava para entender bem o conceito. Cheguei a implementar o que chamei de BIG_Soma e uma versão péssima de um BIG_Mul (lenta que doía, pois fazia X*Y somando X nele mesmo Y vezes!).
Na minha modesta e bugada biblioteca, eu defini um número BIG como um vetor de inteiros. Se quero representar um número de até 128 bits, lá vai um vetor de 4 inteiros (32 * 4 = 128).
O interessante de se usar isto no C é que tudo precisa ser implementado. Não se pode, por exemplo, imprimir um número grande com printf! Tenho que eu escrever a minha versão do printf. Como nunca cheguei a implementar a função BIG_div, também nunca implementei o BIG_imprime!
Mas deixando esta minha experiência de lado, em diversas linguagens é possível trabalhar com números de qualquer tamanho. Algumas de forma incrivelmente fácil, como no caso do python, outras com um pouco mais de sofrimento, como no caso do C.
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