DM2 : Chaînes d'additions

Sujet proposé par Frédéric Chyzak.

L'objectif de ce DM est l'étude de quelques propriétés des chaînes d'additions, un outil qui permet de diminuer le nombre de multiplications employées pour calculer une élévation à une grande puissance, et donc d'accélérer ce calcul. Les premières études sur les chaînes d'additions remontent au 19e siècle et des résultats de calculs sur ordinateurs apparaissaient il y a déjà 30 ans dans le volume 2 du The Art of Computer Programming de Knuth. Des généralisations de cette notion sont maintenant employées en cryptologie.

[Quelques erreurs ou imprécisions ont été corrigées et apparaissent, comme ce paragraphe, entre crochets et normalement en vert. Le 05/05/03.]

Le problème

Le premier algorithme qui ne soit pas naïf auquel on peut penser pour le calcul de puissances est celui de l'exponentiation binaire : par exemple, pour calculer a15, on calcule successivement a2, a3, a6, a7, a14, a15 par b = a2, c = a b, d = c2, e = a d, f = e2, et enfin g = a f, pour un total de 6 multiplications (chaque carré valant pour une multiplication). Ce nombre 6 est-il le nombre minimal de multiplications nécessaires ? En réalité, non, comme le montre le calcul b = a2, c = a b, d = c2, e = c d, f = d e, qui mène à f = a15 en seulement 5 multiplications, en passant par a2, a3, a6, a9, a15.

La notion de chaîne d'additions provient de la suite des exposants dans une suite de calcul comme celle qui précède : une chaîne d'additions pour n est une suite croissante d'entiers

a0 = 1 < a1 = 2 < ... < ai < ... < ak = n,

avec la propriété que chaque entrée de la suite est somme de deux entrées précédentes, éventuellement les deux mêmes.

Vu que la suite ne peut au maximum que doubler d'une entrée à la suivante, la longueur k est au moins logarithmique en n. On vérifie facilement que l'algorithme d'exponentiation binaire fait un nombre de multiplications égal à plafond(log2n) + nu(n) où nu(n) est le nombre de 1 dans l'écriture binaire de n et plafond(x) est l'entier immédiatement supérieur au réel x. Une question intéressante est de comprendre à quel point il est possible de se rapprocher de plafond(log2n).

Calcul de toutes les chaînes d'additions d'un même entier

Quitte à oublier quelle est la décomposition précise de chaque nombre d'une chaîne d'additions comme somme de deux entiers qui le précèdent, une chaîne d'additions peut se représenter par l'ensemble de ses entrées ai. Inversement, d'un tel ensemble, on saura toujours reconstruire une chaîne d'addition, même si des ambiguïtés seront possibles. Par exemple, { 1, 2, 3, 4 } est l'image d'une chaîne d'additions calculant 4, mais on oublie si ce nombre a été obtenu sous la forme 1 + 3 ou 2 + 2.

L'union de deux ensembles représentant deux chaînes d'additions représente donc une nouvelle chaîne d'additions, ce qui fournit l'idée de calcul suivante pour calculer récursivement toutes les chaînes d'additions d'un même entier n : supposons que toutes les chaînes d'additions ont été calculées pour tous les entiers jusqu'à n - 1 [et non pas plafond(n/2), comme indiqué dans la version originale du sujet], alors toute chaîne d'additions pour n qui calcule ce nombre par la somme p + q s'obtient en adjoignant n à l'union d'une chaîne d'addition pour p et d'une chaîne d'addition pour q.

Programme à réaliser

Cette question demande de mettre en oeuvre un certain nombre de structures de données. Il est demandé de définir et de programmer ces structures de données, et non pas d'utiliser les classes déjà présentes, par exemple, dans le package java.util.

Écrire une classe pour des ensembles d'entiers représentant des chaînes d'additions, avec des méthodes pour l'adjonction d'un élément à un ensemble, le test d'appartenance à un ensemble, l'union de deux ensembles, l'affichage d'un ensemble. Une structure de données autour d'un tableau de booléens pourra suffire.

Écrire une classe pour les collections d'ensembles, ou ensembles d'ensembles. Cette classe sera destinée à stocker sans répétition toutes les chaînes d'additions d'un même entier et à pouvoir itérer aisément sur toutes les entrées de la collection. Une structure de donnée non optimale mais suffisante sera une liste chaînée triée par ordre croissant. [Ignorer totalement la remarque suivante de la version originale du sujet : Un meilleur choix (à ne considérer qu'après avoir fini le sujet) sera un arbre binaire de recherche.] Pour permettre de maintenir l'ordre dans la collection, tout choix d'ordre sur les ensembles d'entiers pourra convenir. On ajoutera donc une méthode de test d'ordre à la classe définissant les ensembles d'entiers.

Écrire un programme qui calcule tous les ensembles représentant les chaînes d'additions pour un entier n à partir de tous les ensembles représentant les chaînes d'additions pour les entiers plus petits que n-1. (On pourra évidemment se restreindre à des entiers p plus petits que plafond(n/2).)

Ajouter une méthode pour calculer le cardinal d'une chaîne d'addition et faire afficher les entrées d'une collection qui sont de cardinal minimal. Retrouver ainsi que toutes les chaînes d'additions minimales pour les entiers jusqu'à 20 sont

n = 2 { 1, 2 }
n = 3 { 1, 2, 3 }
n = 4 { 1, 2, 4 }
n = 5 { 1, 2, 4, 5 }, { 1, 2, 3, 5 }
n = 6 { 1, 2, 4, 6 }, { 1, 2, 3, 6 }
n = 7 { 1, 2, 4, 6, 7 }, { 1, 2, 4, 5, 7 }, { 1, 2, 3, 6, 7 }, { 1, 2, 3, 5, 7 }, { 1, 2, 3, 4, 7 }
n = 8 { 1, 2, 4, 8 }
n = 9 { 1, 2, 4, 8, 9 }, { 1, 2, 4, 5, 9 }, { 1, 2, 3, 6, 9 }
n = 10 { 1, 2, 4, 8, 10 }, { 1, 2, 4, 6, 10 }, { 1, 2, 4, 5, 10 }, { 1, 2, 3, 5, 10 }
n = 11 { 1, 2, 4, 8, 10, 11 }, { 1, 2, 4, 8, 9, 11 }, { 1, 2, 4, 6, 10, 11 }, { 1, 2, 4, 6, 7, 11 }, { 1, 2, 4, 5, 10, 11 }, { 1, 2, 4, 5, 9, 11 }, { 1, 2, 4, 5, 7, 11 }, { 1, 2, 4, 5, 6, 11 }, { 1, 2, 3, 6, 9, 11 }, { 1, 2, 3, 6, 8, 11 }, { 1, 2, 3, 5, 10, 11 }, { 1, 2, 3, 5, 8, 11 }, { 1, 2, 3, 5, 6, 11 }, { 1, 2, 3, 4, 8, 11 }, { 1, 2, 3, 4, 7, 11 }
n = 12 { 1, 2, 4, 8, 12 }, { 1, 2, 4, 6, 12 }, { 1, 2, 3, 6, 12 }
n = 13 { 1, 2, 4, 8, 12, 13 }, { 1, 2, 4, 8, 9, 13 }, { 1, 2, 4, 6, 12, 13 }, { 1, 2, 4, 6, 7, 13 }, { 1, 2, 4, 5, 9, 13 }, { 1, 2, 4, 5, 8, 13 }, { 1, 2, 3, 6, 12, 13 }, { 1, 2, 3, 6, 7, 13 }, { 1, 2, 3, 5, 10, 13 }, { 1, 2, 3, 5, 8, 13 }
n = 14 { 1, 2, 4, 8, 12, 14 }, { 1, 2, 4, 8, 10, 14 }, { 1, 2, 4, 6, 12, 14 }, { 1, 2, 4, 6, 10, 14 }, { 1, 2, 4, 6, 8, 14 }, { 1, 2, 4, 6, 7, 14 }, { 1, 2, 4, 5, 10, 14 }, { 1, 2, 4, 5, 9, 14 }, { 1, 2, 4, 5, 7, 14 }, { 1, 2, 3, 6, 12, 14 }, { 1, 2, 3, 6, 8, 14 }, { 1, 2, 3, 6, 7, 14 }, { 1, 2, 3, 5, 7, 14 }, { 1, 2, 3, 4, 7, 14 }
n = 15 { 1, 2, 4, 5, 10, 15 }, { 1, 2, 3, 6, 12, 15 }, { 1, 2, 3, 6, 9, 15 }, { 1, 2, 3, 5, 10, 15 }
n = 16 { 1, 2, 4, 8, 16 }
n = 17 { 1, 2, 4, 8, 16, 17 }, { 1, 2, 4, 8, 9, 17 }
n = 18 { 1, 2, 4, 8, 16, 18 }, { 1, 2, 4, 8, 10, 18 }, { 1, 2, 4, 8, 9, 18 }, { 1, 2, 4, 6, 12, 18 }, { 1, 2, 4, 5, 9, 18 }, { 1, 2, 3, 6, 12, 18 }, { 1, 2, 3, 6, 9, 18 }
n = 19 { 1, 2, 4, 8, 16, 18, 19 }, { 1, 2, 4, 8, 16, 17, 19 }, { 1, 2, 4, 8, 10, 18, 19 }, { 1, 2, 4, 8, 10, 11, 19 }, { 1, 2, 4, 8, 9, 18, 19 }, { 1, 2, 4, 8, 9, 17, 19 }, { 1, 2, 4, 8, 9, 11, 19 }, { 1, 2, 4, 8, 9, 10, 19 }, { 1, 2, 4, 6, 12, 18, 19 }, { 1, 2, 4, 6, 12, 13, 19 }, { 1, 2, 4, 6, 7, 13, 19 }, { 1, 2, 4, 6, 7, 12, 19 }, { 1, 2, 4, 5, 10, 15, 19 }, { 1, 2, 4, 5, 10, 14, 19 }, { 1, 2, 4, 5, 9, 18, 19 }, { 1, 2, 4, 5, 9, 14, 19 }, { 1, 2, 4, 5, 9, 10, 19 }, { 1, 2, 4, 5, 7, 14, 19 }, { 1, 2, 4, 5, 7, 12, 19 }, { 1, 2, 3, 6, 12, 18, 19 }, { 1, 2, 3, 6, 12, 13, 19 }, { 1, 2, 3, 6, 9, 18, 19 }, { 1, 2, 3, 6, 9, 10, 19 }, { 1, 2, 3, 6, 8, 16, 19 }, { 1, 2, 3, 6, 8, 11, 19 }, { 1, 2, 3, 6, 7, 13, 19 }, { 1, 2, 3, 6, 7, 12, 19 }, { 1, 2, 3, 5, 8, 16, 19 }, { 1, 2, 3, 5, 8, 11, 19 }, { 1, 2, 3, 5, 7, 14, 19 }, { 1, 2, 3, 5, 7, 12, 19 }, { 1, 2, 3, 4, 8, 16, 19 }, { 1, 2, 3, 4, 8, 11, 19 }
n = 20 { 1, 2, 4, 8, 16, 20 }, { 1, 2, 4, 8, 12, 20 }, { 1, 2, 4, 8, 10, 20 }, { 1, 2, 4, 6, 10, 20 }, { 1, 2, 4, 5, 10, 20 }, { 1, 2, 3, 5, 10, 20 }

Le programme devrait pouvoir retrouver ces données en moins d'une demi-heure sur les machines les plus lentes des salles info (400 MHz), les machines les plus rapides étant de 5 à 6 fois plus rapides (plus de 2 GHz). Vérifier empiriquement que la taille de la collection des chaînes d'additions pour n est approximativement 2n/(n+3) [et non pas 2n/(n+2), comme indiqué dans la version originale du sujet].

Chaînes d'additions minimales : une illusion

On se concentre maintenant sur l'obtention des chaînes de longueur minimales. Une première idée naïve est qu'une telle chaîne pour n s'obtient en adjoignant n à l'union d'une chaîne d'addition minimale pour p et d'une chaîne d'addition minimale pour q.

Programme à réaliser

Écrire une méthode pour extraire d'une collection la sous-collection des ensembles d'un cardinal donné et adapter le programme précédent pour ne retenir pour chaque n que les chaînes de longueur minimales. Vérifier que, par exemple, la chaîne { 1, 2, 3, 5, 8, 13 } est obtenu par la recherche exhaustive, mais est oubliée par la variante puisque l'unique chaîne minimale pour 8 est { 1, 2, 4, 8 }, qui contient 4.

Chaînes d'additions minimales : un algorithme (extension facultative)

On veut maintenant aller plus loin et trouver les chaînes d'additions minimales pour des entiers plus grands, telle la chaîne

{ 1, 2, 3, 6, 12, 24, 48, 51, 102, 153, 255 }

parmi les 24 chaînes pour l'entier 255, qui correspond à 10 additions là où la chaîne provenant de l'exponentiation binaire en nécessiterait 14. La croissance exponentielle de la taille de l'ensemble de toutes les chaînes d'additions d'un entier n interdit l'approche exhaustive des sections qui précédent.

En vue de décrire un meilleur algorithme, on considère un arbre étiqueté par des entiers et construit de la façon suivante : pour chaque sommet, la suite des étiquettes sur le chemin depuis la racine fourni une chaîne d'additions ; comme descendance de chaque sommet, on place les entiers qui s'obtiennent comme somme de deux étiquettes sur le chemin depuis la racine jusqu'au sommet courant et qui n'apparaissent pas déjà sur le chemin. Tronqué à profondeur 5, cet arbre infini est le suivant :

1
2
3 4
456 568
5 6 7 8   6 7 8 10   7 8 9 12   6 7 9 10   7 8 10 12   9 10 12 16

On ne demande pas de contruire cet arbre, qui n'est qu'une vue abstraite sur la collection de toutes les chaînes d'additions. En revanche, l'algorithme peut être vu comme se déplaçant dans cet arbre à la recherche de toutes les chaînes d'additions pour un entier n et une longueur de chaînes k donnés. Ainsi, on recherche d'abord pour des k si petits qu'aucune chaîne n'existe, puis en incrémentant k petit à petit, on finit par trouver d'un coup toutes les chaînes de longueur minimale. Plus précisément, l'algorithme procède à une recherche en profondeur d'abord et par les entiers les plus grands d'abord dans la descendance de chaque noeud. Ainsi, le chemin 1, 2, 4, 8, 16 sera considéré avant le chemin 1, 2, 3, 4, 5.

Il convient donc de se donner une bonne borne inférieure sur la longueur des chaînes d'additions minimales pour un entier n. Des considérations théoriques ont montré que

plafond( log2n + log2nu(n) - 2,13 )

est une borne inférieure générale, et que

plancher(log2n) + plafond( log2nu(n) )

est une borne inférieure pour les cas particuliers où n < 327679 ou nu(n) < 17. Ici, plancher(x) est l'entier immédiatement inférieur au réel x.

Programme à réaliser

Écrire une méthode récursive qui parcoure l'arbre de recherche décrit plus haut à la recherche de toutes les chaînes d'additions de longueur fixée k pour un entier n. La chaîne d'additions en construction, correspondant au chemin courant dans l'arbre décrit plus haut, sera stockée dans un tableau d'entiers. On partira du tableau vide dont on se servira en fait comme d'une pile.

Écrire un programme qui commence par calculer la borne inférieure b sur la longueur des chaînes d'additions minimales pour un entier n, puis qui recherche les chaînes de cette longueur b, puis en cas d'échec les chaînes de longueur b + 1, etc. Retrouver les 24 chaînes minimales pour 255. Ce calcul devrait être possible en 2 minutes sur les machines les plus lentes des salles info (400 MHz), les machines les plus rapides étant de 5 à 6 fois plus rapides (plus de 2 GHz).

Quelques idées pour élaguer l'arbre de calcul (extension facultative)

Si une chaîne d'additions démarre trop lentement, le fait qu'elle ne peut ensuite croître au mieux que par multiplications par deux contraint les entiers qu'elle peut atteindre en k étapes. On peut ainsi détecter assez tôt un certain nombre de branches de calcul qui ne peuvent donner de chaîne pour l'entier voulu. Plus précisément, la recherche de chaînes d'additions de longueur k pour n sera stérile dès que l'on a un ai tel que 2k - iai < n. Un critère très légèrement amélioré est qu'on peut arrêter toute une branche de calcul dès que

ai < plafond( n/2k - i ).

Ce critère s'améliore grandement si l'on prend en compte la valuation de 2 dans n. En écrivant n sous la forme n = 2tm avec m impair, on obtient qu'on peut arrêter toute une branche de calcul dès que

ai < plafond( n/2k - i -2/3 ) =: bi pour i inférieur ou égal à k - t - 2

ou

ai < plafond( n/2k - i ) =: bi pour i entre k - t - 1 et k, inclus.

Encore mieux, si n = 2tm n'est pas un multiple de 5, alors on peut arrêter la branche de calcul dès lors que ai ne vaut pas n/2k - i (qui conduirait à terminer la chaîne par des multiplications par 2) mais que

ai + ai-1 < bi+1.

Pour plus de détails et d'autres formules d'élagage, on se reportera à l'article Efficient Generation of Minimal Length Addition Chains de Thurber.

Résultats à retrouver et conjecture de Scholz-Brauer

Pour valider votre programme, vous pourrer essayer de retrouver les valeurs qui suivent, où en appelant l(n) la longueur des chaînes d'additions minimales pour n, c(r) désigne le plus petit entier tel que l(n)=r et d(r) le nombre de solutions n de l'équation l(n)=r. Attention, il est fort probable que votre programme ait du mal à calculer pour des n de plus de quelques centaines.

rc(r)   rc(r)   rc(r)
1272913607
23847141087
35971151903
4710127163583
51111191176271
619123791811231
 
rd(r)rd(r)rd(r)
1161511246
2272612432
3384413772
45978141382
5910136152481

D'autres valeurs sont données ici.

Enfin, une conjecture encore ouverte est la conjecture de Scholz-Brauer, qui affirme que, pour tout n,

l( 2n - 1 ) < n + l(n).

Cette borne conjecturale montre à quel point la méthode d'exponentiation binaire serait loin de l'optimum dans le cas le pire, lorsque l'écriture binaire de n a beaucoup de 1. Vérifier la conjecture pour de petites valeurs de n.


Valid HTML 4.01!   Valid CSS!