Probleme du bit parfait

[acadet]

Proposé par mon CTO. Je n'ai pas encore trouvé une solution viable. Matthieu va apprécier.

---

Soit une fonction p(x) retournant true si et seulement si the nombre de bits a 1 en represation binaire d'un nombre x est un carre parfait, ou retourne false sinon. Par exemple:

p(0) # binaire est "0", 0 1's, 0 n'est pas un carre parfait 
=> false

p(1) # binaire est "1", 1 1, 1 est un carre parfait
=> true

p(23) # binaire est "10111", 4 1's, 4 est un carre parfait
=> true

p(24) # binaire est "11000", 2 1's, 2 n'est pas un carre parfait
=> false

Ecrire une fonction bits_parfaits(a, b) qui retourne le nombre d'entiers dans l'intervalle [a, b] pour lesquels p(x) retourne vrai.

Par exemple :

bits_parfaits(1645098712823793798, 14889998042940624528)
=> 1070002673201129717

[FoxCie]

Il y a une solution pour compter le nombre de bits à 1 en temps logarithmique, du moment que tu peux faire un calcul sur le nombre en tant constant (en gros, si t'as un processeur 64 bits, tu peux le faire en temps logarithmique sur 64 bits). L'idée c'est en gros de compter par paquets, tu stockes le nombre de bits à un dans des paquets de 1 bit au début, donc c'est OK, si ton ième bit est à 1, c'est que t'as 1 bit à 1 dans ton ième paquet, s'il est à 0 t'en as 0, et après tu doubles la taille du paquet en continuant grâce à des bitmasks (du genre 0x55555555555, 0x33333333333). Je pourrais essayer de retrouver l'algo si ça t'intéresse.

Mais c'est pas sûr que ça t'intéresse, parce que je suis pas sûr que tu puisses faire 1070002673201129717 opérations rapidement, même si c'est du temps constant (logarithmique sur 64 bits, donc on va dire constant), donc faire un algo naïf en temps linéaire ça semble pas terrible.

Du coup, une solution probablement un peu relou à mettre en place, mais peut-être pas tant que ça, c'est de considérer l'ordre sur les entiers naturels au niveau binaire, pour pouvoir considérer tous les nombres dans ton intervalle facilement. Ensuite, tu comptes le nombre de bits minimal et maximal d'un nombre dans cet intervalle, et tu cherches les carrés parfaits dans cet intervalle (comme il est compris dans [0;64] il y en a pas tant que ça). Après, c'est juste une question de dénombrement des permutations. Mon idée, c'est qu'en gros tu te fous de savoir quels nombres retournent vrai ou faux, tu veux juste savoir combien ils sont. Du coup, imagine que tu aies comme bornes (je prends celles-là parce que c'est facile) 0 et 10, en binaire ça fait 0000 et 1010, donc dans l'intervalle [0;10], t'as toutes les permutations des trois premiers bits plus 1000, 1001 et 1010. Les carrés parfaits possibles sur 4 bits, c'est 0 (oui, 0 c'est un carré parfait, je suis désolé, mais 0 * 0 = 0), 1 et 4. 1111 est pas dans l'intervalle, donc y aura pas de nombre avec 4 bits à 1. Du coup on cherche les nombres de notre intervalle qui n'ont que 1 bit à 1. On a dit que notre intervalle comprenait toutes les combinaisons des trois premiers bits, donc t'as 1 parmi trois = 3 combinaisons qui ont un seul bit à 1, plus le nombre 1000, donc au total il y en a 4.

Le truc relou dans cette méthode, c'est de représenter l'intervalle comme il faut, mais ça doit être possible de se ramener à des cas où la borne inf est toujours 0 (perfect_bits(a, b) = perfect_bits(0, b) - perfect_bits(0, a), avec +-1 d'erreur si c'est vrai pour a ou une connerie du genre). Même avec ça, ça reste assez chiant, mais il doit y avoir moyen de faire un truc avec la puissance de deux supérieure pour la borne sup (en gros t'aurais une erreur de 1 bit selon que t'es dans ton intervalle ou non).

A mon avis c'est un des moyens les plus rapides pour faire ça (calculer les combinaisons, c'est pas très compliqué), mais avoir une implémentation correcte doit demander un peu plus de réflexion que celle que j'ai eue (j'ai tout fait de tête, c'est peut-être un peu voire carrément faux), si tu veux que je me penche un peu plus dessus, dis le moi je prendrai un papier et un crayon =).

EDIT : quand je dis 4 dans mon exemple, je veux bien sûr dire 5, vu qu'il y a 0...

[acadet]

T'es sur la bonne piste Matthieu ! J'ai eu la même idée. Tout d'abord je calcule les carrés parfaits sur un petit intervalle, comme tu l'as expliqué.

Ensuite j'utilise également les combinaisons (coefficient binomiaux). Malheureusement, je suis seulement en mesure de calculer le nombre de carrés parfaits sur des intervalles ayant comme bornes des puissances de 2. Par exemple [2**100, 2**150].

Mais pas sur n'importe quel intervalle d'entiers :disappointed:... Mon unique solution est de retirer un à un chaque carré jusqu'à la puissance de 2 la plus proche, ce qui est horrible pour des gros nombres, évidemment. J'ai eu beau chercher, je n'ai pas trouvé de solutions pour trouver le nombre de combinaisons restantes sur un intervalle de la forme [60, 2**6] ou [2**3, 10].

Par ailleurs, je n'attend pas de toi que tu m'aides à résoudre mon problème :) c'était juste pour partager cette énigme avec vous !

[FoxCie]

J'ai un peu le même problème (du coup je me suis fait nerd snipe =) http://xkcd.com/356/ ), je considère seulement des intervalles du genre [0;n], et mon truc fonctionne seulement quand n est une puissance de 2 (du coup, si tu donnes [2a;2b] ça va fonctionner en calculant [0;2b] - [0;2a], y a peut être un léger décalage à régler pour ça, mais je pense que c'est correct). Du coup, je me retrouve aussi à devoir trouver le nombre de combinaisons restantes après la plus grande puissance de 2, j'ai pas encore trouvé comment faire. Je te tiens au courant si j'y arrive :)

EDIT : Bizarrement, dans leur truc ils semblent effectivement considérer que 0 n'est pas un carré parfait. Faudrait qu'ils m'expliquent pourquoi. Ca change pas grand chose, faut juste ajouter 1 à chaque fois, mais je vois pas pourquoi ça n'en serait pas un.

[FoxCie]

J'ai trouvé une solution, mais l'implémentation ne fonctionne pas pour des (très) grands nombres, je soupçonne un overflow quelque part, peut-être dans le calcul des combinaisons. Si tu veux ma solution, dis le moi.

EDIT : ça fonctionne bien en fait, j'utilisais un int au lieu d'un long dans ma fonction qui calcule les combinaisons, du coup y avait bien un overflow. Maintenant ça marche nickel =)

[acadet]

Merci pour ta solution Matthieu ! Explications et implémentation très claires :) Je n'avais pas pensé à cette récursion, en effet.

[acadet]

J'ai ajouté la solution de mon boss. Très proche de la tienne Matt.