Path: ...!weretis.net!feeder8.news.weretis.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?[Ma_r=c3=a9ponse]_Re:_Probl=c3=a8me_de_l'arr=c3=aat?=
Date: Fri, 30 Sep 2022 22:48:46 +0200
Organization: There's no cabale
Lines: 60
Message-ID: <th7kne$alv$1@cabale.usenet-fr.net>
References: <63367bdd$0$25804$426a74cc@news.free.fr>
 <th6hru$248k$1@cabale.usenet-fr.net>
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 1664570926 10943 77.205.12.220 (30 Sep 2022 20:48:46 GMT)
X-Complaints-To: abuse@usenet-fr.net
NNTP-Posting-Date: Fri, 30 Sep 2022 20:48:46 +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: <th6hru$248k$1@cabale.usenet-fr.net>
Bytes: 3211

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