Mod liczby ujemnej topi mój mózg

195

Próbuję zmodyfikować liczbę całkowitą, aby uzyskać pozycję tablicy, tak aby była zapętlona. Działanie i % arrayLengthdziała dobrze w przypadku liczb dodatnich, ale w przypadku liczb ujemnych wszystko idzie źle.

 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

więc potrzebuję implementacji

int GetArrayIndex(int i, int arrayLength)

takie że

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

Robiłem to już wcześniej, ale z jakiegoś powodu dziś topi mi mózg :(

Colonel Panic
źródło
Zobacz dyskusję na temat modułu matematycznego na math.stackexchange.com/questions/519845/ ...
PPC

Odpowiedzi:

290

Zawsze używam własnej modfunkcji, zdefiniowanej jako

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

Oczywiście, jeśli martwisz się o dwa wywołania operacji modułu, możesz zapisać to jako

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

lub ich warianty.

Powodem tego jest to, że "x% m" zawsze mieści się w zakresie [-m + 1, m-1]. Jeśli więc w ogóle jest ujemny, dodanie do niego m spowoduje umieszczenie go w dodatnim zakresie bez zmiany jego wartości modulo m.

ShreevatsaR
źródło
7
Uwaga: aby uzyskać kompletność teoretyczną liczb, możesz dodać wiersz u góry z napisem „if (m <0) m = -m;” chociaż w tym przypadku nie ma to znaczenia, ponieważ „arrayLength” jest przypuszczalnie zawsze dodatnia.
ShreevatsaR
5
Jeśli zamierzasz sprawdzić wartość m, powinieneś również wykluczyć zero.
billpg
6
@RuudLenders: Nie. Jeśli x = -5 im = 2, to r = x%mjest -1, po którym r+mjest 1. Pętla while nie jest potrzebna. Chodzi o to, że (jak napisałem w odpowiedzi) x%mjest zawsze ściśle większa niż -m, więc musisz dodać mco najwyżej raz, aby było dodatnie.
ShreevatsaR
4
@dcastro: Chcę , aby -12 mod -10 było równe 8. To jest najczęstsza konwencja w matematyce, że jeśli wybieramy reprezentanta rdla amodulo b, to jest takie, że 0 ≤ r <| b |.
ShreevatsaR
8
+1. Nie obchodzi mnie, co jakikolwiek język robi z ujemnym modułem - „najmniejsza nieujemna reszta” wykazuje matematyczną prawidłowość i usuwa wszelkie niejednoznaczności.
Brett Hale,
81

Zwróć uwagę, że operator% w C # i C ++ NIE jest w rzeczywistości modulo, jest resztą. Wzór na modulo, który chcesz w twoim przypadku, to:

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

Musisz to przekodować w C # (lub C ++), ale w ten sposób otrzymujesz modulo, a nie resztę.

Петър Петров
źródło
21
„Proszę zauważyć, że operator% w C ++ tak naprawdę NIE jest modulo, tylko resztą.” Dzięki, teraz ma to sens, zawsze zastanawiam się, dlaczego nigdy nie działał poprawnie z liczbami ujemnymi.
leetNightshade
2
„Proszę zauważyć, że operator% C ++ w rzeczywistości NIE jest modulo, jest resztą.” Nie sądzę, żeby to było dokładne i nie rozumiem, dlaczego modulo różni się od reszty. Tak też jest napisane na stronie Wikipedii Modulo Operation. Po prostu języki programowania inaczej traktują liczby ujemne. Operator modulo w C # oczywiście liczy resztę „od” zera (-9% 4 = -1, ponieważ 4 * -2 to -8 z różnicą -1), podczas gdy inna definicja traktuje -9% 4 jako +3, ponieważ -4 * 3 to -12, reszta +3 (np. W funkcji wyszukiwania Google, brak pewności co do języka zaplecza).
Tyress
18
Tyress, istnieje różnica między modułem a resztą. Na przykład: -21 mod 4 is 3 because -21 + 4 x 6 is 3. ale -21 divided by 4 gives -5z rozszerzeniem remainder of -1. W przypadku wartości dodatnich nie ma różnicy. Dlatego prosimy o zapoznanie się z tymi różnicami. I nie ufaj cały czas Wikipedii :)
Петър Петров
2
Dlaczego ktoś miałby chcieć użyć funkcji reszty zamiast modulo? Dlaczego zostawili %resztę?
Aaron Franke
4
@AaronFranke - to spuścizna z wcześniejszych procesorów cpus, która miała sprzęt do dzielenia, który szybko generował iloraz i resztę - i to właśnie ten sprzęt dał ujemną dywidendę. Język po prostu odzwierciedlał sprzęt. Przez większość czasu programiści pracowali z dodatnimi dywidendami i ignorowali to dziwactwo. Szybkość była najważniejsza.
ToolmakerSteve
17

Implementacja jednoliniowa przy użyciu %tylko jednego:

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }
Evgeni Sergeev
źródło
1
czy to jest poprawne? ponieważ nie uważam tego za zaakceptowane przez nikogo, ani żadnych komentarzy do niego. Na przykład. mod (-10,6) zwróci wartość 6. Czy to prawda? czy nie powinno zwrócić 4?
John Demetriou,
3
@JohnDemetriou Twoje liczby są błędne: (A) powinien zwrócić 2 i (B) zwraca 2; spróbuj uruchomić kod. Pozycja (A): aby znaleźć mod(-10, 6)ręcznie, dodajesz lub odejmujesz wielokrotnie 6, aż odpowiedź będzie w zakresie [0, 6). Ta notacja oznacza „włącznie po lewej stronie i wyłączność po prawej”. W naszym przypadku dodajemy 6 dwa razy, dając 2. Kod jest dość prosty i łatwo zauważyć, że ma rację: po pierwsze, robi to samo, co dodawanie / odejmowanie njak powyżej, z tą różnicą, że zatrzymuje się jeden nkrótki, jeśli zbliża się negatywna strona. W takim przypadku naprawiamy to. Tam: komentarze :)
Evgeni Sergeev
1
Nawiasem mówiąc, oto powód, dla którego użycie jednego %może być dobrym pomysłem. Zobacz tabelę Ile rzeczy kosztują w kodzie zarządzanym w artykule Pisanie szybszego kodu zarządzanego: poznaj koszty . Używanie %jest podobnie drogie jak int divwymienione w tabeli: około 36 razy droższe niż dodawanie lub odejmowanie i około 13 razy droższe niż mnożenie. Oczywiście nic wielkiego, chyba że jest to sedno tego, co robi twój kod.
Evgeni Sergeev
2
Ale czy pojedynczy %jest droższy niż test i skok, zwłaszcza jeśli nie można go łatwo przewidzieć?
Medinoc,
7

Odpowiedź ShreevatsaR nie będzie działać we wszystkich przypadkach, nawet jeśli dodasz „if (m <0) m = -m;”, jeśli uwzględnisz ujemne dywidendy / dzielniki.

Na przykład -12 mod -10 będzie równe 8, a powinno wynosić -2.

Następująca implementacja będzie działać zarówno dla dodatnich, jak i ujemnych dywidend / dzielników i jest zgodna z innymi implementacjami (mianowicie Java, Python, Ruby, Scala, Scheme, Javascript i Google's Calculator):

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;
    }
}

Zestaw testów przy użyciu 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
źródło
Po pierwsze, modfunkcja jest zwykle wywoływana z dodatnim modułem (zwróć uwagę na zmienną arrayLengthw pierwotnym pytaniu, na które tutaj udzielono odpowiedzi, która prawdopodobnie nigdy nie jest ujemna), więc tak naprawdę funkcja nie musi być zmuszana do pracy dla ujemnego modułu. (Dlatego wspominam o traktowaniu ujemnego modułu w komentarzu do mojej odpowiedzi, a nie w samej odpowiedzi.) (Cd.)
ShreevatsaR
3
(... cd.) Po drugie, to, co zrobić z ujemnym modułem, jest kwestią konwencji. Zobacz np . Wikipedia . „Zazwyczaj w teorii liczb dodatnia reszta jest zawsze wybierana” i tak też się tego nauczyłem (w elementarnej teorii liczb Burtona ). Knuth również definiuje to w ten sposób (a konkretnie r = a - b floor(a/b)zawsze jest pozytywne). Nawet wśród systemów komputerowych, na przykład Pascal i Maple, definiują to jako zawsze pozytywne.
ShreevatsaR
@ShreevatsaR Wiem, że definicja euklidesowa mówi, że wynik zawsze będzie dodatni - ale mam wrażenie, że większość nowoczesnych implementacji modów zwraca wartość z zakresu [n + 1, 0] dla ujemnego dzielnika „n”, co oznacza, że ​​-12 mod -10 = -2. Zajrzałem do Kalkulatora Google , Pythona , Ruby i Scali i wszystkie one przestrzegają tej konwencji.
dcastro,
Ponadto, aby dodać do listy: Schemat i Javascript
dcastro
1
Ponownie, to jest nadal warto przeczytać. Definicja „zawsze pozytywna” (moja odpowiedź) jest zgodna z ALGOL, Dart, Maple, Pascal, Z3 itd. „Znak dzielnika” (ta odpowiedź) jest zgodny z: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl itd. Oba są niezgodne ze „znakiem dywidendy”, jak w: AWK, bash, bc, C99, C ++ 11, C #, D, Eiffel, Erlang, Go, Java , OCaml, PHP, Rust, Scala, Swift, VB, x86, itd. Naprawdę nie rozumiem, jak można twierdzić, że jedna konwencja jest „poprawna”, a inne „niepoprawne”.
ShreevatsaR
5

Dodanie zrozumienia.

Zgodnie z definicją euklidesową wynik mod musi być zawsze dodatni.

Dawny:

 int n = 5;
 int x = -3;

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

Wynik:

 -1
Kosz
źródło
15
Jestem zdezorientowany ... mówisz, że wynik powinien zawsze być dodatni, ale potem wypisz wynik jako -1?
Jeff B
@JeffBridgman Stwierdziłem, że na podstawie definicji Euklidesa. `istnieją dwa możliwe wybory dla reszty, jeden negatywny, a drugi dodatni, a także dwa możliwe wybory dla ilorazu. Zwykle w teorii liczb, the positive remainder is always chosenale języki programowania wybierają w zależności od języka i znaków a i / lub n. [5] Standardowy Pascal i Algol68 dają dodatnią resztę (lub 0) nawet dla ujemnych dzielników, a niektóre języki programowania, takie jak C90, pozostawiają to implementacji, gdy jedno z n lub a jest ujemne. "
Abin
5

Porównanie dwóch dominujących odpowiedzi

(x%m + m)%m;

i

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

Nikt właściwie nie wspomniał o tym, że pierwszy może OverflowExceptionchwilę rzucić , drugi nie. Co gorsza, przy domyślnym niezaznaczonym kontekście, pierwsza odpowiedź może zwrócić błędną odpowiedź (patrz mod(int.MaxValue - 1, int.MaxValue)na przykład). Zatem druga odpowiedź wydaje się nie tylko szybsza, ale także bardziej poprawna.

lilo0
źródło
4

Po prostu dodaj swój moduł (arrayLength) do ujemnego wyniku% i wszystko będzie dobrze.

starblue
źródło
4

Dla programistów bardziej świadomych wydajności

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

Małe porównanie wydajności

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

Jeśli chodzi o koszt wykonania rzutów do uint, zajrzyj tutaj

Markus Cozowicz
źródło
3
Wydaje mi się, że -3 % 10powinno to być -3 lub 7. Ponieważ pożądany jest wynik nieujemny, odpowiedzią będzie 7. Twoja implementacja zwraca 3. Powinieneś zmienić oba parametry na uinti usunąć rzutowanie.
Podobał mi się stary Stack Overflow z
5
Arytmetyka bez znaku jest równoważna tylko wtedy, gdy njest potęgą dwójki, w takim przypadku możesz po prostu użyć logicznego i ( (uint)k & (n - 1)) zamiast tego, jeśli kompilator jeszcze tego nie zrobi (kompilatory są często wystarczająco sprytne, aby to rozgryźć).
j_schultz,
2

Podoba mi się sztuczka przedstawiona przez Petera N Lewisa w tym wątku : „Jeśli n ma ograniczony zakres, możesz uzyskać pożądany wynik, po prostu dodając znaną stałą wielokrotność [dzielnika], która jest większa niż wartość bezwzględna minimum."

Więc jeśli mam wartość d, która jest w stopniach i chcę wziąć

d % 180f

i chcę uniknąć problemów, jeśli d jest ujemne, zamiast tego po prostu robię to:

(d + 720f) % 180f

Zakłada się, że chociaż d może być ujemne, wiadomo, że nigdy nie będzie bardziej ujemne niż -720.

RenniePet
źródło
2
-1: niewystarczająco ogólne (i bardzo łatwo jest podać bardziej ogólne rozwiązanie).
Evgeni Sergeev
4
To jest naprawdę bardzo pomocne. jeśli masz znaczący zakres, może to uprościć obliczenia. w moim przypadku math.stackexchange.com/questions/2279751/…
M.kazem Akhgary
Dokładnie, po prostu użyłem tego do obliczenia dayOfWeek (znany zakres od -6 do +6) i zaoszczędziłem mając dwa %.
NetMage,
@EvgeniSergeev +0 dla mnie: nie odpowiada na pytanie OP, ale może być pomocny w bardziej konkretnym kontekście (ale nadal w kontekście pytania)
Erdal G.
1

Oczekujesz zachowania, które jest sprzeczne z udokumentowanym zachowaniem operatora% w języku c # - prawdopodobnie dlatego, że spodziewasz się, że będzie działać w sposób, w jaki działa w innym języku, do którego jesteś bardziej przyzwyczajony. Dokumentacja na C # stanach (podkreślenie moje):

W przypadku argumentów typu całkowitego wynik a% b jest wartością uzyskaną przez a - (a / b) * b. Znak niezerowej reszty jest taki sam, jak w przypadku operandu po lewej stronie

Żądaną wartość można obliczyć za pomocą jednego dodatkowego kroku:

int GetArrayIndex(int i, int arrayLength){
    int mod = i % arrayLength;
    return (mod>=0) : mod ? mod + arrayLength;
}
Andrzej
źródło
1

Jednowierszowa implementacja odpowiedzi dcastro (najbardziej zgodna z innymi językami):

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

Jeśli chcesz zachować użycie %operatora (nie możesz przeciążać operatorów natywnych w 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);
}

Przypadek użycia, oba działa:

int r = (IntM)a % n;

// Or
int r = a % n(IntM);
Erdal G.
źródło
0

Wszystkie odpowiedzi tutaj działają świetnie, jeśli dzielnik jest dodatni, ale nie jest kompletny. Oto moja implementacja, która zawsze zwraca zakres [0, b), tak że znak wyjścia jest taki sam jak znak dzielnika, uwzględniając ujemne dzielniki jako punkt końcowy zakresu wyjściowego.

PosMod(5, 3)zwraca 2
PosMod(-5, 3)zwraca 1
PosMod(5, -3)zwraca -1
PosMod(-5, -3)zwraca zwraca-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;
    }

(gdzie real_tmoże być dowolna liczba)

Aaron Franke
źródło