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: Fri, 30 Sep 2022 21:46:09 +0200
Organization: There's no cabale
Lines: 59
Message-ID: <th7h21$9vi$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>
NNTP-Posting-Host: 220.12.205.77.rev.sfr.net
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: 8bit
X-Trace: cabale.usenet-fr.net 1664567169 10226 77.205.12.220 (30 Sep 2022 19:46:09 GMT)
X-Complaints-To: abuse@usenet-fr.net
NNTP-Posting-Date: Fri, 30 Sep 2022 19:46:09 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Firefox/52.0 SeaMonkey/2.49.4
In-Reply-To: <th7124$1l9b$1@gioia.aioe.org>
Bytes: 2687

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