Armadilhas Numéricas – Inteiros – Parte I

Publicado por Sergio Taborda
03/6/2015
Categoria:
Tags: , , , ,

Este é o primeiro 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.

Toda a linguagem de programação que mereça esse nome deve permitir fazer cálculos. Aliás, o computador começou como uma grande máquina de fazer cálculos. Em linguagens fortemente tipadas como C# ou Java, fazer cálculos significa usar um tipo, uma classe, que de alguma forma represente o valor de um número. Por questões de performance e arquiteturas das máquinas virtuais as plataformas decidiram tratar estes tipos de uma forma especial mais próxima a como eram tratados em linguagens clássicas como Fortran ou C. Linguagens clássicas como Fortran ou C tinham a capacidade de representar alguns tipos diferentes, especialmente os numéricos.  Na realidade, a linguagem C tem apenas tipos numéricos e arrays, o resto deriva disso. Java e .Net herdam estas representações sob a forma de tipos primários (primitivos em java) que não são objetos, mas são usados para cálculos.  Esta é a encarnação mais antiga do padrão Value Object num tempo que sequer existiam objetos ainda (mas havia o conceito de tipos para as variáveis).

Durante esta série de artigos vamos ver como os números são representados nesses tipos especiais e os problemas que derivam dessa representação. Depois iremos ver como a Orientação a Objetos resolve a maior partes desses problemas e promove a escrita de código mais confiável.  Começamos pela representação de números inteiros.

Números Inteiros

A primeira versão de um tipo numérico foi a versão binária onde os bits dentro do valor do tipo representam, conforme o tipo, um valor. O tipo numérico mais simples é o inteiro. Aqui cada bit representa a presença de cada potência de 2 na composição do número. O número cento e cinco (105) é representado, em base dez, como:

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

Repare que os fatores ao lado das potencias vão de 0 a 9 (que é 10 -1). Em base 2, o mesmo valor é representado como

cento e cinco = 1 x 26 + 1 x 25 + 0 x 24 + 1 x 23 + 0 x 22 + 0 x 21 + 1 x 20 = 1101001

Neste caso os fatores vão de 0 a 1 ( que é 2- 1), o que significa que existem apenas dois valores possíveis para cada fator. Dai o conceito de binário.

O conjunto matemático dos números inteiros naturais |N0 contém todos os números naturais inteiros começando em zero e se estendendo ao infinito.  Este conjunto de números têm algumas propriedades interessantes.

A primeira é que existe uma operação soma (+) tal que, se n e m são números naturais inteiros então k = n+ m também é um número natural inteiro. Porque todos os números obtidos pela soma ainda estão dentro do mesmo conjunto diz-se que o |N0 é fechado para a soma. “Fechado” significa que nenhum número gerado pela soma, “escapa” do conjunto. Um conjunto que é fechado para uma dada operação é dito ser um Magma dessa operação.  Uma outra operação com esta mesma propriedade é a multiplicação. O conjunto dos inteiros naturais é, portanto, fechado para a soma e para a multiplicação.

Contudo, se pegarmos a subtração isto já não é verdade. 2 -3 dá um resultado fora do conjunto dos inteiros naturais e |N0 não é um magma para a subtração. O mesmo pode ser dito da divisão já que 2/3 não é um inteiro.

Representação Não-Finita, Truncagem e Overflow

No computador não temos infinitos números. Por que cada fator binário é representado por um bit, o número máximo está limitado pelo número de bits usados para representar o tipo. Tradicionalmente este número começou com 8 bits, mas hoje chega a 64 e em algumas máquinas pode chegar a 128.  Ora, isto não apenas limita o máximo valor para o inteiro, mas cria um subconjunto dos inteiros naturais que não é um magma para nenhuma operação, pois pode existir um n e um m tal que a soma não está no conjunto.

Quando há um cálculo em que o resultado seria maior que o maior número que cabe na representação diz-se que aconteceu um overflow. Quando o resultado seria menor que o menor número, diz-se que aconteceu um underflow.  Os engenheiros de outrora resolveram isto com um truque.

Primeiro fizeram o tipo representar um valor no conjunto dos números inteiros |Z e não apenas no dos naturais |N. Isto significa que número negativos também podem ser representados. |Z é um Magma para a subtração, portanto ganhamos uma operação a mais usando este tipo. Contudo, precisamos agora de um bit para representar se o número é positivo ou negativo (zero é considerado positivo), o que diminui os valores máximos possíveis, mas permite operações como 2-3 serem triviais.

Em segundo, eliminaram o problema de overflow e underflow forçando que a representação binária seja válida no fim da operação, mesmo que o número não seja matematicamente correto. É por isto que se você somar 1 a uma variável num laço de repetição infinito, uma hora o valor vira negativo. Isto foi o que aconteceu com o YouTube, do Google. Por tanto, lembre-se que não importa o quão grande é a empresa, estes erros acontecem com todo mundo. E quanto maiores eles são … menos cabem num inteiro.

Podemos ver isto  facilmente em código (C#).

var maiorInteiro = int.MaxValue; // o maior valor possivel representar com um inteiro
var menorInteiro = int.MinValue; // o menor valor psosivel representar com um inteiro
Assert.IsTrue(menorInteiro < maiorInteiro); // sim, é verdade.

var proximo = maiorinteiro + 1; // o que acontece ?
Assert.IsFalse(proximo >  maiorInteiro); // o próximo não é maior que o maior inteiro, pois nada é maior que o máximo.
Assert.AreEqual(menorInteiro, proximo); // o próximo é na realidade o menor

Nas linguagens de programação o tipo que permite isto é normalmente chamado de integer (ou abreviadamente int) do qual existem vários sabores conforme o tamanho em bits (byte para 8 bits, short para 16, int para 32, long para 64. No C o long é chamado long int e existe o long long que pode representar 128 bits nas máquinas que possibilitam isso). O valor inteiro sem sinal é chamado unsign int (inteiro não sinalizado, sem sinal) ou apenas uint.

Então, embora conceptualmente o tipo int representa um elemento do conjunto |Z as propriedades do cálculo não são exatamente as mesmas que aqueles dos elementos de |Z. Contudo, são próximas o suficiente para a maioria das computações. E são tão próximas que muitas vezes não pensamos nas diferenças.  O overflow de uma contagem pode facilmente se tornar um problema como no exemplo do youtube ou no caso do bug do milênio onde apenas dois dígitos eram usados para representar um número com quatro, neste caso o overflow iria significar que o ano 01 era antes de 99 o que era mentira pois 01 representava 2001 e 99 representava 1999.

Detecção de Overflow e Underflow

Como vimos os tipos inteiros da plataforma .Net e Java executam automaticamente aquilo que se chama de operações wrap-arround em que ao tentar obter um valor maior que o máximo valor , ou um valor menor que o mínimo valor, o resultado é o mínimo valor. As plataformas fazem isto silenciosamente, ou seja, não lançam exceções nem setam algum flag que nos permita verificar se o overflow aconteceu. Isto pode ser um problema, pois se quisermos garantir que nosso programa é correto, temos que gerar um erro sempre que isto acontecer. Para essas ocasiões existem opções.

Em C# é possível usar o bloco/função reservada checked que obriga ao lançamento de uma exceção se o overflow acontecer. No nosso exemplo de antes

//C#
checked {
var proximo = maiorinteiro + 1; // acontece uma exceção porque não é possível obter um valor maior que o máximo.</pre>
} 

Em java é possível usar a nova (java 8 ) família de funções exactas : addExact, subtractExact, incrementExact multiplyExact na classe Math.

Não existência da operação de divisão

Repare que nem |N, nem |Z, nem as versões truncadas usadas em computação são magmas para a divisão. Não existe divisão inteira. Ou seja, não existe uma operação que se n e m são inteiros, então, não é sempre verdade que k = n dividido para m pertence ao mesmo conjunto. Às vezes sim ( 8/2) às vezes não (2/3).  Se forem dados  n e m inteiros, então é sempre possível obter q e r inteiros tal que

m = n x q + r

Porque temos que calcular q e r , são necessárias duas operações, uma que dados n e m permite obter q (o quociente) e outra que permite obter r (o resto).

Tradicionalmente a primeira operação é batizada de Divisão Inteira  (um tipo especial de divisão) que permite obter q e que forma um magma em |Z. Em C# e Java , e na maioria das linguagens é usado o simbolo ‘/’ para divisão seja de inteiros ou não. Embora isto seja mais próximo da representação a que estamos habituados não é matematicamente correto. Algumas linguagens optam por usar outros símbolos para a divisão inteira como  ’//’ (python) para, exatamente, lembrar o programador que não irá ser feita a operação matemática que se espera. O que será feita é uma operação especial chamada Divisão Inteira..

A outra operação é batizada normalmente de Módulo e permite obter r. Esta operação também forma um magma em |Z.  Em C# e Java esta operação é escrita usando o operador % onde r = n % m. Em outras linguagem , como visual basic, é escrita como r = n mod m

Lembre-se que n/ m não significa a divisão real dos números, mas apenas a divisão inteira ou seja 3/2 não é 1.5 , é 1. É comum este erro quanto o programador tem dois inteiros e deseja obter um número real a partir da divisão (por exemplo, para encontrar proporções). Normalmente o programador esquece que / define uma operação especial e não a divisão que ele espera. Isto leva a resultados inesperados. A solução é normalmente forçar um cast para double para que a divisão real aconteça ( o que pode não ser uma melhor solução como veremos mais à frente nesta série).

Resumo

A representação binária de números inteiros diminui o espaço na memória para guardar a representação do número e ajuda a acelerar os cálculos. Contudo, leva a uma representação truncada do conjuntos dos números inteiros (|Z) e a efeitos indesejáveis de overflow. Esta representação limitada pelo número de bits não é apropriada no mundo de hoje , como seja, para o cálculo de chaves criptográficas que normalmente contém 128 bits ou mais e são obtidas por algoritmos matemáticos. Veremos no próximo artigo desta série como as plataformas resolvem este problema com a ajuda da Orientação a Objetos. Mais tarde nesta série focaremos nossa atenção à representação de números reais e seus desafios.





Desenvolvido por hacklab/ com WordPress