|
#1 - 25-04-2024 23:41:24
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
Preuve d’algorithmme, le retour
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 :
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 !
#2 - 27-04-2024 21:10:10
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,986E+3
Preuve d’lgorithme, le retour
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
#3 - 28-04-2024 01:15:51
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
Preuve d’agorithme, le retour
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 ?
#4 - 28-04-2024 08:53:37
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,986E+3
preuve d’algorithme, le retout
Sur le net, on trouve : (((n * 0x0101010101010101) & 0x8040201008040201) % 0x1FF) & 1;
#5 - 30-04-2024 23:35:57
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
preuve d’algoritjme, le retour
Curieux 🧐 je n’aurais pas écrit ça comme ça. Je vais me pencher dessus et regarder pourquoi ça marche…
#6 - 02-05-2024 15:42:18
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
preuve d’algorithme, le retpur
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
#7 - 02-05-2024 15:51:18
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
Preuve d’algorithme, le retuor
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 :
On obtient beaucoup plus rapide: ./parity2.out 0.54s user 0.00s system 57% cpu 0.941 total
#8 - 02-05-2024 16:30:40
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
Preuve d’algorithme, l retour
Pour en revenir au problème initial, je propose:
Je vous laisse prouver que ça marche
#9 - 04-05-2024 08:51:40
- LeJeu
- Passionné de Prise2Tete
- Enigmes résolues : 25
- Messages : 74
Preuve d’algorithme, le etour
Bonjour Scarta je ne lis ta question que bien tard :
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 !
#10 - 04-05-2024 10:44:11
#11 - 04-05-2024 14:57:48
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,986E+3
Preuve d’algoirthme, le retour
C'est ce que je proposais en premier. Même pas besoin du &1
#12 - 04-05-2024 17:13:47
- LeJeu
- Passionné de Prise2Tete
- Enigmes résolues : 25
- Messages : 74
preuve d’algirithme, le retour
Oups, pardon Gwen27, j'avais lu trop vite le début du thread !
#13 - 04-05-2024 19:21:13
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,986E+3
Preuve d’algrithme, le retour
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.
#14 - 04-05-2024 23:44:54
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
Preuve d’algorithme, le rtour
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 :
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
#15 - 04-05-2024 23:50:25
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1965
preuve d’algorithme, ke retour
D'ailleurs, en comptant les opérations, on a le même ratio de 2.3
Et l'autre :
Et 19/8 = 2,375 qui est environ le ratio qu'on retrouve de manière expérimentale.
|
|