On pourrait sous-titrer cet article « Pour en finir avec la binarité de la dichotomie ». L’auteur fait sortir cette méthode classique de résolution de problèmes au lycée des sentiers battus, la frottant à la notion de complexité algorithmique pour mieux mettre en avant sa richesse souvent ignorée.
Tout commence par des déménageurs qui jettent des pianos par les fenêtres d’un immeuble. Et qui veulent, en minimisant les essais, déterminer à partir de quel étage la méthode aboutit à la destruction de l’instrument.
La démarche débute par un petit algorithme de recherche dichotomique de l’étage fatal, celui-ci est testé. Se termine-t-il ? Juste ? Et à quelle vitesse ? Les réponses sont oui, oui et, pour un immeuble de 1024 étages, à peu près cent fois plus vite que des essais en remontant !
L’auteur nous informe alors d’un petit bug de Java, qui recelait une erreur dans le code d’une bibliothèque utilisée pour la recherche dichotomique et nous invite à rectifier notre algorithme en conséquence. Pour prendre en compte la spécificité du codage des entiers sur 64 bits et pour le cas où l’immeuble aurait plus de 263-1 étages (on a pris comme hypothèse de départ que le nombre d’étages est une puissance de 2), ce qui sera courant dans un futur proche.
Pour conclure cette première partie le lecteur est invité à réfléchir sur quelques questions annexes comme le risque de pénurie de pianos pour les tests. Tout va bien, l’algorithme reste performant.
C’est le moment choisi par l’auteur pour nous ramener à notre réalité, un peu plus scolaire dirons-nous et surtout de laquelle (pour la plupart) les pianos sont absents.
Pour commencer la dichotomie ne permet pas de tout améliorer, un exemple utilisant la multiplication de deux entiers le prouve ; couper les nombres en deux n’accélère pas le calcul !
Et quel rapport avec la recherche des solutions d’une équation réelle ? Si l’on cherche notre solution dans un intervalle, que l’on fixe la précision désirée, notre solution sera l’étage parmi le nombre d’étages de possibilités. Passer du piano cassé à un test de valeur ne pose aucune difficulté.
On arrive alors au cœur de l’article, l’étude de la complexité sur machine. C’est à dire le calcul du temps de résolution d’un problème par une machine, ou plutôt du temps d’exécution des instructions qui aboutissent à cette résolution.
A partir d’un petit problème très simple, l’auteur commence tout d’abord par une partie expérimentale. La résolution du problème est codée en Python puis en C. Le temps de calcul est relevé en fonction de la taille de l’échantillon de départ, une formule est établie pour les deux langages qui est fonction du cube de cette taille multiplié par une certaine constante. C l’emporte grâce à sa constante, il est environ 400 fois plus rapide que Python ! Le but est d’optimiser le code, hélas même en C bien des choses restent cachées.
Nous passons alors à l’approche plus théorique avec l’analyse mathématique, le but étant d’optimiser le code, en Python comme en C. Et la conséquence est finalement assez simple.
Pour conclure l’article, l’auteur nous emmène du côté de l’algorithme d’Héron, avec quelques exemples de code pour déterminer une approximation de la racine carrée d’un entier positif. Cet algorithme donne une très bonne précision très rapidement.
Pour terminer l’auteur nous indique la bibliographie de l’article ; elle est très conséquente et permettra à ceux qui le désirent d’approfondir le sujet.