namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:rechnen

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

 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.

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

   123456
  +  9208
    1  1    <- Übertrag
  -------
   132664
  =======

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

 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.

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!

   132664       
  -123456
    1  1    <- Übertrag (geborgt)
  -------
     9208
  =======

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

 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.

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

  6789 * 6
  --------
      455     <-- Übertrag
     40734
  ========

Einstelliges Multiplizieren kann am Ort, innerhalb eines Feldes geschehen, d.h. die Ziffern des Ergebnisses überschreiben den Platz der Ziffern a[i].

mehrstellig

 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.

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

  6987 * 234
  ----------
       27984
      20961
     13974
  ----------
     1634958
  ==========

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*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

 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.

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

  40734 : 6 = 6789 Rest 0
  36          =========== 
  --
   47
   42
   --
    53
    48
    --
     54
     54
     --
      0

mehrstellig

 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.

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
  1634958 : 234 = 6987 Rest 0
  1404            ===========
  ----
   2309
   2106
   ----
    2035
    1872
    ----
     1638
     1638
     ----
        0

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]) einstellig multipliziert. Dann gilt b[n-1] >= BASIS/2. Erweitern des Bruches ändert nichts am Quotienten. Am Schluss muss lediglich der Divisionsrest durch diesen 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''. 
anwenden/rechnen.txt · Zuletzt geändert: 2014-07-13 16:14 (Externe Bearbeitung)