Que fait ce programme ?

[ast]

Devinette: Que retourne cette petite fonction python

(m et n sont 2 entiers naturels)


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


pour ceux qui ne connaissent pas python

"while n" c'est "pendant que n est non nul"

^ est l'opérateur "ou exclusif" bit à bit
& est le "et" bit à bit
<< 1 décalage à gauche bit à bit et ajout d'un 0 à droite

a, b = c, d affectation simultanée a <- c et b <- d

[Olivier Miakinen]

Le 30/09/2022 à 07:17, ast a écrit :
> Devinette: Que retourne cette petite fonction python
>
> (m et n sont 2 entiers naturels)
>
>
> def f(m, n):
> while n:
> m, n = m ^ n, (m & n) << 1
> return m

Je n'ai pas encore compris comment ça fonctionne, mais cette fonction
semble être une façon compliquée de réaliser une opération simple.

Des quelques tests que j'ai réalisés, cela fonctionne même avec des
nombres négatifs, sauf que l'appel suivant semble boucler indéfiniment :
f(-10,12)


--
Olivier Miakinen

[Olivier Miakinen]

Le 30/09/2022 à 11:14, je répondais à ast :

>
>> Devinette: Que retourne cette petite fonction python
>>
>> (m et n sont 2 entiers naturels)
>>
>>
>> def f(m, n):
>> while n:
>> m, n = m ^ n, (m & n) << 1
>> return m
>
> Je n'ai pas encore compris comment ça fonctionne, mais cette fonction
> semble être une façon compliquée de réaliser une opération simple.
>
> Des quelques tests que j'ai réalisés, cela fonctionne même avec des
> nombres négatifs, sauf que l'appel suivant semble boucler indéfiniment :
> f(-10,12)

Bien évidemment ce n'est pas le seul cas où ça boucle indéfiniment, mais
lorsque ça ne boucle pas le résultat est conforme aux attentes.


--
Olivier Miakinen

[Olivier Miakinen]

Le 30/09/2022 à 11:14, j'écrivais :

>>
>> def f(m, n):
>> while n:
>> m, n = m ^ n, (m & n) << 1
>> return m
>
> Je n'ai pas encore compris comment ça fonctionne

Ok, j'ai compris comment ça fonctionne. Réponse en ROT-13.

Cbhe har cnver qr ovgf qbaaéf à yn cbfvgvba x (p'rfg-à-qver qr
cbvqf 2^x) :
- f'vyf fbag gbhf yrf qrhk ahyf vyf erfgrag ahyf nceèf y'bcéengvba ;
- fv y'ha qrf qrf qrhk inhg méeb rg y'nhger ha, nceèf y'bcéengvba
ba ergebhir ha qnaf z rg méeb qnaf a à prggr cbfvgvba ;
- f'vyf fbag gbhf yrf qrhk étnhk à ha, ba ergebhir méeb qnaf z à
prggr cbfvgvba, rg ha qnaf a à yn cbfvgvba x+1. P'rfg-à-qver dhr
2^x nwbhgé à 2^x qbaar 2^(x+1).
Crgvg à crgvg ba rssrpghr qbap yn fbzzr qr z rg qr a, bù à pundhr
égncr ba ergebhir yrf fbzzrf fnaf ergrahr qnaf z rg yrf ergrahrf
qnaf a.


--
Olivier Miakinen

[Michel Talon]

Le 30/09/2022 à 07:17, ast a écrit :

m+n


--
Michel Talon

[Olivier Miakinen]

[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 ?


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


--
Olivier Miakinen

[maixxx]

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.

[Olivier Miakinen]

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

[Olivier Miakinen]

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

[Olivier Miakinen]

Le 30/09/2022 22:48, j'écrivais :

>
> 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.

Exemple avec -123350 et +123350 :

...11100001111000101010
...00011110000111010110

...1110000111100010101|0|
...0001111000011101011|0|

...1110000111100010101|
...0001111000011101011|

Autre exemple avec -123350 et +123458 :

...11100001111000101010
...00011110001001000010

...11100001111|0|0|010|10|1|0|
...00011110001|0|0|100|00|1|0|

...11100001111| |1|
...00011110001| |1|

Alors qu'avec -123350 et +123321 :

...11100001111000101010
...00011110000110111001

...11100001111000|1|01|0|10
...00011110000110|1|11|0|01

|1|01|
|1|11|

Avec deux nombres négatifs, on a une infinité de blocs de longueur 1
mais aucun bloc de longueur infinie, donc ça marche.

--
Olivier Miakinen

[Michel Talon]

Le 30/09/2022 à 21:46, Olivier Miakinen a écrit :
> 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.

En fait, tel que je le vois, m+n est un invariant de la boucle. Pourquoi?

m devient le XOR de m et n, c'est à dire a les bits qui sont soit dans m
soit dans n mais pas les deux.

n devient le double (à cause du << 1) du AND de m et n c'est à dire les
bits qui sont à la fois dans m et n. Evidemment quand on fait m+n
le AND apparaît 2 fois, et le XOR une fois, donc il est "clair" que m+n
a la même valeur que m ^ n + (m & n) << 1.

Comme XOR(m,n) <= max(m,n) et idem pour AND(m,n) et que le AND est
poussé à gauche à chaque étape par le << 1 il va venir un moment où
n est trop grand pour avoir des bits en commun avec m, donc à l'étape
suivante on a n=0 et donc le while se termine et la fonction retourne
n+m puisque le dernier n vaut 0.

--
Michel Talon

[Olivier Miakinen]

Le 01/10/2022 à 12:50, Michel Talon a écrit :
>
>> 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.
>
> En fait, tel que je le vois, m+n est un invariant de la boucle. Pourquoi?
>
> m devient le XOR de m et n, c'est à dire a les bits qui sont soit dans m
> soit dans n mais pas les deux.
>
> n devient le double (à cause du << 1) du AND de m et n c'est à dire les
> bits qui sont à la fois dans m et n. Evidemment quand on fait m+n
> le AND apparaît 2 fois, et le XOR une fois, donc il est "clair" que m+n
> a la même valeur que m ^ n + (m & n) << 1.

Oui, je suis d'accord avec tout ce qui précède.

> Comme XOR(m,n) <= max(m,n) et idem pour AND(m,n) et que le AND est
> poussé à gauche à chaque étape par le << 1 il va venir un moment où
> n est trop grand pour avoir des bits en commun avec m, donc à l'étape
> suivante on a n=0 et donc le while se termine et la fonction retourne
> n+m puisque le dernier n vaut 0.

Oui, encore une fois si les deux nombres sont positifs.

Il se trouve que si les deux nombres sont négatifs, ou si l'un des
deux est négatif et que sa valeur absolue est strictement supérieure
à l'autre nombre, le while se terminera aussi.

En revanche, si la valeur absolue du nombre négatif est inférieure ou
égale au nombre positif, alors il reste vrai que m+n est un invariant
de la boucle (invariant qui est donc positif ou nul), mais cette
boucle ne se terminera jamais : m et n seront de plus en plus grands
en valeur absolue, avec m négatif et n positif.

--
Olivier Miakinen

[Olivier Miakinen]

Le 30/09/2022 à 07:17, ast a écrit :
> Devinette: Que retourne cette petite fonction python
>
> (m et n sont 2 entiers naturels)
>
>
> def f(m, n):
> while n:
> m, n = m ^ n, (m & n) << 1
> return m

Même question, en ajoutant un simple ~ à la troisième ligne :

def f(m, n):
while n:

m, n = m ^ n, (~m & n) << 1

return m

> pour ceux qui ne connaissent pas python
>
> "while n" c'est "pendant que n est non nul"
>
> ^ est l'opérateur "ou exclusif" bit à bit
> & est le "et" bit à bit
> << 1 décalage à gauche bit à bit et ajout d'un 0 à droite
>
> a, b = c, d affectation simultanée a <- c et b <- d

Toujours pour ceux qui ne connaissent pas python :

~ est l'opérateur « inverser tous les bits » (les 1 deviennent des 0
et les 0 deviennent des 1)

En particulier, si m est un nombre entier, -m est égal à (~m + 1)


--
Olivier Miakinen

[ast]

oui bien vu

m contient la somme sans les retenues et n contient les retenues
On additionne les retenues après coup, ce qui génère de nouvelles
retenues, et on réitère pendant qu'il y a des retenues.