Mod de número negativo está derretendo meu cérebro

189

Estou tentando modificar um número inteiro para obter uma posição de matriz para que ele faça um loop redondo. Fazer i % arrayLengthfunciona bem para números positivos, mas para números negativos tudo dá errado.

 4 % 3 == 1
 3 % 3 == 0
 2 % 3 == 2
 1 % 3 == 1
 0 % 3 == 0
-1 % 3 == -1
-2 % 3 == -2
-3 % 3 == 0
-4 % 3 == -1

então eu preciso de uma implementação de

int GetArrayIndex(int i, int arrayLength)

de tal modo que

GetArrayIndex( 4, 3) == 1
GetArrayIndex( 3, 3) == 0
GetArrayIndex( 2, 3) == 2
GetArrayIndex( 1, 3) == 1
GetArrayIndex( 0, 3) == 0
GetArrayIndex(-1, 3) == 2
GetArrayIndex(-2, 3) == 1
GetArrayIndex(-3, 3) == 0
GetArrayIndex(-4, 3) == 2

Eu já fiz isso antes, mas por algum motivo está derretendo meu cérebro hoje :(

Coronel Panic
fonte
Consulte a discussão sobre o módulo matemático em math.stackexchange.com/questions/519845/…
PPC

Respostas:

281

Eu sempre uso minha própria modfunção, definida como

int mod(int x, int m) {
    return (x%m + m)%m;
}

Claro, se você está preocupado em ter duas chamadas para a operação do módulo, você pode escrevê-lo como

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

ou variantes dos mesmos.

A razão pela qual isso funciona é que "x% m" está sempre no intervalo [-m + 1, m-1]. Portanto, se for negativo, adicionar m a ele o colocará na faixa positiva sem alterar seu valor módulo m.

ShreevatsaR
fonte
7
Nota: para uma completa integralidade da teoria dos números, você pode adicionar uma linha no topo dizendo "if (m <0) m = -m;" embora, nesse caso, não importe como "arrayLength" presumivelmente sempre positivo.
ShreevatsaR
4
Se você deseja verificar o valor de m, também deve excluir zero.
billpg
6
@RuudLenders: No. Se X = -5 e m = 2, em seguida, r = x%mé -1, após o que r+mé 1. O loop while não é necessário. O ponto é que (como escrevi na resposta), x%mé sempre estritamente maior que -m, então você precisa adicionar mno máximo uma vez para torná-lo positivo.
ShreevatsaR
4
@dcastro: Eu não quero -12 mod -10 a ser 8. Esta é a convenção mais comum em matemática, que, se escolher um representante rpara amodulo b, então é tal que 0 ≤ r <| b |.
precisa saber é o seguinte
8
+1. Não me importo com o que qualquer linguagem individual faz para um módulo negativo - o 'menor resíduo não negativo' exibe uma regularidade matemática e remove qualquer ambiguidade.
Brett Hale
80

Observe que o operador% C # e C ++ não é realmente um módulo, é o restante. A fórmula para o módulo que você deseja, no seu caso, é:

float nfmod(float a,float b)
{
    return a - b * floor(a / b);
}

Você precisa recodificar isso em C # (ou C ++), mas é assim que obtém o módulo e não o restante.

Петър Петров
fonte
21
"Observe que o operador% C ++ realmente não é um módulo, é o restante." Obrigado, faz sentido agora, sempre se pergunte por que nunca funcionou corretamente com números negativos.
LeetNightshade
2
"Observe que o operador% C ++ realmente não é um módulo, é o restante." Eu não acho que isso seja preciso e não vejo por que um módulo é diferente do restante. É o que também diz na página da Wikipedia sobre a Operação Modulo. As linguagens de programação tratam os números negativos de maneira diferente. O operador módulo em C # obviamente conta os restantes "de" zero (-9% 4 = -1, porque 4 * -2 é -8 com uma diferença de -1) enquanto outra definição consideraria -9% 4 como +3, porque -4 * 3 é -12, restante +3 (como na função de pesquisa do Google, não tem certeza do idioma de back-end).
Tyress
18
Tyress, existe uma diferença entre o módulo e o restante. Por exemplo: -21 mod 4 is 3 because -21 + 4 x 6 is 3. Mas -21 divided by 4 gives -5com a remainder of -1. Para valores positivos, não há diferença. Portanto, informe-se sobre essas diferenças. E não confie na Wikipedia o tempo todo :) #
6601
2
Por que alguém iria querer usar a função restante em vez de um módulo? Por que eles fizeram o %restante?
Aaron Franke
4
@AaronFranke - é um legado de cpus anteriores que tinham hardware de divisão para produzir rapidamente um quociente e um restante - e foi isso que esse hardware fez com um dividendo negativo. A linguagem simplesmente espelhava o hardware. Na maioria das vezes, os programadores trabalhavam com dividendos positivos e ignoravam essa peculiaridade. A velocidade era primordial.
Página
16

Implementação de linha %única usando apenas uma vez:

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }
Evgeni Sergeev
fonte
1
isto está correto? como eu não vejo como aceito por ninguém, nem qualquer comentário a ele. Por exemplo. mod (-10,6) retornará 6. Está correto? não deveria retornar 4?
John Demetriou
3
@JohnDemetriou Seus números estão errados: (A) deve retornar 2 e (B) retorna 2; tente executar o código. Item (A): para encontrar mod(-10, 6)à mão, você adiciona ou subtrai 6 repetidamente até que a resposta esteja no intervalo [0, 6). Essa notação significa "inclusivo à esquerda e exclusivo à direita". No nosso caso, adicionamos 6 duas vezes, fornecendo 2. O código é bastante simples e é fácil perceber que está certo: primeiro, ele equivale a adicionar / subtrair ncomo acima, exceto que ele para um npouco, se estiver se aproximando de o lado negativo. Nesse caso, nós corrigimos isso. LÁ: comentários :)
Evgeni Sergeev
1
A propósito, aqui está uma razão pela qual usar um single %pode ser uma boa ideia. Consulte a tabela Quanto custa o código gerenciado no artigo Escrevendo código gerenciado mais rápido: Saiba o que custa . O uso %é similar ao int divlistado na tabela: cerca de 36 vezes mais caro do que adicionar ou subtrair e 13 vezes mais caro do que multiplicar. Obviamente, não é grande coisa, a menos que isso esteja no cerne do que seu código está fazendo.
Evgeni Sergeev
2
Mas é um item %mais caro que um teste e um salto, especialmente se não puder ser facilmente previsto?
Medinoc 25/10
6

A resposta de ShreevatsaR não funcionará para todos os casos, mesmo se você adicionar "se (m <0) m = -m;", se você considerar dividendos / divisores negativos.

Por exemplo, -12 mod -10 será 8 e deve ser -2.

A implementação a seguir funcionará para dividendos / divisores positivos e negativos e está em conformidade com outras implementações (Java, Python, Ruby, Scala, Scheme, Javascript e Calculadora do Google):

internal static class IntExtensions
{
    internal static int Mod(this int a, int n)
    {
        if (n == 0)
            throw new ArgumentOutOfRangeException("n", "(a mod 0) is undefined.");

        //puts a in the [-n+1, n-1] range using the remainder operator
        int remainder = a%n;

        //if the remainder is less than zero, add n to put it in the [0, n-1] range if n is positive
        //if the remainder is greater than zero, add n to put it in the [n-1, 0] range if n is negative
        if ((n > 0 && remainder < 0) ||
            (n < 0 && remainder > 0))
            return remainder + n;
        return remainder;
    }
}

Conjunto de testes usando xUnit:

    [Theory]
    [PropertyData("GetTestData")]
    public void Mod_ReturnsCorrectModulo(int dividend, int divisor, int expectedMod)
    {
        Assert.Equal(expectedMod, dividend.Mod(divisor));
    }

    [Fact]
    public void Mod_ThrowsException_IfDivisorIsZero()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => 1.Mod(0));
    }

    public static IEnumerable<object[]> GetTestData
    {
        get
        {
            yield return new object[] {1, 1, 0};
            yield return new object[] {0, 1, 0};
            yield return new object[] {2, 10, 2};
            yield return new object[] {12, 10, 2};
            yield return new object[] {22, 10, 2};
            yield return new object[] {-2, 10, 8};
            yield return new object[] {-12, 10, 8};
            yield return new object[] {-22, 10, 8};
            yield return new object[] { 2, -10, -8 };
            yield return new object[] { 12, -10, -8 };
            yield return new object[] { 22, -10, -8 };
            yield return new object[] { -2, -10, -2 };
            yield return new object[] { -12, -10, -2 };
            yield return new object[] { -22, -10, -2 };
        }
    }
dcastro
fonte
Primeiro, uma modfunção geralmente é chamada com módulo positivo (observe a variável arrayLengthna pergunta original que está sendo respondida aqui, que provavelmente nunca é negativa), portanto, a função não precisa realmente ser feita para funcionar com o módulo negativo. (É por isso que eu mencionar o tratamento de módulo negativo em um comentário sobre a minha resposta, não na própria resposta.) (Cont ...)
ShreevatsaR
3
(... continua) Em segundo lugar, o que fazer para um módulo negativo é uma questão de convenção. Veja, por exemplo, a Wikipedia . "Geralmente, na teoria dos números, o restante positivo é sempre escolhido", e foi assim que eu também aprendi (na teoria elementar dos números de Burton ). Knuth também define dessa maneira (especificamente, r = a - b floor(a/b)é sempre positivo). Mesmo entre os sistemas de computadores, Pascal e Maple, por exemplo, definem que é sempre positivo.
precisa saber é o seguinte
@ShreevatsaR Eu sei que a definição euclidiana afirma que o resultado sempre será positivo - mas tenho a impressão de que a maioria das implementações modernas de mod retornará um valor no intervalo [n + 1, 0] para um divisor negativo "n", o que significa que -12 mod -10 = -2. Eu examinei o Google Calculator , Python , Ruby e Scala , e todos seguem esta convenção.
dcastro
Além disso, para adicionar à lista: Esquema e Javascript
dcastro
1
Novamente, essa ainda é uma boa leitura. A definição "sempre positiva" (minha resposta) é consistente com ALGOL, Dart, Maple, Pascal, Z3, etc. O "sinal de divisor" (esta resposta) é consistente com: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl, etc. Ambos são inconsistentes com "sinal de dividendo", como em: AWK, bash, bc, C99, C ++ 11, C #, D, Eiffel, Erlang, Go, Java , OCaml, PHP, Rust, Scala, Swift, VB, x86 assembly, etc. Não vejo como você pode afirmar que uma convenção está "correta" e outras "errada".
ShreevatsaR
6

Adicionando alguma compreensão.

Pela definição euclidiana, o resultado da modificação deve ser sempre positivo.

Ex:

 int n = 5;
 int x = -3;

 int mod(int n, int x)
 {
     return ((n%x)+x)%x;
 }

Resultado:

 -1
Um balde
fonte
15
Estou confuso ... você diz que o resultado sempre deve ser positivo, mas depois lista a saída como -1?
Jeff B
@JeffBridgman Eu afirmei isso com base na definição euclidiana. `existem duas opções possíveis para o restante, uma negativa e outra positiva, e também existem duas opções possíveis para o quociente. Geralmente, na teoria dos números,, the positive remainder is always chosenmas as linguagens de programação escolhem dependendo da linguagem e dos sinais de a e / ou n. [5] Padrão Pascal e Algol68 dar um resto positivo (ou 0), mesmo para divisores negativas, e algumas linguagens de programação, tais como C90, deixá-lo até a implementação quando uma das n ou é negative.`
Abin
5

Comparando duas respostas predominantes

(x%m + m)%m;

e

int r = x%m;
return r<0 ? r+m : r;

Na verdade, ninguém mencionou o fato de que o primeiro pode dar um OverflowExceptiontempo enquanto o segundo não. Pior ainda, com o contexto desmarcado padrão, a primeira resposta pode retornar a resposta errada (veja, mod(int.MaxValue - 1, int.MaxValue)por exemplo). Portanto, a segunda resposta não apenas parece mais rápida, mas também mais correta.

lilo0
fonte
4

Basta adicionar seu módulo (arrayLength) ao resultado negativo de% e você ficará bem.

starblue
fonte
4

Para os desenvolvedores mais atentos ao desempenho

uint wrap(int k, int n) ((uint)k)%n

Uma pequena comparação de desempenho

Modulo: 00:00:07.2661827 ((n%x)+x)%x)
Cast:   00:00:03.2202334 ((uint)k)%n
If:     00:00:13.5378989 ((k %= n) < 0) ? k+n : k

Quanto ao custo de desempenho do elenco para o uint, dê uma olhada aqui

Markus Cozowicz
fonte
3
Pensamentos que -3 % 10devem ser -3 ou 7. Como se deseja um resultado não negativo, 7 seria a resposta. Sua implementação retorna 3. Você deve alterar os dois parâmetros uinte remover a conversão.
Gostei do antigo Stack Overflow
5
A aritmética não assinada é equivalente apenas se nfor uma potência de dois; nesse caso, você pode simplesmente usar um lógico e ( (uint)k & (n - 1)), se o compilador ainda não fizer isso por você (os compiladores geralmente são inteligentes o suficiente para descobrir isso).
precisa saber é o seguinte
2

Gosto do truque apresentado por Peter N Lewis neste tópico : "Se n tiver um intervalo limitado, você poderá obter o resultado desejado simplesmente adicionando um múltiplo constante conhecido do [divisor] que é maior que o valor absoluto do mínimo."

Então, se eu tenho um valor d que está em graus e quero tirar

d % 180f

e quero evitar os problemas se d for negativo, em vez disso, basta fazer o seguinte:

(d + 720f) % 180f

Isso pressupõe que, embora d possa ser negativo, sabe-se que nunca será mais negativo que -720.

RenniePet
fonte
2
-1: não é geral o suficiente (e é muito fácil fornecer uma solução mais geral).
Evgeni Sergeev
4
Isso é realmente muito útil. quando você tem um alcance significativo, isso pode simplificar a computação. no meu caso math.stackexchange.com/questions/2279751/…
M.kazem Akhgary
Exatamente, apenas usei isso para o cálculo dayOfWeek (intervalo conhecido de -6 a +6) e economizou dois %.
NetMage 10/04/19
@EvgeniSergeev +0 para mim: não responde à pergunta do OP, mas pode ser útil em um contexto mais específico (mas ainda no contexto da pergunta)
Erdal G. 30/04
1

Você espera um comportamento contrário ao comportamento documentado do operador% em c # - possivelmente porque espera que ele funcione de uma maneira que funcione em outro idioma com o qual você está mais acostumado. A documentação sobre estados c # (ênfase minha):

Para os operandos de tipos inteiros, o resultado de a% b é o valor produzido por a - (a / b) * b. O sinal do restante diferente de zero é o mesmo que o do operando esquerdo

O valor que você deseja pode ser calculado com uma etapa extra:

int GetArrayIndex(int i, int arrayLength){
    int mod = i % arrayLength;
    return (mod>=0) : mod ? mod + arrayLength;
}
Andrew
fonte
1

Uma implementação de linha única da resposta do dcastro (a mais compatível com outros idiomas):

int Mod(int a, int n)
{
    return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
}

Se você deseja manter o uso do %operador (não é possível sobrecarregar os operadores nativos em C #):

public class IntM
{
    private int _value;

    private IntM(int value)
    {
        _value = value;
    }

    private static int Mod(int a, int n)
    {
        return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
    }

    public static implicit operator int(IntM i) => i._value;
    public static implicit operator IntM(int i) => new IntM(i);
    public static int operator %(IntM a, int n) => Mod(a, n);
    public static int operator %(int a, IntM n) => Mod(a, n);
}

Caso de uso, ambos funcionam:

int r = (IntM)a % n;

// Or
int r = a % n(IntM);
Erdal G.
fonte
0

Todas as respostas aqui funcionam muito bem se o seu divisor for positivo, mas não está completo. Aqui está minha implementação, que sempre retorna em um intervalo de [0, b), de modo que o sinal da saída seja o mesmo que o sinal do divisor, permitindo divisores negativos como o ponto final do intervalo de saída.

PosMod(5, 3)retorna 2
PosMod(-5, 3)retorna 1
PosMod(5, -3)retorna -1
PosMod(-5, -3)retorna-2

    /// <summary>
    /// Performs a canonical Modulus operation, where the output is on the range [0, b).
    /// </summary>
    public static real_t PosMod(real_t a, real_t b)
    {
        real_t c = a % b;
        if ((c < 0 && b > 0) || (c > 0 && b < 0)) 
        {
            c += b;
        }
        return c;
    }

(onde real_tpode ser qualquer tipo de número)

Aaron Franke
fonte