Ich möchte eine möglichst schnelle Möglichkeit finden, zwei kleine boolesche Matrizen zu multiplizieren, wobei klein bedeutet, 8x8, 9x9 ... 16x16. Diese Routine wird sehr oft verwendet, daher muss sie sehr effizient sein, also schlage bitte nicht vor, dass die einfache Lösung schnell genug sein sollte.
Für die Sonderfälle 8x8 und 16x16 habe ich bereits ziemlich effiziente Implementierungen, basierend auf Lösung hier gefunden , wobei wir die gesamte Matrix als uint64_t bzw. uint64_t[4] behandeln. Das ist auf meiner Maschine etwa 70-80 mal schneller als die einfache Implementierung.
Jedoch im Falle von 8 & lt; k & lt; 16, ich weiß nicht wirklich, wie ich irgendeine vernünftige Darstellung nutzen kann, um so schlaue Tricks wie oben zu ermöglichen.
Im Grunde bin ich offen für irgendwelche Vorschläge, die jede Art von Repräsentation (der Matrizen) und Funktionssignaturen verwenden. Sie können davon ausgehen, dass dies entweder auf eine 32-Bit- oder 64-Bit-Architektur abzielt (wählen Sie, was am besten zu Ihrem Vorschlag passt)
Gegeben zwei 4x4 Matrizen a = 0010.0100.111.0001, b = 1100,0001,0100,0100, könnte man zuerst die Transponierte b '= 1000,1011,0000,0100 berechnen.
Dann wird die resultierende Matrix M (i, j) = a · b mod² == popcount (a [i] & amp; b [j]) & amp; 1; // oder Parität
Daraus ergibt sich, dass die Komplexität nur in n ^ 2 wächst, solange der Bitvektor in ein Computerwort passt.
Dies kann mindestens für 8x8-Matrizen beschleunigt werden, vorausgesetzt, dass einige spezielle Permutations- und Bitauswahloperationen verfügbar sind. Man kann genau N mal mit NxN Bits in einem Vektor iterieren. (also 16x16 ist so ziemlich das Limit).
Jeder Schritt besteht aus Akkumulieren, d. h. Ergebnis (n + 1) = Ergebnis (n) XOR A (n). & amp; B (n), wobei Ergebnis (0) = 0, A (n) ist A & lt; & lt; & lt; n und '& lt; & lt; & lt;' == Spaltenförmige Drehung von Elementen und wobei B (n) diagonale Elemente von der Matrix B kopiert:
%Vor% Und wenn wir es ein wenig weiter überlegen, ist eine bessere Option, ^^^ (zeilenweise rotieren) Matrix B und wählen Sie A (n) == Spalte kopierte Diagonalen von A:
BEARBEITEN Um späteren Lesern zu helfen, würde ich die vollständige Lösung für W & lt; = 16-Bit-Matrix-Multiplikationen in tragbarem C vorschlagen.
%Vor%Tags und Links optimization c matrix-multiplication