Multiplikation zweier grosser Zahlen in Darstellung als Array mit Übertrag

Hey, hier zunächst der Code [1], ich konnte hier leider den Code nicht posten, die Code-Umgebung hat alle Zeilenumbrüche entfernt. Ich sehe den Fehler einfach nicht.


[1] finite fields - Most efficient way to compute products of polynomials of same degree n - Mathematics Stack Exchange

Ich gebe mal eine funktionelle Beschreibung, wie der Code arbeitet.

Input:
  • A = [ a_0, a_1, a_2 ]
  • B = [ b_0, b_1, b_2 ]

Output:
  • array = [ array[0], array[1], array[2] ] = {0}, (A*B hat die Länge 5-6, die niedrigen Werte landen in array, die hohen in carry_array)
  • carry_array (fehlt)

Prozedur:
  1. Initialisiere carry=0 und c mit doppelter Bitlänge, als die betrachtete Basis "B" (hier 2^32)
  2. Berechne array[0] mit Übertrag=carry (round i=0)
    • speichere in c: c = a_0 * b_0
    • Zerlege c in zwei Teile bzgl. der gewählten Basislänge B in left und right. Dabei sind "left" die linken 32-Bits und "right" die rechten. Das LSB ist most-right.
    • Addiere "left" zu carry;
    • Speichere array[0] = right
    • Zerlege carry in "carry2" (linken 32-Bit) und "carry1" (rechten 32-Bit). Carry2 wird in zwei Runden gebraucht, carry1 in der nächsten direkt.
    • carry = 0;
  3. Berechne array[1] = a_0*b_1 + a_1+b_0 (round i=1)
  4. h=0; j=i(=1);
    • c = a_h * b_j = a_0*b_1
    • zerlege c in left und right
    • carry += left (Speichere den Übertrag der Multiplikation im Carry)
    • c = right + carry1 + array[1] (Summiere right, + Übertrag aus Runde 0 + bisher in array[1] hinterlegten Wert, in Runde 1 =0)
    • zerlege c in left und right
    • carry += left (Speichere den Übertrag der Addition im Carry)
    • carry1 = 0 (Resette carry1 nach dem ersten Nutzen)
    • array[1] = right
    • h+=1; j-=1; (=> a_1*b_0 in der 2. Runde, 3. Runde existiert nicht)
    • wiederhole (a-i) so lange j >= 0
    • carry += carry2
    • zerlege carry in carry2 und carry1, wie in 1.e
    • carry = 0
  5. Berechne array[2] = a_0*b_2 + a_1*b_1 + a_0*b_2
  6. starte 2. mit h=0 und j=2 und wiederhole so lange, bis j=0.


Edit: Fehler gefunden, in meiner ersten Code-Zeile stand ein "+" anstelle eines "*"..
 
Zuletzt bearbeitet:
Zurück
Oben