[Ma réponse] Re: Problème de l'arrêt

Le 30/09/2022 12:53, j'écrivais :

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

 
[...]
 
Lorsque l'un des nombres est négatif, il arrive que l'algorithme ne
s'arrête jamais. Par exemple lorsque m vaut -1 et que n vaut n'importe
quel nombre strictement positif.
 
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 ?

Voici ma réponse à cette question, sur un exemple.
Voyons par exemple f(-123350, 19676).

En binaire, les nombres -123350 et 19676 s'écrivent respectivement de la façon
suivante, où les « ... » du début indiquent que les 1 ou les 0 sont à imaginer
comme s'étendant jusqu'à l'infini vers la gauche :

 ...11100001111000101010
 ...00000100110011011100

Mettons une barre de séparation à droite de chaque colonne de chiffres égaux
(soit deux 0 l'un au dessus de l'autre, soit deux 1 l'un au dessus de l'autre) :

 ...1110|0|00|11|1|10|00101|010|
 ...0000|0|10|01|1|00|11011|100|

Ne retenons que les blocs se terminant par une colonne de deux 1 :

             |11|1|  |00101|
             |01|1|  |11011|

On a ici un bloc de longueur 2, un bloc de longueur 1 et un bloc de longueur 5.
Ma proposition est que le nombre de tours de boucle sera toujours exactement
égal à un de plus que la plus grande longueur de bloc retenu. Dans cet exemple,
ce sera donc 5 + 1 = 6 tours de boucle.

Plus généralement :
- Si n = 0, on fera 0 tour de boucle.
- Sinon, si on ne retient aucun bloc, on fera 1 tour de boucle.
- Sinon, soit l_max la longueur du plus grand bloc retenu, on fera (l_max + 1)
  tours de boucle. Notons qu'il peut y avoir plusieurs blocs de longueur l_max,
  ça ne changera rien au résultat.

Cas particulier, si l'un des nombres (mettons m) est négatif, et que l'autre
(donc n) est positif et supérieur ou égal à -m, alors le bloc le plus à gauche
est de longueur infinie. Dans ce cas, et dans ce cas seulement, le programme
boucle indéfiniment.


--
Olivier Miakinen