le compte est bon ! (2ème volet Chiffres et Lettres)

[phil-nellier]

J'ouvre ici un deuxième fil dédié à la partie CHIFFRES du célèbre jeu télévisé.

La problématique du « compte est bon » intéressante en elle-même, l’est encore plus lorsqu’on cherche à l’optimiser pour un calculateur de puissance très limitée comme le Spectrum.
Il s’agit, rappelons le, d’obtenir un total fixé aléatoirement et compris entre 100 et 999, à partir de six nombres composés parmi les chiffres de 1 à 9, auxquels s’ajoutent les nombres 10, 25, 50, 75 et 100. Les opérations applicables sont les 4 opérations simples et purement arithmétiques basées sur des entiers positifs, et chaque nombre ne doit être utilisé qu’une seule fois
Le nombre de combinaisons possibles ( il s’agit d’arrangements de nombres 2 à 2, chaque résultat intermédiaire étant à son tour un facteur utilisable dans une opération avec les nombres restants non utilisés) est très important. Je ne suis pas un spécialiste dans ce domaine, mais on peut raisonner de la manière suivante :
Hors utilisation de parenthèses, il y a 6 ! permutations des 6 chiffres 2 à 2, auxquelles on peut appliquer chaque fois 4 opérations entre le premier nombre et les 5 restants, soit au total un nombre de possibilités qui est de 4^5x6 ! = 737280. De plus, chaque résultat intermédiaire vient s’ajouter à la série de chiffres non utilisés, il faut donc en fait multiplier le total par 5 !, ce qui nous amène à plus de 88 millions de combinaisons. Heureusement, l’ordre des nombres importe peu : a op b est identique à b op a lorsqu’il s’agit d’une multiplication ou d’une addition, et pour la soustraction comme pour la division, une seule des deux permutations est valide. Tout cela réduit considérablement le nombre d’opérations à effectuer, et les ramène à un total de 3 516 060.

Même ainsi, cela fait beaucoup pour un Z80 à 3,5 Mhz. l'exploration de toutes les combinaisons d'opérations reste impossible en 45 secondes.
En effet une horloge cadencée à 3,5 Mhz permet en principe au processeur d'effectuer 3 500 000 instructions élémentaires à la seconde, dont une petite partie consommée par les seules interruptions non masquables (environ 400 par cycle d'1/50 ème de seconde, soit 20 000 par seconde). Donc si une routine de traitement utilise ne serait-ce que 1000 instructions élémentaires pour effectuer une opération, l'ordinateur peut effectuer 3300 opérations par seconde. En 45 secondes, le temps imparti dans le jeu « Les chiffres et les lettres » il ne peut donc explorer que 148500 combinaisons, on est donc loin des 3,5 millions que représente le total possible. J'exposerai plus tard que l'on peut réduire sérieusement le nombre de combinaisons à explorer en réalité..
A ma connaissance, il n’existe pas d’algorithme simple pour optimiser la recherche. Les seuls algorithmes réellement efficaces à cet effet sont basés sur l’utilisation de tables qui consomment pas mal de mémoire, et bien évidemment cette voie m’était du coup interdite sur le Spectrum, où la cohabitation des Chiffres et des Lettres m’imposait de conserver le maximum de ram pour le dictionnaire.
Il ne reste donc que deux options :
La première (que j’avais dans un premier temps implémentée) consiste à opérer à partir du total à atteindre et de lui appliquer dans le sens descendant, à l’aides des 6 nombres, des additions, soustractions et divisions (sans multiplication) pour essayer d’obtenir un résultat final de 0. On réduit ainsi considérablement le nombre de combinaisons à tester, et dans la grande majorité des cas le Spectrum trouve le résultat en moins de 45 s. Mais cette méthode ne permet pas d’obtenir un résultat approché si on ne parvient pas au total exact. J’avais donc opté pour un mécanisme basé sur le temps écoulé. Au bout de 30 s, le calculateur re faisait ses calculs pour T+1, puis 7 s plus tard pour T-1. Même ainsi il arrivait une fois sur 10 que l’ordinateur n’obtienne pas de résultat.
J’ai donc voulu finalement explorer la méthode « ouverte » qui s’essaie à explorer toutes les combinaisons possibles. Je me suis appuyé sur l’algorithme récursif de base, dont le développement le plus compact se résume dans les quelques lignes ci-après, bien connues des apprentis en langage C : limpide et complexe à la fois.

#define GAP(a,b) (((a)>(b))?((a)-(b)):((b)-(a)))
#define SPRINTOP(a,b,k,res) \
({strcpy(str_tmp,str_result);\
sprintf(str_result,"%3d %c %3d = %d\n%s",\
(((a)>(b))?(a):(b)),s[k],(((a)>(b))?(b):(a)),res,str_tmp);})
#define NBCH 6
int best_tot = 0, best_gap = 999;
char str_result[255],str_tmp[255];
int plus (int *a, int b) { return (*a += b); }
int moins(int *a, int b) { return (*a = GAP(*a,b)); }
int multi(int *a, int b) { return (*a *= b ); }
int divis(int *a, int b) {
if (*a < b) { *a^=b; b^=*a; *a^=b; }
if ( !(*a%b) ) return (*a /= b );
return 0;
}
#define NBOP 4
int (*f[])(int *,int) = { plus , moins , multi, divis };
char s[] = "+-*/";
int lcb(int *tab, int nb, int tot)
{
int i,j,k,t[NBCH];
for ( i=0 ; i<nb-1 ; i++ )
for ( j=i+1 ; j<nb ; j++)
for ( k=0; k<NBOP; k++) {
memcpy(t,tab,sizeof(int)*NBCH);
if ( (*f[k])(&t,t[j]) ) {
if ( t == tot ) return SPRINTOP(tab,tab[j],k,t);
if ( GAP(t,tot) < best_gap) {
best_tot = t ;
best_gap = GAP(best_tot,tot);
}
t[j]=t[nb-1];
if (lcb(t,nb-1,tot)) return SPRINTOP(tab,tab[j],k,t);
}
}
return 0;
}
int main(void)
{
int t[NBCH], i, tot;
*str_result = 0x00;
for ( i=0; i<NBCH ; scanf("%d",(printf("nombre %d : ",i+1),&t[i++]))) ;
printf("total : ");
scanf("%d",&tot);
if ( ! lcb(t,NBCH,tot) ) lcb(t,NBCH,best_tot);
else printf("Le compte est bon : \n");
return ! printf(str_result);
}

Ma méthode de développement en assembleur passe toujours par deux phases :
1) écriture et test de l’algorithme écrit en Basic Sinclair
2) transcription en assembleur
En effet, le déboguage est beaucoup plus aisé en langage basic, et une fois qu’on est certain que ça marche on peut s’attaquer aux manipulations de registres machine.
Même ainsi, la simple notion de fonction récursive n’existant pas dans le basic Sinclair, il m’a fallu trouver le moyen de la remplacer.
Il suffisait pour cela de créer un tableau de valeurs correspondant aux différents indices d’incrémentation i, j, k, empilées successivement puis désempilées (avec un nombre de niveaux de récursivité qui dans tous les cas se limite à 4 en réalité).

Tout ceci ayant abouti, il restait plusieurs problèmes à traiter :

1) comment limiter autant que possible le nombre de combinaisons à tester ?
Il s’agit d’éliminer toute opération inutile. L’avantage de cette élimination est que du coup toutes les opérations restant à réaliser dans la branche explorée sont également éliminées. Ce qui est particulièrement payant si l’opération initiale se trouve être la première de la branche. Bien entendu la règle de base est que toute division dont le résultat n’est pas entier est éliminée. Mais il y en a d’autres..
première règle : pas de multiplication ni de division si l’un des facteurs est le nombre 1
deuxième règle : lorsque le résultat d’une opération est identique à l’un des facteurs, on élimine l’opération (exemple 4-2=2 est sans intérêt, de même que 9/3 = 3)
troisième règle : limiter les totaux intermédiaires (j’ai ainsi éliminé tout résultat intermédiaire supérieur à 4000, quand il s’agit ne l’oublions pas d’atteindre un total inférieur à 1000)
quatrième règle : test de parité (inutile de diviser deux nombres dont l’un serait pair et l’autre impair), ce test très rapide évite de réaliser une bonne partie des divisions. Les autres règles de divisibilité, trop complexes à tester, ne présentent pas le même intérêt.

2) comment choisir l’ordre des opérations et faut-il classer les nombres ?
En réalité, il y a un cas important que je voulais voir traité à tout coup par l’ordinateur, c’est lorsque le total ne peut être obtenu car le produit des différents nombres est inférieur à ce total. Prenons l’exemple du tirage 2 3 2 4 1 6. Le total le plus important qu’on puisse obtenir est (1+2)x2x3x4x6 = 432. Si le total demandé est supérieur à ce nombre, il faut que l’ordinateur aboutisse le plus vite possible au résultat approché le meilleur, soit 432.
A cet effet, avant tout traitement il faut donc classer les nombres du plus petit au plus grand (ici 2,3,2,4,1,6 s’ordonnent en 1,2,2,3,4,6) et ensuite appliquer en priorité la multiplication puis l’addition.
Ainsi, 1x2 est aussitôt éliminé (multiplication par 1), et toute la série des opérations suivant cette opération est également éliminée. Le test suivant est donc 1+2 puis l’application de multiplications à tous les nombres restants. On obtient donc très vite le meilleur résultat approché.
Ensuite on peut opter pour la soustraction (plus rapide) et terminer par la division, mais en fait on a plus intérêt à faire l’inverse car beaucoup de divisions n’aboutissent pas à un entier, et dans ce cas on économise plus de combinaisons parmi celles restant à effectuer.
L’autre avantage de ce choix de l’ordre x, + , / , - est bien sûr que si après une opération de type + le résultat intermédiaire obtenu reste inférieur au total à atteindre, il est inutile de continuer puisque les opérations restantes ne peuvent que réduire encore ce résultat.


3) Comment optimiser le temps de calcul pour une opération ?
La question se pose évidemment pour la multiplication et la division, beaucoup plus complexes que l’addition et la soustraction. Je vais donc parler des algorithmes possibles pour ces opérations..


**************************************************************************
LA DIVISION EUCLIDIENNE

Il existe en fait deux algorithmes principaux pour la division dite euclidienne (donc entre des entiers)

L’algorithme le plus simple consiste à soustraire autant de fois b de a qu’il est possible, jusqu’à obtenir un reste < b.
Voici l’algorithme correspondant :

division:=proc(a,b)
local r, q, u ;
r := a ;
q := 0 ;
while (r >= b)
do
r := r - b ;
q := q + 1 ;
od ;
u := [q, r] ;
return(u) ;
end ;


Mais, il existe un algorithme beaucoup plus performant, basé sur l’écriture binaire des nombres, et donc nettement mieux adapté à un calcul par ordinateur.
Je dois la découverte de cet algorithme à un article signé Ainigmatias Cruptos, diffusé par l’Association Acrypta sur internet. Je me contente d’en reproduire ici les termes :

Cet algortihme consiste à rechercher les digits successifs du quotient par dichotomie, et à reconstruire ce quotient par l’algorithme de Hörner. Dans un premier temps on détermine un n tel que 2nb > a et on met 2nb dans une mémoire auxiliaire aux.

divisionbin :=proc(a,b) ;
local r,q,aux,n,u ;
r := a ; q := 0 ; n := 0 ; aux := b ;
while (aux <= a)
do
aux := 2 * aux ;
n := n + 1 ;
od ;
while (n > 0)
do
aux := aux/2 ;
n := n - 1 ;
if (r < aux)
then
q := 2 * q ;
else
q := 2 * q + 1 ;
r := r - aux ;
fi ;
od ;
u := [q, r] ;
return(u) ;
end ;

Comparaison

Le premier algorithme (Euclide pour la division) est inutilisable car le nombre de tours de boucles
contenant des opérations simples est O(a) tandis que le deuxième aboutit même pour de grands
nombres, son nombre de tours de boucles contenant des opérations simples est O(ln(a)).

LA MULTIPLICATION :

La méthode la plus évidente pour réaliser une multiplication est de faire une succession d’additions sur l’un des facteurs en décrémentant un compteur constitué par l’autre facteur jusqu’à la valeur 0

Mult=proc(a,b)
n :=a ; t :=0
while n>0
t :=t + a
n :=n – 1
end ;

Il est bien entendu possible d’optimiser en choisissant le plus petit nombre pour a, le plus grand pour b.
Ainsi 2x300 est très rapide à effectuer (deux additions)
Mais dans un cas comme 25x25 il faut réaliser 25 addtitions et autant de décrémentations, ce qui n’est pas très satisfaisant.

Une autre méthode, beaucoup mieux adaptée au binaire, est la multiplication dite « à la russe »
Elle consiste à diviser par 2 le premier facteur dans le même temps que l’on multiplie le second facteur par 2. Et on garde le résultat intermédiaire du 2ème facteur lorsque le résultat entier de la division du premier est impair :
Ainsi, pour reprendre 25x25
25 25 25
12 50
6 100
3 200 200
1 400 400
Résultat = somme des nombres de la troisième colonne. Donc 4 divisions, 4 multiplications, trois additions au total. L’avantage est que muliplication par 2 et division par 2 se résolvent par de simples décalages de bits à gauche ou à droite, ce qui est extrêmement rapide.

En employant ces différents alogorithmes, j’ai pu faire des tests donnant les résultats suivants pour 1000 opérations :
Opération durée moyenne
Addition 0,5 s
Soustraction 0,53 s
Multiplication 0,85 s
Division 0,9 s
Le résultat est donc probant, les écarts entre les opérations simples et les plus complexes se réduisent sérieusement !!

CONCLUSION :

Et le résultat des courses ?

Les différentes règles employées pour limiter les combinaisons à explorer font qu’en moyenne l’ordinateur ne teste qu’entre 200 000 et 400 000 opérations sur les 3,5 millions, et très rarement jusqu’à 500 000.
Du coup, en 45 secondes, il peut en tester à peu près le tiers, et comme l’effet de symétrie permet de réduire encore le nombre efficace des combinaisons, il trouve le meilleur résultat à peu près 15 fois sur 16 ce qui est très honorable. Et quand il ne l’obtient pas, le résultat approché est très rarement à plus d’une unité du total.
Sur un émulateur où l’on peut artificiellement augmenter la cadence d’horloge, le résultat le meilleur est toujours trouvé si on passe la cadence à 14 Mhz (ce qui reste ridicule par rapport à celle de nos processeurs actuels)