Path: ...!news.mixmin.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!.POSTED!not-for-mail
From: Olivier Miakinen <om+news@miakinen.net>
Newsgroups: fr.sci.maths
Subject: =?UTF-8?Q?Re:_Probl=c3=a8me_de_l'arr=c3=aat?=
Date: Sat, 1 Oct 2022 14:38:27 +0200
Organization: There's no cabale
Lines: 38
Message-ID: <th9cc5$nfr$1@cabale.usenet-fr.net>
References: <63367bdd$0$25804$426a74cc@news.free.fr>
 <th6hru$248k$1@cabale.usenet-fr.net> <th7124$1l9b$1@gioia.aioe.org>
 <th7h21$9vi$1@cabale.usenet-fr.net> <63381b70$0$25834$426a74cc@news.free.fr>
NNTP-Posting-Host: 37.167.152.183
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: cabale.usenet-fr.net 1664627909 24059 37.167.152.183 (1 Oct 2022 12:38:29 GMT)
X-Complaints-To: abuse@usenet-fr.net
NNTP-Posting-Date: Sat, 1 Oct 2022 12:38:29 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
 Firefox/60.0 SeaMonkey/2.53.1
In-Reply-To: <63381b70$0$25834$426a74cc@news.free.fr>
Bytes: 2807

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