Autor Beitrag
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Sa 23.12.06 18:18 
Multiplikation großer Zahlen

Hallo, in diesem Tutorial geht es um die Multiplikation von Zahlen, die weit über die Maxima von integer und integer64 hinaus gehen. Benötigt werden diese allerdings in Stringform.

Hintergrund:

Das Prinzip, welches ich hier vorstelle, basiert auf der Vedischen Multiplikation.
Dieses Prinzip lässt sich wunderbar zur schriftlichen Multiplikation heranziehen, falls man gerade mal keinen Taschenrechner zur Hand hat.

Zuerst ein einfaches Beispiel mit zwei Zwei-Stelligen Zahlen:

Zitat:

0034
0056
----
1904

(die Nullen dienen allein zur Formatierung)

Zuerst berechnet man das Produkt von 4 und 6, die letzte Stelle wird notiert und die anderen Stellen gemerkt oder notiert.
In diesem Falle ist die Zahl 4 und der übertrag 2
Danach werden die beiden letzten Stellen der Zahlen über Kreuz multipliziert und anschließend addiert, der übertrag der letzten Rechnung wird aufaddiert.
Zitat:
3 * 6 + 5 * 4 + 2 = 40

Also ist unsere Zahl 0 und der übertrag ist 4

Jetzt werden die ersten Stellen multipliziert und der übertrag addiert:
Zitat:
3 * 5 + 4 = 19

unsere Zahl ist 9 und der übertrag ist 1
jetzt sind wir fertig, der übertrag wird noch vorne drangehängt, da wir alle Stellen abgearbeitet haben und nur noch Null-Stellen übrig sind.
Unser ergebnis ist demnach 1904.

Bei größeren Zahlen wird das ganze ein wenig komplizierter, wir brauchen pro zusätzliche Stelle zwei weitere Schritte, bei 3 Stellen sähe das so aus:

user defined image

Bei 4 Stellen hätten wir diese dreifache Überkreuzung wiederrum 2 mal und dazwischen eine größere.
Möchte man eine zwei Zahlen mit unterschiedlicher Stellenzahl multiplizieren, so kann man die kleinere Zahl vorne mit Nullen auffüllen.

Wer mehr über vedische Mathematik erfahren will, kann einen Blick hier hinein werfen:
www.vedicmaths.org/I...utorial/Tutorial.asp

Dieses Prinzip kann ebenfalls auf andere Basen, so zB für Oktal, Hexadezimal und Binärsysteme angewandt werden!

Die Implementation:

Als ich user profile iconCorpsman davon erzählt habe, hat er dies auch gleich in einen Algorithmus umgesetzt, dieser ist hier zu finden:

tyrann.deadbyte.de/c...ische_multiplication

Trotzdem möchte ich hier etwas genauer darauf eingehen.

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
function VedicMulti(a, b: string): string;
var
  len, i, j: integer;
  num: int64;
begin
  // Variablen initialisieren
  result := '';
  num := 0;
  // Längste Zahl bestimmen
  len := max(length(a), length(b));
  // Mit Nullen auffüllen
  while length(a) < len do
    a := '0' + a;
  while length(b) < len do
    b := '0' + b;
  // Von Rechts zur Mitte
  for i := 1 to len do
  begin
    for j := 1 to i do
      num := num + strtoint(a[len - j + 1]) * strtoint(b[len - i + j]);
    result := inttostr(num mod 10) + result;
    num := num div 10;
  end;
  // Von der Mitte Nach links
  for i := len - 1 downto 1 do
  begin
    for j := 1 to i do
      num := num + strtoint(a[j]) * strtoint(b[i - j + 1]);
    result := inttostr(num mod 10) + result;
    num := num div 10;
  end;
  // Letzten übertrag hinzufügen
  result := inttostr(num) + result;
  // Führende Nullen löschen
  while Pos('0', result) = 1 do
    delete(result, 11);
end;

Der Algo ist im Grunde genommen der gleiche wie der von user profile iconCorpsman, eine rekursive Implementation ist ebenfalls möglich und werde ich eventuell noch nachreichen, bisher ist mir diese leider noch nicht geglückt ;)

Der Algo berechnet zunächst die Länge der längsten Zahl, dann wird die kürzere Zahl (falls vorhanden) mit Nullen aufgefüllt. Die doppelte Länge minus 1 ergibt die Anzahl der benötigten Schritte. Zuerst wird von rechts zur Mitte gearbeitet und im zweiten Schritt von der Mitte nach links. Dabei sorgt die äußere Schleife für das Durchgehen aller Schritte und die innere Multipliziert und addiert die Ziffern über Kreuz. Am Ende wird jeweils die Zahl berechnet und gespeichert, sowie der übertrag berechnet (mod 10 liefert die letzte Stelle und div 10 alles davor). Im nächsten Iterations-Schritt wird der zuvor berechnete übertrag dazu
addiert und der nächste Wert berechnet. Am ende wird noch der letzte übertrag (der auch 0 sein kann) vorne angefügt und alle überflüssigen Nullen entfernt.

Der Grund, warum diese Algo so große Zahlen berechnen kann, liegt darin, dass die einzige Integer Variable mit der gerechnet wird, der übertrag ist, und dieser ist immer recht klein. Durch die Verwendung von int64 lässt sich diese Grenze noch ausweiten (wie bereits im Algo geschehen). die zweite Beschränkung sind die Schleifenvariablen und die Variable zum Speichern der Länge des Strings. Hier kann man ebenfalls noch auf int64 umsteigen.

Alles in allem aber lassen sich mit diesem Algo sehr schnell extrem große Zahlen berechnen, bei denen der Windows Taschenrechner nicht mehr mitreden kann.

Vielen Dank an user profile iconCorpsman für den Algorithmus.

Ich hoffe es war lustig und lehrreich und jemand kann es gebrauchen.

Weiterführende Links:

(Video mit Erklärung von Vedischer Multiplikation)
www.metacafe.com/wat...fast_multiplication/
(Tutorial zur Vedischen Mathematik)
www.vedicmaths.org/I...utorial/Tutorial.asp
(Demo Programm von user profile iconCorpsman mit Source)
tyrann.deadbyte.de/c...ische_multiplication

mfg


Zuletzt bearbeitet von F34r0fTh3D4rk am Do 29.03.07 19:36, insgesamt 3-mal bearbeitet
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Moderator
Beiträge: 3655
Erhaltene Danke: 594

Win XP x86, Win 8.1 x64
Lazarus Snapshot; Delphi 7,2007,XE; PHP (PHPEdit,PhpStorm); JS; Java(Eclipse)
BeitragVerfasst: So 24.12.06 00:19 
Sehr schön. Ist wahrscheinlich das erste deutsche Dokument über Vedic Math.

Was ich aber anmerken muss: das Ding heißt nicht Rest, sondern Übertrag (carry).

Man könnte auch noch anmerken, dass diese Rechenmethode für beliebige Basen funktioniert, also auch für Hex- oder Binärwerte. (Binär ist übrigens praktisch für die Schule, wenn der Infolehrer mit so verrückten Aufgaben kommt :) )

Übrigens: man könnte sowas mal in die diversen BigNumber-Klassen implementieren. Und was aber immer noch fehlt, ist was gutes zur Division.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
F34r0fTh3D4rk Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: So 24.12.06 12:18 
aso, das mit dem rest, etc werde ich editieren, es gibt soweit ich weiß auch eine methode für die division, die kommt dann im nächsten tutorial ;)

ich hoffe dass das prinzip aus dem tutorial hervorgeht und man es danach verstanden hat ;)

ich hoffe auch, dass es einige dazu bringt, bei multiplikationen mit 3-Stelligen Zahlen nicht gleich den Taschenrechner zu zücken, denn in der zeit wo man das tut, kann man das ergebnis schon haben ;)

mfg und frohe weihnachten ;)