no way to compare when less than two revisions

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

@@ Zeile 1: / Zeile 1: @@
+====== Ganzzahl : Schriftliches Rechnen ======
+> Was gibt siebenmal sieben?
+> Feinen Sand.
+>> ---  Kinderspruch
+===== Algorithmen für das schriftliche Rechnen =====
+Wie ging das nochmal, das schriftliche Rechnen?
+Nahezu jeder hat es in den ersten vier Schuljahren erlernt.
+Mancher hat es danach wieder vergessen. Zumal es dafür Maschinen gibt.
+Bevor wir in Details gehen, ein "religiöser" Einschub.
+Warum sollte ich das noch wissen? Ich habe doch einen Taschenrechner.
+Diese Haltung ist gefährlich.
+Was machen wir, wenn uns kein Taschenrechner zur Verfügung steht?
+Eine erschreckend große Zahl derer, die einen Taschenrechner benutzen,
+können damit nicht umgehen.
+Das Ergebnis wird kritiklos übernommen, schließlich macht die Maschine keinen (offensichtlichen) Fehler.
+Eben da liegt das Problem.
+Zahlen können verkehrt eingegeben werden,
+die Operationen können in falscher Reihenfolge ausgeführt worden sein.
+Warum sollte das Ergebnis korrekt sein, wenn das verwendete Rechenverfahren instabil ist?
+Wieviele der Stellen im Ergebnis sind sinnvoll?
+Technik hat eine Kehrseite.
+Menschliche Fertigkeiten verkümmern, sobald sie nicht mehr genutzt werden.
+Das kleine Einmaleins wird von Schulabgängern nicht beherrscht,
+zweistellige, ja sogar einstellige Zahlen werden nicht mehr korrekt im Kopf addiert.
+Der Griff zum Taschenrechner ist Reflex.
+Größenvorstellungen sind nicht mehr vorhanden.
+Wenn ich zwei dreistellige Zahlen multipliziere,
+wieviele Stellen wird das Ergebnis haben?
+Mit einer überschlägigen Schätzung kann man erkennen,
+ob ein Resultat voll daneben liegt.
+Beim Umgang mit Rechenschiebern war der Überschlag unerlässlich,
+bei Taschenrechnernutzung unterbleibt er zumeist.
+Solche Fragen spielen wieder eine Rolle, wenn es z.B. darum geht,
+wieviel Speicher für das Ergebnis zu reservieren ist,
+bevor die Rechnung beginnen kann.
+Soweit zur Bedeutung der Religion.
+Die Beschreibungen der Grundrechenarten beginnen stets mit der Angabe der
+Stellenzahl der Eingabewerte und der maximalen Stellenzahl im Ergebnis.
+Das Feld ''a[n]'' enthält die Ziffern a[0] bis a[n-1] der Zahl.
+Der Index ''i'' = 0...n-1 gibt den Stellenwert ''pow(10,i)'' der Ziffer an.
+Um es unmissverständlich auszudrücken:
+die immer vorhandene "Einerstelle" liegt in ''a[0]'', die "Zehner" in ''a[1]'' usw.
+Die Nummerierung der Stellen erfolgt also in arabischer Schreibrichtung, von rechts nach links.
+Die Algorithmen beschränken sich auf natürliche,
+d.h. nicht negative Zahlen.
+Die [[#Vorzeichenregeln]]
+sind leicht zu ergänzen.
+Nicht nur zur Erbauung vorangestellt sind hier Zitate aus Adam Rieses
+"Rechnung auff der Linihen und Federn" aus dem Jahr MDXXXII
+[114. Auflage. Magistrat der Stadt Erfurt, 1991].
+Das Rechnen "auff der Linihen" (mit dem Abakus) ist
+mit dem Abzug der sowjetischen Truppen 1991
+wohl endgültig aus unserem Blickfeld verschwunden.
+"Volgen die species auff der feddern. ..."
+===== Addieren =====
+<file>
+ Addirn.\\
+ Lert viel zaln ynn eine summa zu bringen / thu yhm also /
+ setz die selbigen zaln / welche du sumirn wilt untereinander /
+ die ersten unter die ersten / die ander unter die ander / also hinfurt /
+ darnach heb zu fodderst an gen der rechten hand /
+ summir zu sammen die ersten figurn /
+ kömet eine zal die du mit einer figur schreiben magst / so setz sie gleich dar unter /
+ entspringt aber ein mit zweien figurn so schreib die erst gleich darunter / die ander behalt /
+ darnach summir zusammen die andern figurn / gib darzu das du behalten /
+ und schreib abermals die erst figur / wo zwo vorhanden /
+ und thu des gleichen hinfurt mit allen figurn /
+ bis auff die letzte / die schreib gantz aus /
+ so hastu wie viel ynn einer summa komet / als volgende exempel ausweisen.</file>
+Algorithmus addieren(a, b)
+>  Parameter: a[m], b[n]
+>  Ergebnis: summe[ 1+max(m,n) ]\\
+>  übertrag = 0
+>  für i = 0 ... max(m,n)-1
+>>  wenn i < m dann übertrag um a[i] erhöhen
+>>  wenn i < n dann übertrag um b[i] erhöhen
+>>  summe[i] = übertrag mod BASIS
+>>  übertrag durch BASIS teilen
+>  summe[ max(m,n) ] = übertrag
+<code cpp>
+  +  9208
+  1    <- Übertrag
+  -------
+  =======
+</code>
+Folgende Verbesserungen sind möglich:
+  * Das Summe wird nur bei einem Übertrag ganz vorn länger als die Summanden.
+  * Die Felder summe und a können identisch sein (m >= n, Speichervergrößerung nur bei Bedarf).
+  * Überflüssige Tests sind vermeidbar (Laufzeitverbesserung auf Kosten der Lesbarkeit).
+  * Für i > n ist summe[i] = a[i], sobald keine Überträge mehr stattfinden.
+===== Subtrahieren =====
+<file>
+ Subtrahirn.\\
+ Lernt wie du eine zal von der andern nemen solt /
+ thu yhm also setz oben die zal da von du neme wilt
+ und die du abnemen wilt gleich darunder wie yhm summirn /
+ darnach mach ein linihen darunder /
+ und heb zu foderst an wie yhm addirn /
+ nim die erste der untersten zal von der ersten figur der obersten zal
+ was dann bleibt setz unden /
+ darnach nim die ander figur der undern zal /
+ von der andern der obersten zal /
+ das bleibet setz auch unden /
+ Magstu aber die under figur von der obern nicht nemen /
+ so nimm sie von zehen / zum bleibenden /
+ gib die ober un' setz gleich under die linihen / was do komet /
+ darnach addir eins der nehisten undern figur gegen der lincken hand /
+ und subtrahir fort bis zum end /
+ wie hie folgt.</file>
+Algorithmus subtrahieren(a, b)
+>  Parameter: a[m], b[n]
+>  Ergebnis: differenz[m]
+>  Vorbedingung: a >= b und damit m >= n\\
+>  übertrag = 1
+>  für i = 0 ... m-1
+>>  übertrag um BASIS-1 erhöhen
+>>  übertrag um a[i] erhöhen
+>>  wenn i < n dann übertrag um b[i] vermindern
+>>  differenz[i] = übertrag mod BASIS
+>>  übertrag durch BASIS teilen
+>  Nachbedingung: übertrag = 1, sonst war a < b!
+<code cpp>
+
+  -123456
+  1    <- Übertrag (geborgt)
+  -------
+  =======
+</code>
+Der dargestellte Algorithmus weicht insofern vom schriftlichen Verfahren ab,
+dass er ständig mit einem "geborgten Zehner" arbeitet.
+Negative Werte treten damit nicht auf,
+die Rechnung kann dadurch mit vorzeichenlosen Zahlen erfolgen.
+Wie man sieht, kann das Ergebnis auch wesentlich kürzer als der Minuend a sein.
+Führende Nullen kann man weglassen. Nicht immer überblickt man das sofort...
+Die Differenz kann am Ort des Minuenden entstehen.
+Bei i > n braucht nur solange weitergerechnet werden, wie geborgt wurde.
+Die davor stehenden Ziffern bleiben erhalten.
+===== Multiplizieren =====
+==== einstellig ====
+<file>
+ Multiplicirn.\\
+ Lernt viel machen /
+ must auch forn anheben /
+ und fur allen dingen das ein mal ein auswendig lernen /
+ wie furhin angezeigt.\\
+ Wiltu nun ein zal mit einer figur Multiplicirn
+ so schreib die zal oben /
+ die du multplicirn wilt /
+ und die figur damit du multiplicirn wilt /
+ gleich under die erste figur /
+ Als dann multiplicir sie mit der ersten /
+ kömet ein zahl mit einer figur /
+ so setz sie unden wo mit zweyen / so schreib die erst /
+ die ander behalt als dann multiplicir die unter figur mit der ander der obern zal /
+ un gib darzu das du behalten hast /
+ schreib abermals die erste /
+ also hinfurt / und zum letzten schreib es gantz aus / wie hie.</file>
+Algorithmus einstellig_multiplizieren(a, ziffer)
+>  Parameter: a[m], ziffer
+>  Ergebnis: produkt[m+1]\\
+>  übertrag = 0
+>  für i = 0 ... m-1
+>>  übertrag um a[i]*ziffer erhöhen
+>>  produkt[i] = übertrag mod BASIS
+>>  übertrag durch BASIS teilen
+>  produkt[m] = übertrag
+<code cpp>
+* 6
+  --------
+     <-- Übertrag
+  ========
+</code>
+Einstelliges Multiplizieren kann am Ort, innerhalb eines Feldes geschehen,
+d.h. die Ziffern des Ergebnisses überschreiben den Platz der Ziffern a[i].
+==== mehrstellig ====
+<file>
+ Durch zwo figurn.\\
+ Wiltu eine zal mit zweyen figurn Multiplicirn
+ so fure die erste figur durch / wie itzt gesagt /
+ als dann die ander auch gleichförmig /
+ und setz das selbige ein figur hinein bis gen der lincken hand /
+ als dann summir zusammen wie hie.\\
+ \\
+ Durch drey figurn.\\
+ Des gleichen multiplicir auch durch .3. odder mehr figurn
+ allein setz solchs ein figur hinein bas / wie hie folget.</file>
+Algorithmus multiplizieren(a, b)
+>  Parameter: a[m], b[n]
+>  Ergebnis: produkt[m+n]\\
+>  für k = 0 bis m+n-1
+>>  produkt[k] = 0
+>  für j = 0 ... n-1
+>>  übertrag = 0
+>>  für i = 0 ... m-1
+>>>  übertrag um produkt[i+j] + a[i]*b[j] erhöhen
+>>>  produkt[i+j] = übertrag mod BASIS
+>>>  übertrag durch BASIS teilen
+>>  produkt[m+j] = übertrag
+<code cpp>
+* 234
+  ----------
+  ----------
+     1634958
+  ==========
+</code>
+Mehrstelliges Multiplizieren geschieht wie von Hand,
+jedoch werden die Zwischenprodukte sofort aufsummiert.
+Dazu werden am Anfang alle Ziffern des Produktes auf 0 gesetzt.
+Das Produkt z.B. zweier zweistelliger Zahlen ist höchstens vierstellig:
+*99 = 9801.
+Es kann vorkommen, dass die führende Ziffer 0 bleibt,
+z.B. bei 10*10 = 0100. In diesem Fall ist diese zu streichen.
+===== Dividieren =====
+==== einstellig ====
+<file>
+ Dividirn.\\
+ Lernt ein zal inn die andern teiln /
+ hinden soltu anheben schreib die zal fur dich /
+ welche du teylen wilt unter die letzte figur den teiler
+ so du anderst inn ein figur teilest / und genemen magst.
+ Ist aber der teyler grösser /
+ so schreib ihn unter die letzte figur an eine und besihe /
+ wie offt du yhn genemen magst /
+ als offt nun yhn und schreib das selbig wie offt / neben der zal /
+ nach dem strichlein /
+ multiplicir inn teiler unnd nim von der gantzen zal.
+ Als dann ruck mit dem teiler fort unter die nehist gen der rechten hand /
+ und besihe aber wie offt du nemen magst / so offt nim /
+ und setz nach der vorigen figur /
+ Also hinfurt bis unter kein figur mehr zu rücken ist wie hie.</file>
+Algorithmus einstellig_dividieren(a, teiler)
+>  Parameter: a[m], teiler
+>  Ergebnis: quotient[m], rest
+>  Vorbedingung: teiler > 0\\
+>  übertrag = 0
+>  für i = m-1 ... 0 SW -1
+>>  übertrag mit BASIS multiplizieren
+>>  übertrag um a[i] erhöhen
+>>  quotient[i] = übertrag div teiler
+>>  übertrag = übertrag mod teiler
+>  rest = übertrag
+<code cpp>
+: 6 = 6789 Rest 0
+          ===========
+  --
+   --
+    --
+     --
+</code>
+==== mehrstellig ====
+<file>
+ Durch zwo figurn.\\
+ Wiltu ein zal ynn zwo figurn teylen /
+ so hab achtung das du ein figur gleich so offt /
+ sam die andere nymst als dann unter die nehisten fort ruck ist /
+ un' abermals so offt du genemen magst nymest.
+ Auch solltu wissen das du den teiler auffs meyst 9 mal /
+ und zum wenigsten ein mal nemen solt also.\\
+ \\
+ Des gleichen soltu auch teiln mit dreyen odder mehr figurn /
+ nym ein figur nach der andern /
+ darnach rück fort und besihe wie offt also.
+</file>
+Algorithmus dividieren(a, b)
+>  Parameter: a[m+n], b[n]
+>  Ergebnis: quotient[m+1], rest[m+n+1]
+>  Vorbedingung: m >= 0, n > 1, b[n-1] > 0\\
+>  rest = a
+>  für j = m ... 0 SW -1
+>>  q = nächste_Ziffer_des_quotienten(rest, b)
+>>  multiplizieren und und von rest abziehen
+>>  quotient[j] = q
+<code cpp>
+  1634958 : 234 = 6987 Rest 0
+            ===========
+  ----
+   ----
+    ----
+     ----
+</code>
+Das schriftliche Dividieren enthält mehr Tücken,
+als man ihm auf den ersten Blick ansieht.
+Die Hinterhältigkeit versteckt sich in Adam Rieses Formulierung
+"so offt du genemen magst".
+Wie oft muss man nehmen? Was ist die nächste Ziffer ''quotient[j]''?
+Beim schriftlichen Rechnen probiert man intuitiv,
+aus Erfahrung wählt man oft die richtige Ziffer.
+Manchmal ist die gewählte Ziffer zu klein oder zu groß.
+Dann muss man einen Teil der Rechnung verwerfen und nachkorrigieren.
+Der Prozess erfordert "Herumraten",
+weil die entstehenden Zwischenergebnisse nicht mehr überblickt werden können.
+Beim einstelligen Dividieren genügte die Kenntnis des kleinen 1x1.
+Jetzt hilft nicht einmal mehr das große.
+Hier werden stärkere Geschütze benötigt.
+Donald E. Knuth schreibt in Abschnitt 4.3.1 von
+[DEK: The Art of Computer Programming. Vol. 2, S.270-273]:
+"Wir müssen die Raterei ausmerzen oder eine Theorie entwickeln,
+um sie sorgfältiger zu erklären."
+Hier wird die Lösung von Knuth dargestellt.
+=== Die nächste Ziffer des Quotienten ===
+Teile die zwei vordersten Ziffern des Restes durch die vorderste Ziffer des Teilers.
+>>  ''q = (rest[j+n] * BASIS + rest[j+n-1]) div b[n-1]''
+>>  ''r = (rest[j+n] * BASIS + rest[j+n-1]) mod b[n-1]'' \\
+Die erhaltene Ziffer q ist niemals kleiner als die gesuchte Ziffer des Quotienten.
+Sie ist andererseits höchstens um zwei zu groß,
+wenn die vorderste Ziffer des Teilers mindestens halb so groß wie die Basis ist. Es gilt:
+>>  ''q-2 <= quotient[j] <= q'', wenn ''b[n-1] >= BASIS/2''.\\
+Darum werden Dividend und Divisor am Anfang "normalisiert", d.h.
+beide Zahlen werden mit ''faktor = BASIS div (1+b[n-1])'' [[#Multiplizieren_einstellig|einstellig multipliziert]].
+Dann gilt ''b[n-1] >= BASIS/2''.
+Erweitern des Bruches ändert nichts am Quotienten.
+Am Schluss muss lediglich der Divisionsrest durch diesen
+[[#Dividieren_einstellig|einstelligen Faktor geteilt]] werden,
+damit das Ergebnis korrekt bleibt.
+Die gute Schätzung für q lässt sich noch weiter verbessern.
+Offensichtlich wäre q = BASIS zu groß.
+Auch die nächsten Ziffern der beteiligten Zahlen können hinzugezogen werden.
+>>  Wenn ''q = BASIS ''ODER ''q*b[n-2] > BASIS*r + rest[j+n-2]'' dann
+>>>  q um 1 vermindern
+>>>  r um b[n-1] erhöhen
+>>>  Wenn jetzt ''r < BASIS'' ODER ''q*b[n-2] > BASIS*r + rest[j+n-2]'' dann
+>>>>  q nochmals um 1 vermindern
+=== Multiplizieren und wegnehmen ===
+Damit sind alle Fälle beseitigt, in denen die Schätzung q um zwei,
+und die meisten, aber nicht alle, in denen q um eins zu groß war.
+Das Wegnehmen muss deshalb mit Vorsicht geschehen.
+>>  übertrag = 1  (borgen)
+>>  produkt = 0
+>>  für i = 0 ... n-1
+>>>  produkt um q*b[i] erhöhen
+>>>  übertrag um BASIS-1 + rest[j+i] - produkt mod BASIS erhöhen
+>>>  rest[j+i] = übertrag mod BASIS
+>>>  übertrag durch BASIS teilen
+>>>  produkt durch BASIS teilen\\
+Die vorderste Ziffer wird getrennt berechnet, könnte aber in der obigen Schleife behandelt werden:
+>>  übertrag um BASIS-1 + rest[j+n] - produkt mod BASIS erhöhen
+>>  rest[j+n] = übertrag mod BASIS
+>>  übertrag durch BASIS teilen
+=== Korrektur durch Zurückaddieren ===
+Ist jetzt kein Übertrag mehr vorhanden, wurde zuviel weggenommen, sodass zurückaddiert werden muss.
+>>  Wenn übertrag = 0 dann
+>>>  q um 1 vermindern
+>>>  für i = 0 ... n-1
+>>>>  übertrag um rest[j+i] + b[i] erhöhen
+>>>>  rest[j+i] = übertrag mod BASIS
+>>>>  übertrag durch BASIS teilen
+>>>  rest[j+n] = 0\\
+Jetzt kann die Ziffer quotient[j] = q festgeschrieben werden.
+Da das mehrstellige Dividieren alle anderen Rechenarten
+Addieren, Subtrahieren, einstelliges Multiplizieren und Dividieren
+in Kombination mit etwas Theorie nutzt,
+ist dieser Algorithmus länger und komplizierter als alle anderen zusammen.
+Vor 500 Jahren konnte sich noch nicht jede Universität einen Professor leisten,
+der das Dividieren beherrschte...
+Genießen Sie den Algorithmus in voller Schönheit:
+Algorithmus dividieren(a, b)
+>  Parameter: a[m+n], b[n]
+>  Ergebnis: quotient[m+1], rest[m+n+1]
+>  Vorbedingung: m >= 0, n > 1, b[n-1] > 0\\
+>  rest = a
+>  faktor = BASIS div (1+b[n-1])
+>  normalisieren(rest, faktor)
+>  für j = m ... 0 SW -1
+>>  q = (rest[j+n] * BASIS + rest[j+n-1]) div b[n-1]
+>>  r = (rest[j+n] * BASIS + rest[j+n-1]) mod b[n-1]
+>>  wenn q = BASIS ODER q*b[n-2] > BASIS*r + rest[j+n-2] dann
+>>>  q um 1 vermindern
+>>>  r um b[n-1] erhöhen
+>>>  wenn r < BASIS ODER q*b[n-2] > BASIS*r + rest[j+n-2] dann
+>>>>  q um 1 vermindern
+>>  übertrag = 1
+>>  produkt = 0
+>>  für i = 0 ... n
+>>>  wenn i<n dann produkt um q*b[i] erhöhen
+>>>  übertrag um BASIS-1 + rest[j+i] - produkt mod BASIS erhöhen
+>>>  rest[j+i] = übertrag mod BASIS
+>>>  übertrag durch BASIS teilen
+>>>  produkt durch BASIS teilen
+>>  wenn übertrag = 0 dann
+>>>  q um 1 vermindern
+>>>  für i = 0 ... n-1
+>>>>  übertrag um rest[j+i] + b[i] erhöhen
+>>>>  rest[j+i] = übertrag mod BASIS
+>>>>  übertrag durch BASIS teilen
+>>>  rest[j+n] = 0
+>>  quotient[j] = q
+>  denormalisieren(rest, faktor)
+===== Vorzeichenregeln =====
+Verglichen mit den Algorithmen für das Rechnen mit Absolutwerten sind
+die Regeln für Plus und Minus ein Klacks:
+  * Die Null ist weder positiv noch negativ.
+  *  Ganze Zahlen mit gleichem Vorzeichen werden in ihren Absolutwerten addiert,
+  das Ergebnis erhält das gemeinsame Vorzeichen.   *  Bei unterschiedlichem Vorzeichen muss die absolut kleinere von der absolut größeren abgezogen werden.
+  das Vorzeichen des Ergebnisses wird durch das Vorzeichen der Absolut größeren Zahl bestimmt.   * Subtrahieren ist Addieren des Minuenden mit entgegengesetztem Vorzeichen.
+  * Das Produkt zweier Ganzzahlen ist negativ, wenn die Vorzeichen der Faktoren verschieden sind.
+  * Dasselbe gilt für das Vorzeichen des Quotienten ''q'' zweier Zahlen ''a'' und ''b''.
+  *  Wegen den Beziehungen ''a = b*q + r'' und ''abs(a) >= abs(b*q)''
+  trägt der Divisionsrest ''r'' dasselbe Vorzeichen wie der Dividend ''a''.