Welche Gründe werden verwendet, wenn Programmiersprachenentwickler entscheiden, welches Vorzeichen das Ergebnis der Modulo-Operation hat?

9

Beim Durchlaufen der Modulo-Operation (der Straße, die ich betreten habe, als ich den Unterschied zwischen remundmod erkundet habe ) bin ich auf Folgendes gestoßen:

In der Mathematik ist das Ergebnis der Modulo-Operation der Rest der euklidischen Division. Andere Konventionen sind jedoch möglich. Computer und Taschenrechner haben verschiedene Möglichkeiten, Zahlen zu speichern und darzustellen. Daher hängt ihre Definition der Modulo-Operation von der Programmiersprache und / oder der zugrunde liegenden Hardware ab.

Fragen:

  • Als ich die euklidische Division durchlief, stellte ich fest, dass der Rest dieser Operation immer positiv (oder 0) ist. Welche Einschränkung der zugrunde liegenden Computerhardware zwingt Programmiersprachenentwickler dazu, sich von der Mathematik zu unterscheiden?
  • Jede Programmiersprache hat eine vordefinierte oder undefinierte Regel, nach der das Ergebnis der Modulo-Operation sein Vorzeichen erhält. Welche Gründe werden bei der Festlegung dieser Regeln verwendet? Und wenn die zugrunde liegende Hardware das Problem ist, sollten sich die Regeln dann nicht unabhängig von der Programmiersprache entsprechend ändern?
Blutende Finger
quelle
1
In meinem Code brauche ich fast immer Modulo, nicht den Rest. Keine Ahnung, warum der Rest so beliebt ist.
CodesInChaos
8
Verwandte Was ist der Unterschied? Rest gegen Modul - Eric Lipperts Blog (von einem der C # -Designer, aber ich glaube, er ist dem Team beigetreten, nachdem diese Entscheidung getroffen wurde)
CodesInChaos
1
Wenn Sie den Wikipedia-Artikel weiter lesen (über den von Ihnen zitierten Teil hinaus), wird erklärt, was Sie ziemlich gut zitiert haben. Was ist mit dieser Erklärung, über die Sie verwirrt sind?
Robert Harvey
1
Eine verwandte Frage ist, welche dieser Operationen direkt CPU-Anweisungen zugeordnet sind. In c ist die Implementierung definiert, die zur c-Philosophie passt, auf so vielen Plattformen wie möglich direkt auf die Hardware abzubilden. Es werden also keine Dinge angegeben, die sich zwischen den CPUs unterscheiden könnten.
CodesInChaos
5
@BleedingFingers Bei der Programmierung wird häufig eine Ganzzahldivision verwendet, die gegen Null geht, z (-3)/2 == -1. Diese Definition kann nützlich sein. Wenn Sie %mit dieser Teilung übereinstimmen möchten , erhalten x == (x/y)*y + x % ySie die Definition von %in C # verwendet.
CodesInChaos

Antworten:

6

Die Hardware aller modernen Computer ist ausreichend leistungsfähig, um Mod-Operationen mit beiden Vorzeichen ohne (oder mit geringfügigen) Auswirkungen auf die Leistung zu implementieren. Dies ist nicht der Grund.

Die meisten Computersprachen erwarten häufig, dass (a div b) * b + (a mod b) = a. Mit anderen Worten, div und mod, die zusammen betrachtet werden, teilen eine Zahl in Teile, die zuverlässig wieder zusammengesetzt werden können. Diese Anforderung ist im C ++ - Standard explizit. Das Konzept ist eng mit der Indizierung mehrdimensionaler Arrays verbunden. Ich habe es oft benutzt.

Daraus ist ersichtlich, dass div und mod das Vorzeichen von a beibehalten, wenn b positiv ist (wie es normalerweise ist).

Einige Sprachen bieten eine 'rem ()' - Funktion, die sich auf mod bezieht und eine andere mathematische Begründung hat. Ich musste das nie benutzen. Siehe zum Beispiel frem () in Gnu C. [bearbeitet]

david.pfx
quelle
Ich denke, das rem(a,b)ist eher so, mod(a,b)wenn es positiv ist oder mod(a,b) + bnicht.
user40989
3
(a div b) * b + (a mod b) = a- das so sehr. In der Tat, im Gegensatz zu , wie beschreibt Wikipedia es zu negativen Zahlen in der euklidischen Teilung erstreckt (insbesondere „Der Rest ist das einzige der vier Zahlen , die nie negativ sein können.“) Verwirrt mich , weil ich immer , dass der Rest gelehrt kann negativ sein in jeder Matheklasse auf diesem Niveau.
Izkata
@ user40989: Ich sagte, ich hätte es nie benutzt. Siehe bearbeiten!
david.pfx
4

Für die Programmierung, die Sie normalerweise wünschen X == (X/n)*n + X%n; Daher hängt die Definition von Modulo davon ab, wie die Ganzzahldivision definiert wurde.

Vor diesem Hintergrund fragen Sie sich wirklich: " Welche Gründe werden verwendet, wenn Designer von Programmiersprachen entscheiden, wie die Ganzzahldivision funktioniert? "

Es gibt tatsächlich ungefähr 7 Möglichkeiten:

  • rund bis negativ unendlich
  • rund bis positiv unendlich
  • auf Null runden
  • mehrere Versionen von "auf den nächsten runden" (mit Unterschieden in der Rundung von 0,5)

Nun überlegen Sie -( (-X) / n) == X/n. Ich möchte, dass dies wahr ist, da alles andere inkonsistent (es gilt für Gleitkomma) und unlogisch (eine wahrscheinliche Ursache für Fehler und auch eine möglicherweise übersehene Optimierung) erscheint. Dies macht die ersten beiden Auswahlmöglichkeiten für die Ganzzahldivision (Rundung auf eine Unendlichkeit) unerwünscht.

Alle "Rund um die nächste" Auswahlmöglichkeiten sind ein Problem für die Programmierung, insbesondere wenn Sie so etwas wie Bitmaps (z offset = index / 8; bitNumber = index%8;. B. ) ausführen .

Damit bleibt die Rundung gegen Null als "potenziell vernünftigste" Wahl, was impliziert, dass Modulo einen Wert mit dem gleichen Vorzeichen wie der Zähler (oder Null) zurückgibt.

Hinweis: Sie werden auch feststellen, dass die meisten CPUs (alle mir bekannten CPUs) die Ganzzahldivision auf dieselbe Weise "auf Null runden" durchführen. Dies ist wahrscheinlich aus den gleichen Gründen.

Brendan
quelle
Das Abschneiden der Teilung hat aber auch seine eigenen Inkonsistenzen: Es bricht (a+b*c)/b == a % bund a >> n == a / 2 ** n, für die die Teilung auf dem Boden ein vernünftiges Verhalten aufweist.
Dan04
Ihr erstes Beispiel macht keinen Sinn. Ihr zweites Beispiel ist ein Chaos für Programmierer: Für positives a und positives n ist es konsistent, für negatives a und positives n hängt es davon ab, wie die Verschiebung nach rechts definiert ist (arithmetisch vs. logisch), und für negatives n ist es gebrochen (z 1 >> -2 == a / 2 ** (-2). B. ).
Brendan
Das erste Beispiel war ein Tippfehler: Ich meinte (a + b * c) % b == a % b, der %Operator ist in der Dividende divisor-periodisch, was oft wichtig ist. Wenn Sie beispielsweise eine Bodenteilung verwenden, erhalten day_count % 7Sie den Wochentag. Bei einer abgeschnittenen Teilung wird dies jedoch für Daten vor der Epoche unterbrochen.
Dan04
0

Zuerst wiederhole ich, dass ein Modulo b gleich a - b * (a div b) sein sollte, und wenn eine Sprache dies nicht bietet, befinden Sie sich in einem schrecklichen mathematischen Durcheinander. Dieser Ausdruck a - b * (a div b) gibt tatsächlich an, wie viele Implementierungen ein Modulo b berechnen.

Es gibt einige mögliche Gründe. Das erste ist, dass Sie maximale Geschwindigkeit wollen, also wird ein div b als das definiert, was der verwendete Prozessor bereitstellt. Wenn Ihr Prozessor einen "div" -Befehl hat, ist ein div b das, was dieser div-Befehl tut (solange es etwas ist, das nicht völlig verrückt ist).

Das zweite ist, dass Sie ein bestimmtes mathematisches Verhalten wünschen. Nehmen wir zunächst b> 0 an. Es ist durchaus sinnvoll, dass das Ergebnis eines div b gegen Null gerundet wird. Also 4 Div 5 = 0, 9 Div 5 = 1, -4 Div 5 = -0 = 0, -9 Div 5 = -1. Dies ergibt (-a) div b = - (a div b) und (-a) modulo b = - (a modulo b).

Das ist ziemlich vernünftig, aber nicht perfekt; Zum Beispiel (a + b) div b = (a div b) + 1 gilt nicht, sagen wir, wenn a = -1. Mit einem festen b> 0 gibt es normalerweise (b) mögliche Werte für a, so dass ein div b das gleiche Ergebnis liefert, außer dass es 2b - 1 Werte a von -b + 1 bis b-1 gibt, wobei ein div b gleich 0 ist Es bedeutet auch, dass ein Modulo b negativ ist, wenn a negativ ist. Wir möchten, dass ein Modulo b immer eine Zahl im Bereich von 0 bis b-1 ist.

Andererseits ist es auch durchaus sinnvoll zu verlangen, dass ein Modulo b beim Durchlaufen aufeinanderfolgender Werte von a die Werte von 0 bis b-1 durchläuft und dann erneut mit 0 beginnt. Und um zu fordern, dass (a + b) div b (a div b) + 1 sein soll. Um dies zu erreichen, möchten Sie, dass das Ergebnis eines div b auf -infinity gerundet wird, also -1 div b = -1. Auch hier gibt es Nachteile. (-a) div b = - (a div b) gilt nicht. Durch wiederholtes Teilen durch zwei oder durch eine beliebige Zahl b> 1 erhalten Sie schließlich kein Ergebnis von 0.

Da es Konflikte gibt, müssen die Sprachen entscheiden, welche Vorteile für sie wichtiger sind, und entsprechend entscheiden.

Für das negative b können sich die meisten Menschen nicht vorstellen, was ein div b und ein modulo b überhaupt sein sollten. Eine einfache Möglichkeit besteht darin, zu definieren, dass ein div b = (-a) div (-b) und a modulo b = (-a) modulo (-b) wenn b <0 ist oder was auch immer das natürliche Ergebnis der Verwendung des Codes für positives b ist.

gnasher729
quelle