Guter Algorithmus zum multiplizieren großer Zahlen gesucht

[FAlter]

Hallo,

ich bin gerade dabei, darüber nachzudenken, wie ich am gescheitesten zwei 128 Bit große Integerzahlen auf meinem 32 Bit System multiplizieren kann.

Ein Gedanke wäre, die schriftliche Multiplikation aus der Grundschule nachzubilden und die Vorzeichen vorher extra behandeln/hinterher entsprechend wieder korrigieren, sodass man immer positive Zahlen multipliziert. Dabei würde ich 32bittig multiplizieren und die Ergebnisse dann entsprechend addieren.

Nun kommt mir dieser Ansatz aber sehr komplex vor. Gibt es vielleicht einen besseren Ansatz (einfacher, schneller?)

Ein noch schlimmerer und schon längst wieder verworfener Gedanke war es, das ganze so oft mit sich zu addieren wie es der andere Faktor angibt. Aber das ist zu umständlich und wird wohl ewig dauern.

Ideen können z. B. in Worten, Delphi (class operator Multiply(const Left, Right: Int128): Int128;) oder Assembler (eax zeigt auf/adressiert Ergebnis, edx auf linken und ecx auf rechten Faktor) formuliert werden. ;)
Int128 ist ein Record, dass zwei Int64 (Lo und Hi) enthält. Addition und Subtraktion, Vergleiche und Negation sind per Operatorüberladung bereits problemlos möglich.

So, jetzt schlaf ich erstmal ne Nacht darüber...

Mfg
FAlter

[Neutral General]

Zitat:

ich bin gerade dabei, darüber nachzudenken, wie ich am gescheitesten zwei 128 Bit große Integerzahlen auf meinem 32 Bit System multiplizieren kann.

Weiter habe ich nicht gelesen. Aber das reicht schon.

Mein Tipp: Schlafen und morgen weiterdenken :mrgreen: :wink:
Das werde ich jetzt auch tun.

Gute Nacht :stupid:

[Corpsman]

Ich denke die Variante mit dem Zerlegen in die 4 Int32bit zahlen dürfte das beste sein.

so werden die ja schlieslich intern auch gerechnet ...

Die Schulmethode Shift add wird da wohl zu langsam sein .

[jfheins]

Also ich würde sagen, du kannst die Zahlen einfach ausmultiplizieren ;)

Soll heißen, wenn du die in 2 64bit Zahlen splittest (verschnkt übrigens ein bit, da du 2 Vorzeichenbits hast)

Und dann kannnst du rechnen: A*B = a1*b1*2^128 + a1*b2*2^64 + a2*b1*2^64 + a2*b2

Jetzt musst du nur noch eine Funktion schreiben, die 2 64bit Zahlen multipliziert und das Ergebnis als 128bit Zahl zurückgibt (die 2^64 kannste ja shiften...) ;)

(Mit 32bit wirds natürlich entsprechend länger ...)

Btw.: Auf fast allen modernen CPUs gibt es doch bereits vorgefertigte 128bit Arithmetik, oder nicht?

[himitsu]

Die 64-Bit-Operationen sind aber auch nicht grad schnell (wenn man nicht grad in 64 Bit programmiert)
Dann doch lieber direkt 32 Bit-Operationen(?)
ups, stümmt, da gab's doch noch was (ok, dann halt weiter in ASM und SSE2)

[FAlter]

Hi,

Zitat:

Zitat von jfheins

Btw.: Auf fast allen modernen CPUs gibt es doch bereits vorgefertigte 128bit Arithmetik, oder nicht?

Und das wäre? Meine kann MMX, SSE und SSE2. Aber das sind alles Themen mit denen ich mich noch nie beschäftigt habe. Nur mal schnell nachgesehen, was das für Anweisungen kennt.

Die MMX-Register sind nur 64 Bit groß. Das ist defginitiv keine 128er Arithmetik. Außerdem, so weit ich es lese, arbeitet das maximal mit 32 bit, und man verarbeitet eben 2 32bittige Zahlen zusammen. Also ohne dass sich der Übertrag der einen z. B. auf die andere auswirkt.

Bei SSE lese ich nur was von Floating Point Operationen, auch da eben mehrere Zahlen glecihzeitig.

Bei SSE2 ist beides möglich, Packed Floats und Packed Integers; und da kann man schonmal endlich mit 64-Bit-Werten rechnen, von denen zwei in dem 128-Bit-Register stehen.

Ich sehe also keine direkte Möglichkeit mit meiner CPU 128-Bittig zu multiplizieren.

Mfg
FAlter

[jfheins]

Naja, kann sein dass es das nicht in einem Befehl gibt ... ich hab nur SSE&128bit Register gelesen :oops:

Aber du brauchst ja auch nur 64bit Arithmetik ;)

Denn: A*B = a1*b1*2^128 + a1*b2*2^64 + a2*b1*2^64 + a2*b2

Den ersten Term kannst du vergessen. (Würde deinen 128bit Typen sprengen)

Den 2. kannste ausrechnen mit 64bit und zum dritten dazuaddieren *wuppdi* haste den "hohen-ergbnis-64bit-wert" und der vierte Term liefert dir den niedrigen 64bit wert.

Also keine native 128bit Miltiplikation von Ganzzahlen aber alles was du brauchst um es mit wenigen Assemble Befehlen zu schreiben ;)

[FAlter]

Hi,

aber wie sieht es mit den Überträgen aus, die bei der 64Bit-Multiplikation ggf. entstehen? Ich habe das Gefühl, diese werden wohl verworfen... [edit] Unsinniger Satz... [/edit]

Aber mit den 64 Bit (Quad Words):

http://flatassembler.net/docs.php?article=manual#2.1.16

SSE2 mit ghepackten QWords:

paddq performs the addition of packed quad words, psubq performs the substraction of packed quad words, pmuludq performs an unsigned multiply of low double words from each corresponding quad words and returns the results in packed quad words. These instructions follow the same rules for operands as the general MMX operations described in 2.1.14.

Das heißt die einzige 64-Bit-Multiplikation die es mit SSE2 gibt ist eine 32-Bit-Multiplikation mit 63 64-Bit ergebnissen, ansonsten kann man nur 64-Bit addieren und subtrahieren. Und zwar bei allen drei Anweisungen jeweils zwei Operationen (zwei Zahlen) gleichzeitig.

Also geht das mit der 64-Bit-Multiplikation auch nur über den 32-Bit-Umweg. Da werde ich wohl letztlich es doch per Hand mit 32-Bit stricken. Erstmal ohne SSE und dann wenns klappt und ich auch ne Division (mit Rest!) habe ggf. nochmal zum lernen / als Übung mit SSE.

Mfg
FAlter

[edit] Was mach ich denn alles für Fehler? Ich will meine Rechtschreibprüfung zurück haben! [/edit]

[FAlter]

Hi,

hier mein aktueller Stand, ich habe in Assembler eine Proc zum unsigned multiplizieren geschrieben, die sogar ein 256 bittiges Ergebnis zurückliefert. Und dann In Delphi die Behandlung des Vorzeichens. Also jeweils in der Sprache, wo ich es einfacher fand.

Hier die Unsigned Multiplikation, ist sicherlich noch optimierungsfähig:

Delphi-Quellcode:

procedure MulPInt128U256U(const Result: PInt128; Left, Right: PInt128);
//Result: 256 bit --> zwei PInt128 (Lo, Hi) nacheinander!!!
//Unsigned!
//for 32-bit; nur wenn ss = ds, was bei Delphi immer zu sein scheint
//(kleine Optimierung durch Voraussetzung)
var
  buf1, buf2, buf3: array[0..4] of LongWord;
asm
//mul performs an unsigned multiplication of the operand and the accumulator.
//[...] If the operand is a double word, the processor multiplies it
//by the contents of EAX and returns the 64-bit result in EDX and EAX. mul
//sets CF and OF when the upper half of the result is nonzero, otherwise they
//are cleared. Rules for the operand are the same as for the inc instruction.

  push ebx
  push esi

  push eax
  push ecx

  mov esi, edx

  mov ecx, [ecx]
  mov ebx, eax
  call @@multiply

  mov ebx, [esp] //=original ecx
  mov ecx, [ebx+4]
  lea ebx, [buf1]
  call @@multiply

  mov ebx, [esp]
  mov ecx, [ebx+8]
  lea ebx, [buf2]
  call @@multiply

  mov ebx, [esp]
  mov ecx, [ebx+12]
  lea ebx, [buf3]
  call @@multiply

  //pop ecx
  add esp, 4 //Wert von ecx nicht wichtig, add schneller
  pop eax

  lea ebx, [buf1]
  xor ecx, ecx
  call @@add

  lea ebx, [buf2]
  call @@add

  lea ebx, [buf3]
  call @@add

  jmp @@end

  @@multiply:
    //eine Zeile multiplizieren
    //ecx = dword-faktor
    //abx = buf für ergebnis
    //und esi: Zeigt auf 128-Bit-Faktor!!!

    mov eax, [esi]
    mul ecx
    mov [ebx], eax
    mov [ebx+4], edx

    mov eax, [esi+4]
    mul ecx
    add[ebx+4], eax
    adc edx, 0
    mov [ebx+8], edx
    jc @@m1             //Übertrag speichern
      mov [ebx+12], 0
      jmp @@m2
    @@m1:
      mov [ebx+12], 1
    @@m2:

    mov eax, [esi+8]
    mul ecx
    add [ebx+8], eax
    adc [ebx+12], edx
    jc @@m3             //Übertrag speichern
      mov [ebx+16], 0
      jmp @@m4
    @@m3:
      mov [ebx+16], 1
    @@m4:

    mov eax, [esi+12]
    mul ecx
    add [ebx+12], eax
    adc [ebx+16], edx

  //Wenn jetzt noch ein Bit Übertrag ist, scheiss ich drauf!
  //Oder quäle mich wenn es immer total falsch rechnet :(
  //Meiner Berechnung sollten die 160 Bit (5*32 Bit) aber genau passen für eine
  //Multiplikation 32-Bit mit 128-Bit
  ret

  @@addcarry:
    //eax --> Ergebnis-Stelle
    //ebx ist wieder buf --> Stelle
    //ecx - letzter Übertrag

    add ecx, [ebx]  //Übertrag verrechnen

    jnc @@a1        //neuer Übertrag?
      mov edx, 1    //Speichern
    jmp @@a2
    @@a1:           //kein neuer Übertrag
      xor edx, edx  //Speichern
    @@a2:

    add [eax], ecx  //eigentliche Addition

    jnc @@a3        //neuer Übertrag?
      inc edx       //Speichern/erhöhen
    @@a3:

    mov ecx, edx
  ret

  @@add:
    //EAX -> Ergebnis, letzte Stelle
    //(nicht sie Stelle, die zuerst addiert werden soll, sondern DAVOR)
    //zwei der Zeilen zusammenaddieren
    //ebx ist wieder buf
    //ecx - letzter Übertrag

    add eax, 4  //ne Stelle weiterrutschen

    push eax    //4 Stellen addieren...
      call @@addcarry

      add eax, 4
      add ebx, 4
      call @@addcarry

      add eax, 4
      add ebx, 4
      call @@addcarry

      add eax, 4
      add ebx, 4
      call @@addcarry
    pop eax
  ret

  @@end:

  pop esi
  pop ebx
end;

Und hier die Vorzeichenbehaftete Multiplikation, die darauf zurückgreift:

Delphi-Quellcode:

procedure MulPInt128(const Result: PInt128; Left, Right: PInt128);
var
  Negative: Boolean;
  Help1, Help2: PInt128;
  UseH1, UseH2: Boolean;
  Reslt{$IFOPT Q+}, Reslt2{$ENDIF}: PInt128;
begin
  Help1 := nil; UseH1 := false;
  Help2 := nil; UseH2 := false;

  Negative := false;

  try

    if Left^ < 0 then
    begin
      Negative := true;
      UseH1 := true;
      New(Help1);
      Help1^ := -Left^;
    end
    else
      Help1 := Left;
    if Right^ < 0 then
    begin
      Negative := not Negative;
      UseH2 := true;
      New(Help2);
      Help2^ := -Right^;
    end
    else
      Help2 := Right;

    GetMem(Reslt, SizeOf(Int128) * 2);
    try
      MulPInt128U256U(Reslt, Help1, Help2);

      Result^ := Reslt^;

      {$IFOPT Q+}
      Reslt2 := Reslt;
      inc(Reslt2);

      if (Reslt2^ <> 0) or (Reslt < 0) then
        raise EIntOverflow.Create('Integer Overflow.');
      {$ENDIF}
    finally
      FreeMem(Reslt);
    end;

    if Negative then
      Result^ := -Result^;
  finally
    if UseH2 then Dispose(Help2);
    if UseH1 then Dispose(Help1);
  end;
end;

Mfg
FAlter

[jfheins]

Ich kenne mich jetzt nicht mit Assembler aus, aber ... du addierst doch nicht etwa, oder?

Außerdem kann ich mir nicht vorstellen, dass das effizient ist - das sieht mir einfach zu lang aus :mrgreen:

Um nochmal auf meinen Vorschlag zurückzukommen:

128bit - A*B = a1*b2*2^64 + a2*b1*2^64 + a2*b2

Kannst du weiter runterbrechen - d.h. eine Multiplikation von 2 64bit Werten sieht dann so aus:

x*y = x1*y1*2^64 + x1*y2*2^32 + x2*y1*2^32 + x2*y2

Wobei x1 das high-order dword ist und x2 das low-order dword. [s]Außerdem kannst du wieder den ersten Term vernachlässigen (würde wieder zu einem Überlauf führen)[s] Vergiss das ^^

Du musst dann eben Funktionen für 64bit und 32bit Multiplikation sowie zur Multiplikation mit 2er Potenzen zur Verfügung stellen ;)

Du könntest daraus auch etwas rekursives machen nach dem Motto "Teile und Herrsche" :mrgreen:

[FAlter]

Hi,

ich multipliziere, die Unterprozedur @@multiply (welche sich an keinerlei Vereinbarungen hält...) multipliziert jeweils einen 32-Bit-Wert mit dem einen der 128-Bit-Werte, also 4 32-Bit-Multiplikationen, welche ja 64-Bit-Ergebnisse liefern, mit entsprechenden Additionen (Überträge). Das Ergebnis ist eine 160-Bit-Zahl, die erste wird gleich im Ergebnis gespeichert, die anderen drei Zwischenwerte werden in den bufX gespeichert. Zum Schluss werden die Ergebnisse versetzt zusammenaddiert. Das entspricht also der schriftlichen Multiplikation, und prinzipiell ist es deinem Verfahren ähnlich. Ich erwende zwar keine Shifts, aber ich addiere versetzt, und dass Versetzen ist ja der Sinn deiner Shifts.
Insbesondere, dass die Überträge aus dem CF und nicht verloren gehen hat mir Sorgen bereitet.

Insgesamt habe ich 16 mal multipliziert. Ich addiere ja nicht eine Zahl, die so groß ist, dass sie in keinen int64 mehr passt, in einer in dieselbe Größenordnung passenden Anzahl mit sich selbst, das dauert dann ja Jahre. Meine Tests, die unter anderem über 100000000 Multiplikationen enthalten, haben etwa 3,5 Minuten gebraucht (Pentium 4, kein HT, derzeit 2533 MHz). Ich will nicht wissen, was die Additionsvariante benötigen würde.

Mfg
FAlter

[Hawkeye219]

Hallo,

hier noch ein Link zum Thema: Multiplikation langer Zahlen

Gruß Hawkeye

[FAlter]

Hi,

Zitat:

Zitat von Hawkeye219

hier noch ein Link zum Thema: Multiplikation langer Zahlen

Das war ja gar nicht so einfach zu verstehen, aber ich glaube jetzt hab ichs.

Ich habe mir dann auch mal überlegt, was das bedeuten würde, wenn ich zwei 64-Bit-Zahlen damit in 32 Bit zerlegen wurde, um das Produkt zu berechnen. Ich bin von 64 Bit unsigned ausgegangen, also ohne Vorzeichen. [edit]Die Einzelnen 32-bittigen "Ziffern" sind aber eh vorzeichenlos.[/edit]

Der Schritt
v=(q-p)(s-r)
sieht mir problematisch aus.

pq und rs sind ja die einzelnen "Stellen", also 32-Bit-Teile er 64-Bit-Zahlen. Sie sind unsigned Integers und können ALLE Werte von 0 bis 2^32-1 sein.

Da gibt es nun z. B. für q-p folgende Fälle:

q > p --> das Ergebnis ist positiv. Wenn p gar 0 ist und q = 2^32-1, ist es 2^32-1.
q = p --> 0
q < p --> das Ergebnis ist negativ. Im Extremfall ist q = 0 und p=2^32-1.

Das Ergebnis muss also Zahlen von +2^32-1 bis -2^32-1 speichern können und daher ist es mindestens 33 Bit groß, weil Vorzeichen wichtig ist. Das Vorzeichen wird ja auch extra im Text betont.

Das gleiche gilt auch für die andere Differenz.
Diese 33-Bit-Zahlen werden jetzt miteinander multipliziert. Das kann der Prozessor aber nicht, er kann nur 32-Bit-Zahlen multiplizieren. Also müsste man die Zahlen erweitern und z. B. einen Algorithmus verwenden, um Zahlen 64-Bittig miteinander zu multiplizieren. Genau das war aber der gesuchte Fall. (Das Ergebnis der 33-Bit-Multiplikation kann übrigens im schlimmsten Fall nur mit 66 Bits oder mehr dargestellt werden...)

Auch andere Gedanken, die ich mir dazu gemacht habe, wie man dieses "Problem" umgehen könnte (und da hatte ich schon einige Ideen) lassen es mir letztlich als kompliziert erscheinen. Da nehme ich doch lieber meine Schulmethode.

Ich habe mich mal in meinem Testprogrammcode durchgewühlt und dort mit Taschenrechner ;) die Anzahl der Multiplikationen gezählt, die dort mit meinem Algo oben durchgeführt werden. In den 3,5 Minuten schafft mein PC 322 Millionen Multiplikationen. Ich denke mal das reicht mir für meine Zwecke aus, denn die Fälle, in denen ich 128 Bits verwenden möchte, sind ja nicht Fälle wo ich viele Berechnungen nacheinander vornehmen möchte, sondern ich habe vor, große Zahlen zu verwenden.

Mfg
FAlter

[negaH]

Hi Felix,

zuerstmal rate ich dir mit Assembler zu arbeiten. Dabei gibt es keine Unterscheidung zwischen 32 Bit Integern mit oder ohne Vorzeichen da intern immer im komplementären Zahlen (bei Vorzeichen) gearbeitet wird. Das Vorzeichen spielt also bei der 32 Bit ASM Multiplikation keine Rolle, ebenso bei der Addition und Subtraktion.

Als nächstes musst du also die Entscheidung treffen wie deine Langzahlen definiert sind, also wie das Vorzeichen gespeichert wird. Als am sinnvollsten hat sich Signed Magnitude herausgestellt. Dh. das Vorzeichen der Lanhzahl wird extern in einem eigenen zb. Boolean gespeichert. Für Mul/Div ist also das sich ergebende Vorzeichen = Vorzeichen A xor Vorzeichen B.

Die Langzahl selber stellt also immer den Absolutbetrag der Zahl dar.

Nun zu den einzelenen Verfahren:

1.) Schoolboy, das ist das was du schon machst
2.) COMBA. das ist Schoolby aber leicht optimiert, eine Pyramidenförmige Multiplikation bei der die partiellen Zwischenprodukte pyramidenförmig addiert werden und somit besser auf 32 Bit Rechnern optimiert sind.
3.) Karatsuba Multiplikation
4.) TOOM-COOK Multiplikation, das ist wie Karatsuba nur teilt man nicht in 2 Teile sondern in 3,5,7 usw.
5.) FFT, genauer die Schönhage-Strassen-modulare-Fermat-Fast-Fourier-Transformation

Alle dieses Methoden habe ich in meinem DECMath schon implementiert. Die Selektion welche dieser Verfahren dann zur Laufzeit angewendet werden hängt von einer Thesholdtabelle ab, also von der Digitanzahl=Anzahl von 32Bit Werten, der beiden Multilikanten. Diese Breakeven-Tabelle wird für verscheidene Rechnerarchitekturen errechnet. Das ist nötig da zb. die Multiplikation und Addition/Subtrakton bei mir als Low-Low-Level Funktionen als I32 wie auch SSE2 Assembler Funktinen vorliegen. Und da sind wir bei der nächsten Entscheidung: Umsetzung in Assembler in 32 Bit IA32 Code oder SSE2 oder MMX (für zb. Boolsche Operationen XOR, OR, AND usw.) Mit SSE2 kann man dann statt mit 32Bit Digit mit 64Bit Digits arbeiten, man zerlegt also den Langzahl-Speicherbereich nicht in 32Bit Digits sonder 64Bit Digits.

Aber für die Multiplikation von 2x 128Bit Werten kann ich dir jetzt schon sagen das die Schoolboy Methode am effizientesten sein wird. Die COMBA Methode lohnt sich dann nur für ältere Rechner da sie die Speicherzugriffe optimiert und bei neueren Rechnern sind diese kein Problem mehr.
Also würde ich an deiner Stelle mit SSE2 Assembler implementieren, nachdem du eine normale IA32 MUL implementiert hast. Nur das schafft noch einen Performanceboost von Faktor x2. Falls du immer mit fixen 128 Bit Zahlen arbeitest dann dürfte mit SSE2 noch mehr drinnen sein.

Auf SSE2 Rechnern gilt für die Multipliaktion bei meinem DECMath:
Die Karatsuba lohnt erst ab so ca. 42 Digits = 1344 Bit Zahlen.
Toom-Cook-3 bei 7424 Bits.
Die FFT sogar erst ab 177984 Bit großen Zahlen.

Für die Quadrierung, die ca. 1.5mal schneller sein kann als eine Multiplikation gilt:
Karatsuba 2048 Bit Zahlen
Toom-Cook-3 7552 Bit Zahlen
FFT 174784 Bit großen Zahlen

Diese Breakeven's gelten für beide Multiplikanten, jeweils der kleiner zählt. Also zb. 256 Bit * 128 Bit bedeutet das man defakto 2x eine 128 Bit Mul machen muß. Man muß also die 256 Bit große Zahl in 2 Teile a 128 Bit zerlegen und diese dann mit der anderen 128 Bit großen Zahl multiplizieren. Man betrachtet also die 256 Bit große Zahl als eine Zahl mit 2 Digit = 2 Ziffern und die 128 Bit große Zahl als eine mit 1 Digit= 1 Ziffer a 128 Bit Größe.
Daran erkennt man das man nach Möglichkeit die Zwischenresultate eines mathematischen Verfahrens auf gleiche Größe gewichten sollte um die höchste Performance rauszuholen.

Aufbauend auf einer Lanzahl * 1 Digit Multiplikation in Assembler kannst du jede höherwertige Multiplikation programmieren. Es hat sich aber gezeigt das es aus Sicht der Performance auch gut ist wenn man eine Langzahl * Langzahl Schoolboy Multiplikation in purem Assembler implementiert, statt diese aus mehreren Aufrufen der Langzahl * 1 Digit Mul in Hochsprache aufzubauen.

Mein DECMath benutzt ebenfalls ein Signed Magnitude Speicherformat der Langzahlen. Allerdings noch mit Optimierungen im Speichermanagement. Dh. der Speicherbereich der Langzahl wird in bestimmten Schrittweiten immer prealloziert statt für jedes Digit immer neu beim Speichermanager neu zu reallozieren zu müssen. Somit führt die Langzahl-Datenstruktur die reale Größe in Digits und die benutzte Anzahl der Digits als 2 Recordfelder mit, neben dem Vorzeichen als Boolean.

Falls du weiterführende Fragen hast dann frag mich einfach ;)

Gruß Hagen

[negaH]

Zitat:

Zitat von Hawkeye219

Hallo,

hier noch ein Link zum Thema: Multiplikation langer Zahlen

Gruß Hawkeye

Mir sind par Sachen aufgefallen:

1.) es heist Karatsuba und nicht Karazuba, das das dem Prof der diese Arbeit abgenommen hat nicht aufgefallen ist ?

2.) die Analyse des Aufwandes für den Karatsuba Trick ist einseitig. Sie berücksichtigt nicht die Aufwandsdifferenz zwischen Additonen und Multiplikationen. Wenn zb. eine CPU für die Addition 1 Takt benötigt und für die Multiplikation ebenfalls nur 1 oder 2 Takte dann ist der Karatsuba Trick nicht mehr besser als eine Schoolboy Methode. Nun dieser Unterschied im Aufwand für diese beiden Operationen ist aber essentiell und muß für die jeweilige Rechnerarchitektur berücksichtigt werden. Je weniger Takte eine CPU für eine Multiplikation im Vergleich zu Addition benötigt desto weniger lohnt Karatsuba

3.) die Addition der partiellen Zwischenprodukte wurde links wie rechts mit Nullen erweitert und dann davon ausgehend die Anzahl der Additionen berechnet um den Gesamtaufwand zu errechnen. Das ist natürlich ineffizient und nicht nötig. Normalerweise addiert man zwei Speicherbereiche mit unterschiedlichen Offsets in diese Bereiche und somit auch wirklich nur diejenigen Ziffern die von Relevanz sind.

4.) bei der Karatsuba Methode muß man schon einiges an Intelligenz investieren damit man unnötige Speicherkopierungen vermeidet, also Daten im Speicher hin&her zu kopieren. Diesen Aufwand muß man ebenfalls berücksichtigen und kann mit dem Aufwand der Addition gleichgesetzt werden.

Gruß Hagen