Multiplication de vecteur masortingciel binary
Je veux multiplier une masortingce binary 8×8 représentée par un entier non signé de 64 bits par un vecteur de 8 bits représenté par un caractère non signé. Cependant, en raison d’autres problèmes, la masortingce doit être ordonnée par colonnes. Par conséquent , il n’y a pas de correspondance facile d’octets pour une multiplication facile.
Une idée de comment accélérer un tel calcul? Chaque opération compte car j’ai besoin de milliards de calculs de ce type.
Les multiplications sont effectuées sur un champ de 2 éléments (F-2).
- Comment conserver l’ordre des éléments de même priorité dans une queue de priorité implémentée en tant que tas binary?
- En C bits, multiplier par 3 et diviser par 16
- Explication de la conversion int en binary
- Correspondance des modèles binarys en C
- Convertir Hex en Binaire en C
- Effectuer des opérations arithmétiques en binary en utilisant uniquement des opérateurs au niveau du bit
- Pourquoi unsigned int x = -1 et int y = ~ 0 ont-ils la même représentation binary?
- Comment convertir un caractère en binary?
- Afficher la représentation binary d’un nombre en C?
- Comment convertir une chaîne hexadécimale en chaîne binary en C
Avec cette représentation masortingcielle et vectorielle, cela facilite la multiplication masortingcielle:
(col 1 … col 8 ) * (v 1 … v 8 ) T = col 1 * v 1 + … + col 8 * v 8
où masortingce A = (col 1 … col 8 )
et vecteur de colonne v = (v 1 … v 8 ) T
En pensant plus loin, vous pouvez faire toutes les multiplications en même temps si vous gonflez le vecteur 8 bits en un vecteur 64 bits en répétant chaque bit 8 fois, puis en calculant P = A & v_inflated . Il ne rest plus alors que l’addition (c’est-à-dire XOR) des produits.
Une approche simple pour XORing les produits est.
uint64_t P = calculated products from text above; uint64_t sum = 0; for( int i = 8; i; --i ) { sum ^= P & 0xFF; P >> 8; }
Vous avez seulement 256 vecteurs! Utilisez les tables de recherche pour générer les bons masques, votre logique ressemblera à quelque chose comme
output_bit_n = bool (masortingx [n] & lookup [vector])
En d’autres termes, votre table de correspondance peut transposer une valeur de 8 bits dans le monde 64 bits.
Vous pouvez efficacement intégrer cela dans le résultat avec des instructions de rotation avec report si le compilateur n’est pas assez intelligent pour optimiser (value<<=1)|=result .