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:
Output:
Prozedur:
Edit: Fehler gefunden, in meiner ersten Code-Zeile stand ein "+" anstelle eines "*"..
[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:
- Initialisiere carry=0 und c mit doppelter Bitlänge, als die betrachtete Basis "B" (hier 2^32)
- 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;
- Berechne array[1] = a_0*b_1 + a_1+b_0 (round i=1)
- 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
- Berechne array[2] = a_0*b_2 + a_1*b_1 + a_0*b_2
- 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: