Re: Problème de l'arrêt (was: Que fait ce programme ?)

Le 30/09/2022 à 12:53, Olivier Miakinen a écrit :

[diapublication, suivi vers fr.sci.maths seul]
 
Bonjour,
 
Le 30/09/2022 à 07:17, ast avait écrit :

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

 
Comme l'écrivait Michel Talon, cette fonction retourne simplement
la somme des entiers m et n, du moins cela fonctionne pour tous les
entiers positifs. À chaque tour de boucle, on retrouve dans m la
somme bit à bit des nombres m et n *sans tenir compte des retenues*,
et dans n la somme de toutes les retenues. Au bout d'un petit
nombre de tours de boucle, il n'y a plus aucune retenue à faire, et
alors le nombre n vaut 0 tandis que le nombre m contient le résultat
attendu à savoir la somme des nombres m et n de départ.
 
Je voudrais maintenant étendre la question d'ast, en faisant suivre
vers fr.sci.maths seul car ça n'a plus rien de spécifique à python.
 
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 ?
 

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. AMA le nombre de boucles est *au plus* égal au rang max du chiffre
binaire à 1 du résultat. Vrai ??

 
Précision pour la représentation des nombres en binaire, un nombre
positif comporte « à gauche » une infinité de chiffres binaires
valant zéro, tandis que les nombres négatifs ont une infinité de
chiffres à 1.
 
Exemples :
  3 = ...0000011
  2 = ...0000010
  1 = ...0000001
  0 = ...0000000
 -1 = ...1111111
 -2 = ...1111110
 -3 = ...1111101
 -4 = ...1111100
 
 

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

https://www.techno-science.net/definition/6685.html

Ce n'est plus exactement des maths "pures" mais c'est bien utile dans les ordis.