Cuidado com o que você pensa que sabe…

Recentemente topei com um exemplo que deveria ser absolutamente simples e já estar “no sangue” de qualquer estudante do ensino básico (note bem: básico!). Por exemplo, o resto da divisão de 2 por 3 (2\mod 3) é 2, certo? Parece lógico extrapolar e dizermos que -2\mod 3=-2. Surpresa! A resposta pode estar errada, dependendo de qual definição de resto você usa! O problema está na definição de resto. Usando o método do truncamento do quociente, temos:

\displaystyle x\mod y=x - y\cdot trunc\left(\frac{x}{y}\right)

Mas, também existe a definição de Knuth:

\displaystyle x\mod y=x - y\left\lfloor\frac{x}{y}\right\rfloor

Ao usarmos essa definição teremos:

\displaystyle \begin{matrix}  -2\mod 3 &= (-2)-3\left\lfloor-\frac{2}{3}\right\rfloor \\  &= (-2)-3(-1) \\  &= -2+3 = 1 \\  \end{matrix}

Isso parece estranho até você lembrar da regrinha sobre o resto: Ele precisa ser sempre menor que o divisor. Mas qualquer valor negativo é menor que 3, certo? Portanto a restrição de que o quociente seja calculado através do operador floor, faz todo sentido…

Ainda, é interessante notar que, de acordo com a definição acima, o resto tem valor absoluto diferente nas expressões abaixo. Ele segue o sinal do divisor:

\displaystyle \begin{matrix}  -2\mod -3 = (-2)-(-3)\left\lfloor\frac{2}{3}\right\rfloor = -2 \\  2\mod -3 = 2-(-3)\left\lfloor-\frac{2}{3}\right\rfloor = -1 \\  -2\mod 3 = (-2)-3\left\lfloor-\frac{2}{3}\right\rfloor = 1 \\  2\mod 3 = 2-3\left\lfloor\frac{2}{3}\right\rfloor = 2 \\  \end{matrix}

Uma interpretação geométrica para o método de Knuth pode ser a de que a operação mod restringe o co-domínio da função para valores no intervalo entre 0 e o valor mais próximo (porém, absolutamente menor) que o do divisor, formando um “loop”. No caso de divisores positivos, o loop ficaria assim:

loop

Partindo de zero, uma vez que o dividendo (numerador) tem sinal contrário ao divisor (denominador), o ponteiro do “relógio” tem que ser “girado” duas casas no sentido “anti-horário” e obtemos o valor 1, como mostrado acima. No caso de um divisor negativo, a graduação é feita no sentido anti-horário usando 0, -1 e -2 e, se o dividendo tiver sinal contrário (positivo) o ponteiro girará no sentido horário, obtendo -1 (como pode ser visto na lista acima)… No caso de a=-2 e b=-3, a operação a\mod b graduará o loop no sentido anti-horário com 0, -1 e -2, já que o divisor é negativo, e o ponteiro será girado no mesmo sentido, já que o dividendo (numerador) também é negativo e, por isso, obtemos -2.

Essa é uma forma interessante de se entender o chamado complemento 2, usado na aritmética binária com sinais… Considere um conjunto com 16 valores possíveis (ou, 4 bits). O valor -2 deverá ser representado pelo valor positivo 14, já que -2\mod 16=14, segundo a definição. Isso também fica simples de representar geometricamente, graduando o loop no sentido horário e deslocando o ponteiro do “relógio” duas posições no sentido anti-horário:

loop2

Para maior quantidade de bits, mais graduações teremos no loop…

O problema é que a maioria das linguagens de programação lidam com o resto através do truncamento do quociente. Eis dois exemplos, o primeiro em Java:

/* test.java */
class test {
  public static void main(String[] args)
  { 
    int x = -2;
    int y = 3;
    int r = x % y;
    System.out.println(r); 
  }
}

Compilando e executando, obtemos:

$ javac test.java
$ java test
-2

A mesma coisa ocorre em C, C++ e Pascal (embora o Pascal padrão sempre resulte num resto positivo!), por exemplo… Quanto aos processadores, os compatíveis com a arquitetura Intel x86 possuem a instrução IDIV, que é definida como (quando a divisão é feita com valores de 32 bits):

Signed divide EDX:EAX by r/m32, with result stored in EAX ← Quotient, EDX ← Remainder

Assim, para obter o resto de uma divisão inteira temos que colocar o numerador no par de registradores EDX:EAX, o denominador em um outro lugar, executar IDIV e obter o resto em EDX. A função, para ser usada em C fica assim:

; mymod.asm
bits 64
section .text
global mymod
; Retorna A mod B.
; Entrada: EDI = A; ESI = B
; Saída: EAX = resto
mymod:
  mov  eax,edi
  cdq          ; estende o sinal de 'A' em EDX.
  idiv esi
  mov  eax,edx ; queremos só o resto.
  ret

Usarei a função da seguinte maneira:

/* test.c */
#include <stdio.h>

extern int mymod(int, int);

void main(void)
{ printf("%d\n", mymod(-2,3)); }

Compilando tudo, linkando e executando, temos:

$ nasm -felf64 mymod.asm -o mymod.o
$ gcc -c -o test.o test.c
$ gcc -o test test.o mymod.o
$ ./test
-2

Ou seja, o processador também calcula o resto de maneira “tradicional”, truncando…

O outro método é o de Euclides e pode ser equacionado assim:

\displaystyle x\mod y = x - \left|y\right|\left\lfloor\frac{x}{\left|y\right|}\right\rfloor

Que, é claro, é bem mais complicado e tem como resultado o mesmo valor obtido pelo método de Knuth, exceto que o sinal do resto não é sempre o mesmo do divisor…

ATENÇÃO: Os 3 métodos são “corretos”, depende somente como uma divisão é definida!!

O alerta aqui é que, se você está adaptando uma equação que use aritmética modular (mod) na implementação que usa valores negativos, pode ser que tenha problemas com os resultados se não estiver certo sobre o método que o compilador/linguagem está lidando.

Como falei antes, a maioria das linguagens usa o método do truncamento do quociente, mas nem todas. Uma exceção interessante: Python calcula o resto usando o método de Knuth

$ python
Python 2.7.12 (default, Nov 19 2016, 06:48:10) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> -2 % 3
1
>>>^D
$

A mesma coisa acontece com a aplicação gnome-calculator

Anúncios