Armadilhas Numéricas – Inteiros – Parte II

Este é o segundo artigo de uma série de artigos sobre a representação de números nas plataformas de programação modernas como C# e  Java, os problemas práticos derivados dessas representação, erros comuns dos programadores e formas OO de resolver e lidar com as limitações.

Vimos no artigo anterior como é feita a representação de números inteiros em forma binária e que problemas isso levanta. Veremos neste artigo algumas formas de driblar as limitações do modelo binário.

O principal problema da representação binária é que estamos presos a um tipo especifico da plataforma que apenas comporta um tamanho pré-determinado de bits. Atualmente este número está em 64. Esta limitação nos impede de representar números maiores.  Em criptografia , as chaves criptográficas são números inteiros e a capacidade de computação necessária para quebrar a chave por força bruta é proporcional ao número de bit usados para representar o número. Portanto, uma chave como 64 bits é mais difícil de quebrar que uma de 32, por exemplo. Com os avanços em hardware a velocidade de computação aumentou muito e chaves com poucos bits são facilmente quebráveis. Hoje se usam chaves de 1024 , 2048 ou mais bits.  Como representar e calcular esses números em computadores que só entendem séries de 64 bits ?

Resolver este problema não é trivial em hardware pois a cada novo limite de bits novas arquiteturas e processadores seriam necessários e, embora eles existam, não é um modelo prático ficar comprando hardware novo a cada par de meses. A resposta está na Orientação a Objetos. Se criarmos um objeto que se comporta como um inteiro de um número maior de bits, temos nosso problema resolvido.  Em Java isto é resolvido pela classe BigInteger. Em C# pela estrutura BigInteger. As diferenças são subtis entre as plataformas. Em C# BigInteger é um tipo primário ( fica alocado na pilha) enquanto em Java é um objeto (fica alocado no heap). A primeira implementação de BigInteger em java utilizava a JNI para obter melhor performance. Com os avanços na VM isto não é mais necessário hoje.

O que é um BigInteger ?

Nas máquinas atuais temos um limite de 64 bits, para representar números maiores, precisamos de mais bits. Ou precisamos pensar diferente.

Todas as linguagens comportam o conceito de array. Um arranjo de valores em que cada um pode ser acessado pela posição. No primeiro artigo desta série vimos que um número pode ser representado como a decomposição em potências de dez.

cento e cinco = 1 x 1020 x 1015 x 100 105

Então, em vez de usarmos uma representação binária, podemos ter um array de inteiros onde cada posição corresponde a uma potência de dez e o valor nessa posição corresponde ao fator (de 0 a 9). Com esta representação estamos apenas limitados pelo número máximo de posições no array ( Em C# este valor é limitado pelo  maior número inteiro da plataforma, e pela memória até um limite de 2GB de espaço ocupado pelo array e os valores nele contidos).  Mesmo com as limitações na posição do array é possível representar uma quantidade enorme de valores. Isto porque estamos usando base 10 e fatores de 0 a 9. Mas em um inteiro cabe muito mais que isso. Podemos inclusive usar uma potência de int.MaxValue com fatores de zero a int.MaxValue - 1.

A representação interna do BigInteger cabe ao seu implementador, várias configurações são possíveis, mas o que interessa entender é que se trada do uso de um array para representar os fatores da decomposição do número inteiro numa certa base. Neste sentido um BigInteger é muito semelhante a uma String. O String contém e controla um array de char, o BigInteger contém e controla um array de inteiros.

BigInteger é um exemplo de implementação do padrão Value Object em que um objeto (ou um struct no caso do C#) é usado para representar um valor.  O uso de capacidades da Orientação a Objetos como o encapsulamento, permitem implementar operações complexas de arrays como se estivéssemos apenas usando um número inteiro muito grande.

Cálculos com BigInteger

Na plataforma .NET o calculo com BigInteger é transparente pois todos os operadores básicos de inteiros são implementados. Em java dá um pouco mais de trabalho porque há que usar métodos específicos para cada operação.

Internamente acontecem cálculos entre os inteiros do array. Estas operações não são baratas computacionalmente falando. Portanto algoritmos especiais são necessários para quebrar a complexidade computacional. A multiplicação é especialmente complexa porque envolver uma serie de multiplicações e somas dígito a dígito . Para este caso o algoritmo de Karatsuba é normalmente usado.

Embora tecnicamente a representação de BigInteger seja limitada, como vimos, na prática ela não é. É possível fazer quaisquer operações entre inteiros positivos e negativos sem medo de erros de overflow. Se for usada uma base 10, o maior número teria 2147483647 dígitos que são suficientes para qualquer aplicação normal. Na prática a base é normalmente int.MaxValue o que permite ainda mais dígitos.  Por outro lado, o interessante de BigInteger é poder ter um conjunto de bits de tamanho arbitrariamente grande (limitado apenas pela memória). Por isso, na plataforma Java , BigInteger implementa também todas as operações binárias que são possíveis sobre inteiros como left e right shift além de contagem de bits e operações lógicas como and, or e xor.

Números Primos

A necessidade de ter um objeto BigInteger é, como vimos, poder criar operações para criptografia. A criptografia depende fortemente da teoria de números especialmente no conceito de números primos, números aleatórios e como vimos antes da quantidade de bits usados.

Portanto, é importante reconhecer se um número é primo e em geral se ele é divisível por outro número inteiro. Isto implica na implementação de algoritmos como o algoritmo do mínimo denominador comum ou o crivo de Erastotenes de forma encapsulada e eficiente do ponto de vista da performance. Isto é a alma da Orientação a Objetos, onde as regras relativas ao objeto são contidas nele mesmo.

Resumo

Vimos no post anterior como a representação binária de números inteiros leva a uma representação truncada do conjuntos dos números inteiros. Neste post, vimos como as plataformas se utilizam da Orientação de Objetos e o padrão Value Object para criar uma representação de um número inteiro com  uma quantidade arbitrária de dígitos e bits para suprir necessidades na área da criptografia que é inerente a qualquer plataforma moderna. Além disto, este objeto resolve também o problema do overflow e underflow que existia e permite operações que são sempre exatas. Por que este tipo de objeto é muito importante para a plataforma a sua performance é normalmente uma preocupação. Na prática usar um BigInteger nas máquinas de hoje não representa um problema de performance já que se trata de um trade-off entre a exatidão das operações versus os recursos da máquina (memória e processamento). Veremos no próximo post da série como os números reais são representados e os problemas que derivam dai.





Desenvolvido por hacklab/ com WordPress