Forum: Digitale Signalverarbeitung / DSP / Machine Learning Integer Division mit Rest


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Günther A. D. Hauptmann (Gast)


Lesenswert?

Wertes Forum,

welche der beiden Divisionsmethoden in Table 3.3 und 3.4 würdet ihr
erstens als Mathematiker und zweitens als Informatiker bevorzugen 
und warum?
1
Table 3.3 - Floored Division Example [1]
2
3
Dividend        Divisor Remainder       Quotient
4
--------        ------- ---------       --------
5
10                 7       3                1
6
-10                7       4               -2
7
10                -7      -4               -2
8
-10               -7      -3                1
9
10
Table 3.4 - Symmetric Division Example [1]
11
12
Dividend        Divisor Remainder       Quotient
13
--------        ------- ---------       --------
14
10                 7       3                1
15
-10                7      -3               -1
16
10                -7       3               -1
17
-10               -7      -3                1
[1] http://forth.sourceforge.net/standard/dpans/dpans3.htm#3.2.2.1

: Verschoben durch Moderator
von Walter K. (walter_k488)


Lesenswert?

Oh, schön - ein Forth Interessierter!

von Nikolaus S. (Firma: Golden Delicious Computers) (hns)


Lesenswert?

Das kommt darauf an...

Weil: "bevorzugen" heisst sich zwischen 2 Varianten zu entscheiden. 
Dafür braucht es ein Entscheidungskriterium. Welches?

Hier ein paar mögliche:
Was der Anwender braucht? Konvention? Norm? Verfügbarkeit im Prozessor? 
Gefällt mir besser? scheint mir "logischer"? Luftdruck? Hutgröße?

Vor allem ab "Gefällt mir besser" muß man einen Psychologen fragen :)

Für den Mathematiker sind also beide völlig ok. Es ist einfach ein Axiom 
in einem Beweisgebäude. Und der Informatiker denkt, dass es zwei 
verschiedene Konventionen gibt die beide ihre Berechtigung haben.

: Bearbeitet durch User
von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Das ist dem Elektrotechniker egal, denn der Rest, der ausgerechnet wird, 
wird entweder:

- ignoriert, womit es egal ist
- korrekt interpretiert, womit der Fehler im Bereich +/- 0.5 ist und 
sich alle Ergebnisse gleichen
- weiterberechnet, womit sich der Fehler in die nächste Stufe weiter 
fortpflanzt und entsprechend limitiert

von Lerninstructor (Gast)


Lesenswert?

Der Fehler liegt hier eine Entscheidung erzwingen zu weil, weil es hier 
kein richtig oder falsch gibt. Auch ist es keine Frage nach der 
Divisionsmethode, sondern nach Berechnung der Restklasse (modulo) oder 
des Restes (remainder). Deshalb gibt es ja beide Verfahren zur Auswahl: 
mod() oder rem().

https://de.wikipedia.org/wiki/Division_mit_Rest#Implementierung_in_Computersystemen

Aber das wurde hier doch schon oft genug durchgekaut:

Beitrag "VHDL - Unterschied REM & MOD ?"
Beitrag "Modulofunktion"
Beitrag "Wieso ist -1 mod 26 = 25 ?"

von Yalu X. (yalu) (Moderator)


Angehängte Dateien:

Lesenswert?

Ich persönlich bevorzuge die floored Division (im folgenden "div"
genannt) gegenüber der symmetric Division (im folgenden "quot" genannt).
Eng verbunden mit der Integer-Division ist die Modulo-Funktion. Die zu
div gehörende Funktion sei "mod" und die zu quot gehörende "rem"
genannt.

Im angehängten Diagramm sind div und mod grün, und quot und rem rot
dargestellt.

Gründe für meiner Präferenz von div und mod:

- Bei gegebenem Divisor haben quot und rem um 0 herum einen
  unregelmäßigen Verlauf, was vor allem bei der Programmierung stört.

- Das erschwert u.a. auch die zum nächsten Nachbarn gerundete Division.
  Die gerundete Division durch durch 6 kann man bspw. so schreiben:

  x / 6 = div(x + 3, 6)

  Das funktioniert für positive und negative x. Ersetzt man div durch
  quot, stimmt das Ergebnis für negative x nicht mehr, d.h. man braucht
  hier eine Fallunterscheidung.

- Aus mathematischer Sicht ermittelt x modulo y eine Restklasse und
  liefert als Ergebnis einen Repräsentanten dieser Klasse. Welcher der
  unendlich vielen möglichen Repräsentanten der geeignetste ist, ist
  diskutabel. Was aber IMHO sehr schlecht ist, wenn bei gleicher
  Restklasse nicht immer der gleiche Repräsentant ausgewählt wird.

  Beispiel:

  Die zu 7 modulo 3 und -5 modulo 3 gehörenden Restklassen sind beide
  gleich, nämlich {..., -8, -5, -2, 1, 4, 7, 10, ...}. Dennoch sind
  rem(7,3) = 1 und rem(-5,3) = -2 verschieden. Auf der anderen Seite ist
  mod(7,3) = mod(-5,3) = 1, wie es sein sollte.

Andersherum habe ich noch keinen Fall erlebt, wo quot und rem einen
programmiertechnischen Vorteil gegenüber div und mod gehabt hätten.
Deswegen schränke ich für mich die Verwendung dieser Operatoren wie
folgt ein:

1. Stehen nur quot und rem zur Verfügung (wie bspw. in C und C++),
   verwende ich nur nichtnegative Operanden.

2. Stehen nur div und mod zur Verfügung (wie bspw. in Python), verwende
   auch negative Dividenden. Beim Divisor beschränke ich mich dennoch
   auf nichtnegative, weil ich negative noch nie gebraucht habe, und
   diese zudem etwas verwirrend finde.

3. Stehen sowohl quot und rem als auch div und mod zur Verfügung (wie
   bspw. in Haskell), beschränke ich mich auf div und mod und verwende
   diese wie in (2).

von Günther A. D. Hauptmann (Gast)


Lesenswert?

Vielen Dank für die Antworten. Unter was muss ich denn danach im 
Bronstein suchen?

von Zahlenmax - Digitax (Gast)


Lesenswert?

Günther A. D. Hauptmann schrieb:
> Vielen Dank für die Antworten. Unter was muss ich denn danach im
> Bronstein suchen?

Bronstein ist tot, Teubner lebt! ;-) ISBN: 978-3519200123

Aber in beiden Fällen ist so ein Tabellen-/Formelbuch der 'klassischen 
mathematik' eher wenig hilfreich. Du solltest eher in Richtung Numerik 
suchen (bspw.  ISBN:978-3446005808) oder in aus dem Fachgebiet in dem du 
die Integer Division einsetzen willst (Crypto? -> Zahlentheorie)

von Klaus W. (mfgkw)


Lesenswert?

Weder Bronstein noch Teubner werden dir sagen können, was du eigentlich 
willst.
Ich zumindest habe das bisher nicht wirklich gesehen.

von Der Heini (Gast)


Lesenswert?

Sagt er doch: Er will unsere Meinung wissen und das Einsatzgebiet 
kennenlernen. Gfs möchte er was lernen, was er noch nicht weis, was ja 
eine so schlechte Einstellung nicht ist.

Mein Senf:

Yalu X. schrieb:
> Ich persönlich bevorzuge die floored
Das erzeugt bei symmetrischem Datenmaterial aber eine Asymmetrie und 
damit einen falschen Offset.

von Zahlenmax - Digitax (Gast)


Lesenswert?

Der Heini schrieb:
> Gfs möchte er was lernen, was er noch nicht weis, was ja
> eine so schlechte Einstellung nicht ist.

Für Ingenieure ist eine solche Einstellung grundfalsch.
Auch Lernen ist eine Werkzeug. Und Werkzeuge benutzt man 
ziel-/zweckgerichtet. (anders als Spielzeuge, damit verplembert man 
seine Lebenszeit mit der kindlichen Hoffnung auf unerwarteten 
Erkenntnisgewinn).
Dagegen als Student oder Wissenschaftler kann man ungerichtet Wissen in 
sich hineinschaufeln, als Ingenieure schult man sich seine Wissenslücken 
zielgerichtet weg.

Also wenn der TO nicht benennen kann, warum er sich mit den scheinbaren 
Widerspruch zwischen mod() und rem() soll er sein lassen und sich 
lediglich eine mentale Notiz dazu machen.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Der Heini schrieb:
> Yalu X. schrieb:
>> Ich persönlich bevorzuge die floored
> Das erzeugt bei symmetrischem Datenmaterial aber eine Asymmetrie und
> damit einen falschen Offset.

Mit "symmetrischem Datenmaterial" meinst du wahrscheinlich, dass von den
Divisionsergebnissen die Hälfte negativ und die Hälfte positiv ist. Dann
ist der mittlere Offset bei der symmetrischen Division 0. Sobald es aber
mehr positive als negative Werte gibt (oder umgekehrt), wird der
mittlere Offet größer (bzw. kleiner) als null.

Bei der floored Division hingegen ist der mittlere Offset unabhängig vom
Vorzeichen der Divisionsergebnisse immer -0,5. Er kann deswegen einfach
durch Addition von +0,5 zu jedem Divisionsergebnis kompensiert werden.
Das funktioniert auch problemlos bei asymmetrischem Datenmaterial.

von Günther A. D. Hauptmann (Gast)


Lesenswert?

Besten Dank für die Buchtipps.

Das ganze Thema ist mir dank Eurer Antworten klarer geworden, wo es doch 
sehr verworren ist. Etwa, dass in C % Modulo genannt wird und Remainder 
gemacht wird. Vorher sah ich nur, dass |a|/|b|=|a/b| nur bei Quot 
gegeben ist, nicht jedoch bei Div.

PS: Falls mal jemand fragt ob er of Science oder of Engineering 
studieren soll, Zahlenmax' zweiter Post könnte hilfreich sein.

von Zahlenmax - Digitax (Gast)


Lesenswert?

Günther A. D. Hauptmann schrieb:
> PS: Falls mal jemand fragt ob er of Science oder of Engineering
> studieren soll,

Naja science ist die Grundlage von Engineering, so ganz entwerder oder 
geht nicht. Und manchmal heisst es Science ist aber reines Engineering 
bspw. "Computer Science" aka Informatik.

von Videospezi (Gast)


Lesenswert?

Yalu X. schrieb:
> 1. Stehen nur quot und rem zur Verfügung (wie bspw. in C und C++),
>    verwende ich nur nichtnegative Operanden.
>
> 2. Stehen nur div und mod zur Verfügung (wie bspw. in Python), verwende
>    auch negative Dividenden. Beim Divisor beschränke ich mich dennoch
>    auf nichtnegative, weil ich negative noch nie gebraucht habe, und
>    diese zudem etwas verwirrend finde.
>
> 3. Stehen sowohl quot und rem als auch div und mod zur Verfügung (wie
>    bspw. in Haskell), beschränke ich mich auf div und mod und verwende
>    diese wie in (2).

Das könnte man mal einrahmen oder in die Artikelsammlung übernehmen!

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.