Problem mit dem Verständnis einer Messung

EDIT: Fehler hat sich geklärt. Das Compilat war nicht sauber und es war wohl noch im arr16 Modus.. Jedenfalls ist das Ergebnis zum Gunsten von arr4 ausgefallen: 5kk vs 700k.


Hey,

ich habe eine Funktion definiert, das ist die Karazuba Multiplikation. Die Definition ist Rekursiv.

Alles was für diese Funktion benötigt wird, ist in der Datei kara.c zu finden.

Nun habe ich zwei Operationen: Zwei Arrays der Länge 4*11 (arr4) und zwei der Länge 16*11 (arr16). Diese werden jeweils miteinander multipliziert, wie Polynome.

In der Datei arr4.c eine Multiplikation so definiert, dass sie karazuba aufruft. Die Funktion arr16_mult ist in kara.c definiert.

Code:
void arr4_mult(arr4 A, arr4 B, arr4 C)
{
    karazuba(A,B,C,4,2,0);
}

void arr16_mult (arr16 A, arr16 B, arr16 C)
{
    karazuba(A,B,C,16,4,0);
}

Zur Erklärung der Eingaben: @arr16: 16 = Länge des Arrays, 4 = Anzahl der Runden, 0 aktuelle Rekursionstiefe.
@arr4: entsprechend arr16, mit kleineren Werten.

In einer Testdatei teste ich die arr4_mult vs. arr16_mult. Die Ergebnisse sind, dass arr4_mult ca. 200k mehr cycles braucht, als arr16_mult. Wie kann man das erklären?

Beschreibung: In arr4_mult habe ich nur 2 rekursionsstufen und nur 2x 4 Einträge. Bei arr16_mult sind es 4 Rekursionsstufen und 2x 16 Einträge.


Dieser Polynom-Multiplikationsalgorithmus zerlegt die Arrays in zwei: Low und High mit jeweils der Hälfte der Bytes. Anschließend werden diese erneut in Karazuba eingeworfen, mit kleinerer Länge. Beispiel:

Input A,B
Prozedur:
A = A0 || A1
B = B0 || B1

karazuba(A0, B0, C0); // C0 = A0 * B0
karazuba(A1, B1, C2);
karazuba( A0+A1, B0+B1, C1 );

C = C0 + C1 b^n + C2 b^2n
(wobei b die Basis der Zerlegung und n der Grad des Polynoms +1 halbe ist. also bei arr4 ist n=2, arr16 ist n=8)
Insgesamt ist der Algo etwas komplexer, aber so funktioniert er vereinfacht.
 
Zuletzt bearbeitet:
Zurück
Oben