Discussion :

[souviron34]

En moyenne on tombe à moins de 2.6 opérations (méthode avec les ifs sans dichotomie).

ça veut dire quoi "en moyenne" ???

si je suis tes calculs, 99% des cas demandent 3 tests ou moins, le reste au max jusqu'à 7 tests.


Dans mon approche, dans tous les cas le pire cas est 4.. et dans 99.999999% des cas 3...

Sauf que ceci est à prendre avec une répartition uniforme, et une requête portant sur l'ensemble..

Dans la pratique, il est peu probable que, dans la majeure partie des cas, cette fonction serve à obtenir quelque chose de supérieur à 10^7... (des indices de l'odre du milliard seront plutôt en général utilisés comme des floats, sauf pour des 64 bits, auquel cas l'adaptation de la dichotomie fourni toujours 5 tests dans le pire des cas et 4 en moyenne..)


Donc, dans la "moyenne des cas d'utilisation", tu feras de 4 à 7 tests...

Et sur un 64 bits de 9 à 15...

[valefor]

ça veut dire quoi "en moyenne" ???

Si je lance la fonction avec un jeux de test allant de 0 à 2^32-1, et que je fais la moyenne des tests que la fonction a exécuté, j'obtiendrai 2.6.

[souviron34]

et moi 2.8 (3 tests pour 71%, 2 pour 21%)

mais c'est surtout le "pire des cas", et la moyenne dans les cas "utile"...

[Djakisback]

Juste pour vous remercier pour vos réponses
Je trouve le sujet intéressant, on apprend pas mal de trucs rien qu'avec une petite fonction.

(@valefor : oops j'avais pas vu ton lien)