Alguns meses atrás resolvi implementar as operações aritméticas fundamentais para inteiros de precisão arbitrária. O principal motivo era mais curiosidade do que necessidade, já que existem várias boas bibliotecas por aí com esse foco. Ainda assim, achei que valeria à pena o exercício e diversão.
Originalmente estava atrás de algo bem simplista, mas ao longo do percurso o código acabou tomando mais forma e eventualmente se transformou em uma classe C++ de API bem definida. Basicamente, foram aparecendo as conexões lógicas, uma coisa foi levando a outra, e no final das contas acabei implementando mais do que planejado.
A referência que utilizei foi o volume de Seminumerical Algorithms do livro do Knuth, The Art of Computer Programming. Naturalmente, o legal é que mesmo o livro se preocupando em mencionar dicas de implementação, ainda há espaço para muitas questões no processo de conversão da descrição algorítmica para a o código final em C++.
Pontos interessantes que observei…
- Antes que qualquer coisa, o primeiro passo foi pensar em qual o modelo de representação a ser usado. Bom, no mundo binário a opção mais comum é o complemento de dois. No entanto, no caso de precisão arbitrária em um nível mais alto a base numérica é tipicamente um inteiro grande, logo uma abordagem de magnitude e sinal passa a ser uma boa opção.
- Considerando magnitude e sinal, há ainda um aspecto flexível que é justamente a questão do zero. Qualificá-lo explicitamente ou utilizar apenas dois sinais e inferi-lo a partir dos valores? Achei mais simples e consistente ter um atributo que indica se o número é positivo, negativo ou zero.
- Qual estrutura de dados e onde colocar os dígitos mais significativos? Normalmente um vetor é uma boa opção. Fornece acesso aleatório, você pode controlar a alocação com certa previsibilidade, não há overhead de espaço, a memória é contínua e há um mapeamento “natural” das operações. Com relação a posição dos dígitos mais significativos, colocá-los no final do vetor é o convencional, já que permite o crescimento/decrescimento do inteiro de forma eficiente.
- Continuando o parágrafo acima, existe a necessidade de eliminar zeros iniciais que podem resultar de algumas operações. Isso facilita a implementação em geral. Além disso, como o zero não é representado apenas pela magnitude também precisei adicionar verificações um pouco “artificiais” após alguns cálculos.
- As operações de adição, subtração e multiplicação são bem intuitivas. Nada muito elaborado, o único cuidado é com o tratamento do carry. Já a divisão com resto, essa é outra história. Obviamente, você pode seguir um algoritmo simples de subtrações consecutivas, mas eu queria algo mais bacana. O algoritmo apresentado no livro do Knuth é baseado na normalização do divisor e dividendo e de se estimar um valor para o quociente. Alguns detalhes são não-triviais e eu diria que há um certo potencial para erros na implementação. ;-) Nota: Há duas correções deste algoritmo na errata do livro.
- Saindo do planejado… Acaba que para a divisão acima tive que implementar também as operações de shift esquerda/direita. Elas são recomendadas para a etapa de normalização. As outras operações que são uma evolução natural de usabilidade são as de conversão entre a base da representação e a base decimal. Isso permite a construção e impressão fáceis dos números a partir de uma string.
- Testes, é claro. Afinal de contas, você precisa verificar de alguma forma se as coisas estão funcionando. Como neste caso estamos lidando com números de precisão arbitrária você precisa de uma ferramenta auxiliar. Por exemplo, uma calculadora poderosa ou uma outra biblioteca de inteiros grandes.
Bom, eu já tinha disponibilidade o código há um tempinho, mas só agora resolvi escrever o blog. Ah, dê uma olhada nas notas antes…
O código está aqui: vlint (Very Long Integer)
Tchau!
Leandro Melo
Parabéns pelo excelente blog, vou ler todos os posts, pois esse é um blog com características muito próximas da que eu queria montar pra mim.
Sucesso :-)