Fragen? Antworten! Siehe auch: Alternativlos
Bisher habe ich bloß Addition und Multiplikation implementiert, noch nichts mit Modulo und Potenzieren, aber das kommt noch. Modulo ist für Addition hauptsächlich ein Vergleich und eine Subtraktion von einer kleineren Zahl (beides relativ trivial) und bei Multiplikation führt man das auf das Additions-Modulo zurück, weil Divisionen echt teuer sind. Potenzieren ist letztlich einfach nur häufig Multiplizieren, insofern wende ich mich dem zu, wenn ich mit meiner Multiplikation zufrieden bin. Das Modulo macht man beim Potenzieren immer nach jeder Multiplikation, sonst werden die Zwischenwerte zu unhandlich.
Jedenfalls ist meine Additions gerade Weltmarktführer, und meine Multiplikation spielt immerhin in der selben Liga wie die anderen. Da ist das letzte Wort noch nicht gesprochen, aber letztlich hoffe ich, daß es da tolle Tools gibt, die mir da beim Unrollen und Scheduling helfen können.
Ein kleines Zwischenergebnis kann ich aber schon mal mitteilen hier, was ich heute gelernt habe: Zeigerarithmetik ist langsamer als Indizieren auf x86 und AMD64 (zumindest bei AMD). Wenn man in einer Schleife ständig die Zeiger hochzählt, dann schafft das künstliche Abhängigkeiten, billiger ist es da, die erweiterten Adressmodi zu benutzen, z.B. movq (%rsi,%rcx,8),%rax. Wenn man die Reihenfolge der Schleife nicht einfach umkehren kann (bei der Addition z.B.), dann ist es immer noch billiger, wenn man vor er Schleife die Arraygröße zu den Zeigern dazu zählt, dann rcx negiert, und in der Schleife immer einen draufzählt statt abzieht, und dann guckt, ob es jetzt Null ist. Erstaunlich, aber das hat meine Addition von 84 Zyklen auf 73 reduziert bei zwei 1024-Bit Zahlen, und das ist ja kein Pappenstiehl. Wenn das hier jemanden interessiert, kann ich ja noch ein paar Sachen bloggen, die ich so gelernt habe dabei bisher.