Operação modular com números negativos

No programa ac eu estava tentando as operações abaixo (só para verificar o comportamento)

x = 5 % (-3); y = (-5) % (3); z = (-5) % (-3); printf("%d ,%d ,%d", x, y, z); 

me deu saída como (2, -2 , -2) no gcc. Eu estava esperando um resultado positivo o tempo todo. Um módulo pode ser negativo? Alguém pode explicar esse comportamento?

C99 requer que quando a/b é representável:

(a/b) * b + a%b será igual a

Isso faz sentido, logicamente. Certo?

Vamos ver o que isso leva a:


Exemplo A. 5/(-3) é -1

=> (-1) * (-3) + 5%(-3) = 5

Isso só pode acontecer se 5%(-3) for 2.


Exemplo B. (-5)/3 é -1

=> (-1) * 3 + (-5)%3 = -5

Isso só pode acontecer se (-5)%3 for -2

O operador % em C não é o operador de módulo , mas o operador restante .

Os operadores de módulos e de descanso diferem em relação aos valores negativos.

Com um operador de resto, o sinal do resultado é o mesmo que o sinal do dividendo, enquanto que com um operador de módulo o sinal do resultado é o mesmo que o divisor.

C define a operação % para a % b como:

  a == (a / b * b) + a % b 

com / a divisão inteira com truncamento para 0 . Esse é o truncamento que é feito em direção a 0 (e não em relação à inifinidade negativa) que define o % como um operador de descanso, em vez de um operador de módulo.

Baseado na especificação C99: a = (a / b) * b + a % b

Podemos escrever uma function para calcular (a % b) = a - (a / b) * b !

 int remainder(int a, int b) { return a - (a / b) * b; } 

Para operação do módulo, podemos ter a seguinte function (assumindo b> 0)

 int mod(int a, int b) { int r = a % b; return r < 0 ? r + b : r; } 

Minha conclusão é (a% b) em C é um operador de resto e NÃO operador de módulo.

Eu não acho que seja necessário verificar se o número é negativo. A function geral mais simples para encontrar o módulo positivo seria isso – funcionaria em valores positivos e negativos de x.

 int modulo(int x,int N){ return (x % N + N) %N; } 

As outras respostas foram explicadas em C99 ou mais tarde, a divisão de inteiros envolvendo operandos negativos sempre trunca em direção a zero .

Observe que, em C89 , se o resultado arredondado para cima ou para baixo é definido pela implementação. Como (a/b) * b + a%b é igual a a em todos os padrões, o resultado de % envolvendo operandos negativos também é definido pela implementação em C89.

O resultado da operação Modulo depende do sinal do numerador e, portanto, você obtém -2 para y e z

Aqui está a referência

http://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_14.html

Divisão Integer

Esta seção descreve as funções para executar a divisão de inteiros. Essas funções são redundantes na biblioteca GNU C, já que no GNU C o operador ‘/’ sempre arredonda para zero. Mas em outras implementações C, ‘/’ pode arredondar de forma diferente com argumentos negativos. div e ldiv são úteis porque especificam como arredondar o quociente: para zero. O restante tem o mesmo sinal do numerador.

Na Matemática, de onde decorrem essas convenções, não há nenhuma afirmação de que a aritmética modular deva produzir um resultado positivo.

Por exemplo.

1 mod 5 = 1, mas também pode ser igual a -4. Ou seja, 1/5 produz um resto 1 de 0 ou -4 de 5. (Ambos os fatores de 5)

Similarmente, -1 mod 5 = -1, mas também pode ser igual a 4. Ou seja, -1/5 produz um resto -1 de 0 ou 4 de -5. (Ambos os fatores de 5)

Para ler mais, examine as classs de equivalência em Matemática.

Operador de módulo dá o restante. Operador de módulo em c geralmente leva o sinal do numerador

  1. x = 5% (-3) – aqui o numerador é positivo, portanto resulta em 2
  2. y = (-5)% (3) – aqui o numerador é negativo, portanto, resulta -2
  3. z = (-5)% (-3) – aqui o numerador é negativo, portanto, resulta -2

Também o operador de módulo (restante) só pode ser usado com o tipo inteiro e não pode ser usado com ponto flutuante.

O operador de módulo é como o operador mod quando o número é positivo, mas diferente se o número for negativo.

Muitas vezes nos problemas nos é pedido para dar a resposta módulo 10 ^ 9 + 7.

Deixe a resposta (antes de usar o modulo) ser denotada por ‘a’.

Regra simples e direta

se a é positivo , então um módulo 10 ^ 9 + 7 = a% (10 ^ 9 + 7)

se a é negativo , então um módulo 10 ^ 9 + 7 = (a% (10 ^ 9 + 7)) + (10 ^ 9 + 7)

Se, em tais problemas, descobrirmos que qualquer etapa do loop pode calcular um valor que esteja fora do intervalo inteiro (se estivermos usando números inteiros), então podemos usar o operador de módulo nesse próprio passo. A resposta final será como se tivéssemos usado o operador de módulo apenas uma vez.

Isso ocorre porque- (a * b)% c = ((a% c) (b% c))% c O mesmo vale para adição e subtração.

De acordo com o padrão C99 , seção 6.5.5 Operadores multiplicativos , é necessário o seguinte:

 (a / b) * b + a % b = a 

Conclusão

O sinal do resultado de uma operação remanescente, de acordo com C99, é o mesmo que o do dividendo.

Vamos ver alguns exemplos ( dividend / divisor ):

Quando apenas o dividendo é negativo

 (-3 / 2) * 2 + -3 % 2 = -3 (-3 / 2) * 2 = -2 (-3 % 2) must be -1 

Quando apenas o divisor é negativo

 (3 / -2) * -2 + 3 % -2 = 3 (3 / -2) * -2 = 2 (3 % -2) must be 1 

Quando ambos divisor e dividendo são negativos

 (-3 / -2) * -2 + -3 % -2 = -3 (-3 / -2) * -2 = -2 (-3 % -2) must be -1 

6.5.5 Operadores multiplicativos

Sintaxe

  1. expressão multiplicativa:
    • cast-expression
    • multiplicative-expression * cast-expression
    • multiplicative-expression / cast-expression
    • multiplicative-expression % cast-expression

Restrições

  1. Cada um dos operandos deve ter tipo aritmético. Os operandos do operador % devem ter um tipo inteiro.

Semântica

  1. As conversões aritméticas usuais são realizadas nos operandos.

  2. O resultado do operador binário * é o produto dos operandos.

  3. O resultado do operador / é o quociente da divisão do primeiro operando pelo segundo; o resultado do operador % é o restante. Em ambas as operações, se o valor do segundo operando for zero, o comportamento é indefinido.

  4. Quando inteiros são divididos, o resultado do operador / é o quociente algébrico com qualquer parte fracionária descartada [1]. Se o quociente a/b é representável, a expressão (a/b)*b + a%b será igual a .

[1]: isso geralmente é chamado de “truncamento em direção a zero”.