Enigme Preuve d’algorithme, le retour @ Prise2Tete

scarta · #1

Après avoir lu l’énigme précédente, un programmeur malin se dit: « tiens, on m’a demandé une fonction qui renvoie 0 si le nombre de bits à 1 est pair et 1 sinon, je vais m’en inspirer ». C’est, autrement dit, une fonction qui renvoie le résultat du popcount précédent, modulo 2: il pense d’abord à rajouter un « & 1 » tout à la fin, ce qui lui garantit un résultat correct et somme toute assez rapide.

Mais ! En lisant les explications de LeJeu et de scarta, il réalise que l’histoire de la multiplication pour additionner des trucs en parallèle c’est vraiment bien trouvé ! Et du coup, il écrit :

Code:

int parity(unsigned long number) {
    return (number * 0xFFFFFFFFFFFFFFFF) >> 63;
}

Ainsi, tous les bits se retrouvent additionnés au niveau du tout premier bit, ok ça déborde mais c’est pas grave il ne lui faut que le bit de poids faible donc ça passera.

Question(s):
* prouver que cette fonction est correcte si c’est le cas, ou expliquer pourquoi elle ne l’est pas sinon, et donner dans ce cas un contre exemple.
* si cette fonction devait s’avérer incorrecte, essayer d’en trouver une autre qui soit aussi efficace que possible (avec, comme base, popcount modulo 2, qui est déjà pas mal rapide).

Bon courage !

gwen27 · #2

Ton truc ne tient pas compte des retenues.
Je ne comprends rien à popcount, mais quelque chose qui marcherait sans être forcément plus rapide serait de faire :

nombre=nombre xor nombre//2^32 ( // étant la division entière qui revient à ton >>
puis idem avec 2^16, 2^8, 2^4, 2^2, 2

Le bit de poids faible serait bon, le nombre obtenu serait même exact avec :
nombre=nombre%2^32 xor nombre//2^32

scarta · #3

Effectivement ça ne marche pas à cause des retenues.

Par contre ce que tu proposes c’est 6 étapes de 3 opérations chacune (je prends celle qui donne le résultat sur le bit de poids faible, sinon c’est encore plus), soit 18 au total: le popcount présenté à l’énigme précédente, même en ajoutant un modulo 2, c’est moins que ça.

L’avantage de popcount c’est de faire des opérations en parallèle sur des paquets de bits, mais en une seule opération à chaque fois. Ici on a effectivement un problème de retenue, mais ne pourrait-on pas trouver la « bonne » taille de paquets qui évite les problèmes de retenue, tout en évitant de faire 6 étapes successives ?

gwen27 · #4

Sur le net, on trouve :
(((n * 0x0101010101010101) & 0x8040201008040201) % 0x1FF) & 1;

scarta · #5

Curieux 🧐 je n’aurais pas écrit ça comme ça. Je vais me pencher dessus et regarder pourquoi ça marche…

scarta · #6

Comme je n'arrivais toujours pas à comprendre pourquoi ça marche, j'ai essayé de montrer pourquoi ça pourrait "ne pas marcher". Et pour ça, j'ai cherché un contre exemple, c'est plus simple.

Pour ça, il est est très utile de bien comprendre ce qui est fait.

Déjà, n * 0x0101010101010101
- coupe n en 8 blocs de 8 bits
- de droite à gauche, on aura le dernier bloc, puis la somme des deux derniers, puis la somme des 3 derniers, etc…; les éventuelles retenues d’un bloc sont ajoutées au bloc qui est à sa gauche.

Ensuite, n & 0x8040201008040201
- considère toujours des blocs de 8 bits
- de gauche à droite cette fois, ne garde que le premier bit du premier bloc, le second du second bloc, … et tous les autres sont à 0.
Autrement dit, puisque l’écart entre deux bits ciblés est de 9, on a une somme de termes de la forme n_9k * 2^9k pour k compris entre 0 et 7

Etape suivante, n % 0x1FF
- 0x1FF vaut 511, soit 2^9-1
- 2^9 vaut 1 modulo 0x1FF, et 2^9k vaut 1 aussi du coup.
- chaque terme n_9k * 2^9k vaut tout simplement n_9k
- et donc pour finir, n% 0x1FF est la somme des bits d’indices 9k, pour k compris entre 0 et 7
(remarque : il est possible de faire plus efficace pour cette étape je pense…)

Dernière étape, n & 1: on ne prend que le dernier bit, donc la parité.

Pour trouver un contre exemple simple, on peut tout simplement chercher un 2^n (qui devrait donner comme résultat 1, logiquement), et qui va donner 0 après les 2 premières étapes.

Si on prend 2^i pour i entre 0 et 7 (les 8 bits les plus à droite), il sera répété dans chaque bloc (la multiplication va simplement répéter ces 8 bits 8 fois), et il y a forcément un de ces blocs (le numéro i, de droite à gauche) qui contiendra 1 à la position i relativement à ce bloc, et c’est précisément ce que prend l’opération and.

Par contre, 2^8… après multiplication, en prenant des blocs de 8 bits, ils valent tous 1, sauf le dernier qui vaut 0. Et donc le “peigne” du AND ne ramasse rien. Résultat : 0, et un modulo et la suite n’y changeront rien.

On peut vérifier par acquis de conscience : 2^8 = 256 = 0b100000000 = 0x100
0x100 * 0x0101010101010101 = 0x0101010101010100 (on ajoute 2 zéros à droite - et du coup on tronque deux chiffres à gauche)
0x0101010101010100 & 0x8040201008040201 = 0 (comme attendu)
0 % 0x1FF = 0
0 & 1 = 0

Conclusion: ce qu’on trouve sur le net n’est pas toujours… très net

scarta · #7

Toutefois, comme expliqué plus haut, pour tous les 2^i pour i entre 0 et 7, et plus généralement pour n entre 0 et 255, il n’y a pas de problème.
Et dans ce cas, on peut même expliquer pourquoi ça marche: on a un bloc de 8 bits, on le répète 8 fois, et on ne garde dans chaque bloc que le 1er bit du 1er bloc, le 2nd du 2nd, etc…, puis arrive le modulo qui comme on l’a dit additionne les bits qu’on a gardé, et enfin le &1 pour la parité.

C’est donc une fonction qui marche très bien, pour des chars uniquement et pas des unsigned long.

Comme je le disais plus haut, on peut quand même faire mieux que le modulo ! Une autre multiplication, par le même 0x8040201008040201 va sommer ces mêmes bits et les mettre dans le bit tout à gauche (le reste déborde)

Avec la méthode postée plus haut, si on teste toutes les valeurs un million de fois
./parity1.out 1.77s user 0.00s system 82% cpu 2.144 total

Si on change le code ainsi :

Code:

 
int parityTest2(unsigned char number) {
    return (((number  *  0x0101010101010101) & 0x8040201008040201) * 0x8040201008040201) >> 63;
}

On obtient beaucoup plus rapide:
./parity2.out 0.54s user 0.00s system 57% cpu 0.941 total

scarta · #8

Pour en revenir au problème initial, je propose:

Code:

int parity(unsigned long number) {
        number = (number << 1) ^ number;
        return ((((number << 2) ^ number) & 0x8888888888888888) * 0x1111111111111111) >> 63;
}

Je vous laisse prouver que ça marche

LeJeu · #9

Bonjour Scarta je ne lis ta question que bien tard :

Code:

int parity(unsigned long number) {
        number = (number << 1) ^ number;
        return ((((number << 2) ^ number) & 0x8888888888888888) * 0x1111111111111111) >> 63;

Le calcul se fait sur quatre bits ( 16 fois en //)

le premier calcul : (number << 1) ^ number :
à partir de 4 bits a b c d on obtient (a^b) ( b^c) ( c^d) x
ce qui est important est le (a^b) en 1 et le (c^d) en 3 ( le 4 est indéterminé)

le deuxième calcul (number << 2) ^ number :
donne comme 1bit des quatre (c^d)^(a^b)

ce qui est la parité du nombre de 1 des 4 bits ( 1 si impair)

à partie de là tout se déroule comme on le connait déjà :
le calcul & 0x8888888888888888)
ne conserve que le 1 bit de la série de 4 bits

le calcul *0x1111111111111111 :
fait la somme de ces 16 bits dans le 1°

le calcul >> 63 :
récupère ce bit !

LeJeu · #10

Scarta

je trouve ce code sur https://fr.wikibooks.org/wiki/Les_op%C3 … imis%C3%A9

Code:

unsigned ParityBit (unsigned x)
{
    x ^= (x >> 32) ;
    x ^= (x >> 16) ;
    x ^= (x >> 8) ;   
    x ^= (x >> 4) ;
    x ^= (x >> 2) ;
    x ^= (x >> 1) ;

    return x & 1 ;
}

qui n'est pas trop mal ?

gwen27 · #11

C'est ce que je proposais en premier.
Même pas besoin du &1

LeJeu · #12

Oups, pardon Gwen27, j'avais lu trop vite le début du thread !

gwen27 · #13

Pas de souci, scarta semble dire que c'est chronophage, avec son langage et sa vision des choses, mais je ne suis pas convaincu par la différence de temps.
Ce n'est peut-être pas optimal en terme de temps, mais ça l'est en terme de simplicité et ça doit se jouer dans u mouchoir de poche.

scarta · #14

En termes de cycles CPU, il y en a quand même quelques uns en plus.
Accessoirement le &1 final est bien nécessaire il me semble.

Le mouchoir de poche n'est pas si petit que ça. Pour un milliard de nombres aléatoires :

Code:

./1B_noop.out  9.23s user 0.01s system 99% cpu 9.246 total
./parity1.out  9.86s user 0.01s system 99% cpu 9.877 total
./parity2.out  10.69s user 0.01s system 99% cpu 10.703 total

Le noop ne fait rien, c'est l'étalon, qui génère un milliard de nombres aléatoires (ce qui en soit prend du temps).
Le parity1 c'est celui que je proposais. 63 centièmes de seconde pour un milliard de calculs (une fois qu'on enlève le temps de la génération, donné par noop)
Le parity2, c'est les 6 xor successifs, et ça met 1.46 secondes.

C'est vrai que sur un calcul unique, on a une différence inférieure à une nano-seconde.
Mais il ne faut pas considérer la différence, il faut considérer le rapport: le second est en moyenne 2,3 fois plus long

scarta · #15

D'ailleurs, en comptant les opérations, on a le même ratio de 2.3

Code:

unsigned ParityBit (unsigned x)
{
    x ^= (x >> 32) ;  // 3 étapes: le >>, le xor et le =
    x ^= (x >> 16) ; // 3 autres
    x ^= (x >> 8) ;   // 3 autres
    x ^= (x >> 4) ;// 3 autres
    x ^= (x >> 2) ;// 3 autres
    x ^= (x >> 1) ;// 3 autres

    return x & 1 ; // et une dernière, le and, total: 19
}

Et l'autre :

Code:

int parity(unsigned long number) {
        number = (number << 1) ^ number; // 3 opérations
        return ((((number << 2) ^ number) & 0x8888888888888888) * 0x1111111111111111) >> 63; //un <<, un xor, un and, un mult et un >>: 5 opérations, total: 8
}

Et 19/8 = 2,375 qui est environ le ratio qu'on retrouve de manière expérimentale.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 25-04-2024 23:41:24

przuve d’algorithme, le retour

Code:

#0 Pub

#2 - 27-04-2024 21:10:10

preuve d’algorithmz, le retour

#3 - 28-04-2024 01:15:51

Preuve d’algoritmhe, le retour

#4 - 28-04-2024 08:53:37

preuve d’alforithme, le retour

#5 - 30-04-2024 23:35:57

Preuve d’algorithme,, le retour

#6 - 02-05-2024 15:42:18

preuve d’algorithme, le tetour

#7 - 02-05-2024 15:51:18

reuve d’algorithme, le retour

Code:

#8 - 02-05-2024 16:30:40

Preuve da’lgorithme, le retour

Code:

#9 - Hier 08:51:40

Preuve d’aalgorithme, le retour

Code:

#10 - Hier 10:44:11

Preuve d’algorithhme, le retour

Code:

#11 - Hier 14:57:48

rPeuve d’algorithme, le retour

#12 - Hier 17:13:47

Preuve d’lgorithme, le retour

#13 - Hier 19:21:13

preuve d’algorithme, le rerour

#14 - Hier 23:44:54

Preuve d’algorihtme, le retour

Code:

#15 - Hier 23:50:25

Preuvve d’algorithme, le retour

Code:

Code:

Réponse rapide

Sujets similaires

Pied de page des forums