Re: Problème de l'arrêt

Le 30/09/2022 17:13, maixxx m'a répondu :

>
def f(m, n):
   while n:
     m, n = m ^ n, (m & n) << 1
   return m

 
[...]
 
Ma question est alors de déterminer pour quelles valeurs de m et n
le programme s'arrête et pour quelles valeurs il ne s'arrête jamais.
 
Question subsidiaire : lorsque le programme s'arrête, combien de
tours de boucle a-t-il réalisés ?

 
pour 15+1  m= 1111 + n=0001
     14+2     1110     0010
     12+4     1100     0100
     8+8      1000     1000
     16+0     10000    0000
4 itérations
 
pour 6+5     0110   0101
     3+8     0011   1000
     11+0    1011   0000
2 itérations
 
pour 4+8     1000   0100
     12+0    1100   0000
1 itération
 
Remarquer qu'à chaque itération la somme m+n est constante et égale au résultat
final.

Oui.

AMA le nombre de boucles est *au plus* égal au rang max du chiffre
binaire à 1 du résultat. Vrai ??

... ce qui est évidemment vrai lorsque le résultat est un nombre négatif,
puisqu'alors ce rang max est infini. :-)

Mais oui, pour des nombres positifs ce que tu dis est forcément vrai, du
fait que s'il y a plusieurs boucles c'est à cause de la propagation d'une
retenue, à chaque fois au rang suivant.

Je vais bientôt proposer ma propre solution à cette question.

[...]
 

Ça fait bien penser aux "additionneurs" réalisés avec des registres et des portes.

Oui. Je suis même prêt à parier qu'il s'agit de la source d'inspiration d'ast
(ou de la personne ayant écrit la fonction que nous a proposée ast, si ce n'est
pas lui l'auteur de cette fonction).


--
Olivier Miakinen