namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:rechnen

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

anwenden:rechnen [2014-07-13 16:14] (aktuell)
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>
 +   123456
 +  +  9208
 +    1  1    <- Übertrag
 +  -------
 +   132664
 +  =======
 +</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>
 +   132664       
 +  -123456
 +    1  1    <- Übertrag (geborgt)
 +  -------
 +     9208
 +  =======
 +</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>
 +  6789 * 6
 +  --------
 +      455     <-- Übertrag
 +     40734
 +  ========
 +</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>
 +  6987 * 234
 +  ----------
 +       27984
 +      20961
 +     13974
 +  ----------
 +     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*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>
 +  40734 : 6 = 6789 Rest 0
 +  36          =========== 
 +  --
 +   47
 +   42
 +   --
 +    53
 +    48
 +    --
 +     54
 +     54
 +     --
 +      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
 +  1404            ===========
 +  ----
 +   2309
 +   2106
 +   ----
 +    2035
 +    1872
 +    ----
 +     1638
 +     1638
 +     ----
 +        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''
 +
  
anwenden/rechnen.txt · Zuletzt geändert: 2014-07-13 16:14 (Externe Bearbeitung)