Vad är snabbaste sättet att köra vektormultiplikation med XOR-operatören?
Antar att du har en matris A som har M rader och N kolumner.
Matrisen A har datatypen osignerad 8-bit, dvs uint8_t.
Vi tar en vektor x som har dimensionen N (längd N) och multiplicerar den med matrisen A så kommer vi få vektorn y.
y = A*x
Men här har jag tänkt att använda mig av XOR. Detta betyder att om y är 0, så kommer vektorn x vara identisk en viss rad på matrisen A.
y = A^x
Frågor:
För att få detta så optimalt som möjligt, så bör matrisen A ha så stor datatyp som möjligt, t.ex. uint64_t eller högre, om det finns.
1. Har alla moderna C kompilatorer stöd för uint64_t eller högre?
2. Vad händer om en hårdvara har inte stöd för 64-bit?
3. Har ARM stöd för 64-bit? Lite mera specifika processorer: Cortex-M3 och Cortex-M4
4. Vad är det absolut snabbaste sättet att utföra XOR multiplikation?
Vi kan ta ett exempel där vi multiplicerar en rad i A med vektorn x
#include <stdio.h>
typedef unsigned long long uint64_t;
typedef uint64_t size_t;
#define N 4
int main(){
/* Skapa en rad i matrisen A */
uint64_t A[N] = {255, 65535, 511, 1023};
/* Skapa vektor */
uint64_t x[N] = {255, 60000, 510, 1000};
/* Iterera array */
size_t i;
for(i = 0; i < N; i++){
printf("%i\n", (int) A[i] ^ x[i]);
}
return 0;
}
Utskriften blev:
0
5535
1
23
Men är detta optimalt att göra så?
För i praktiken så ska jag jämföra talen med varandra.
#include <stdio.h>
typedef unsigned long long uint64_t;
typedef uint64_t size_t;
#define N 4
int main(){
/* Skapa en rad i matrisen A */
uint64_t A[N] = {255, 65535, 511, 1023};
/* Skapa vektor */
uint64_t x[N] = {255, 65535, 511, 1023};
/* Iterera array */
size_t i, j;
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
printf("%i\t", (int) A[i] ^ x[j]);
}
printf("\n");
}
return 0;
}
Utskrift:
0 65280 256 768
65280 0 65024 64512
256 65024 0 512
768 64512 512 0
Syftet är att veta vid vilket index är ett element i vektorn x likadant som ett element i matrisen A.
Men detta är O(N^2) komplexibilitet. Om jag ska testa flera rader i matrisen A, dvs om raderna M togs med i uppgiften, så kommer jag få tre stycken for-satser, vilket är O(N^3) komplexibilitet och nu börjar vi tala om oeffektivt.
Så vad är snabbaste sättet?
