02 sept. 2013

Racine d'un entier 64 bits non signé en C

Ce billet est un peu spécial, dans le sens ou je me contente de poster un morceau de code sans beaucoup de commentaires. J'ai écrit ce code récemment pour résoudre un problème un peu agaçant : calculer une racine carrée sur un nombre entier 64 bits.

Pour ceux qui se disent que le problème est simple (appeler la fonction sqrt() de la librairie C ou std::sqlt() de la librairie standard C++), je répond "oui, presque". Parce qu'un nombre non signé de 64 bits ne peut étre représenté correctement sur un double de 64 bits (sqrt() utilise le co-processeur arithmétique de votre x86). On peut utiliser un long double - mais dans ce cas, les performances sont désastreuses (parce que votre processeur n'a pas de registre générique travaillant en 80 bits).

Tout ça pour dire que la fonction ci-dessous peut aussi vous être utile (même si elle n'est pas parfaite : elle dépends principalement de la réponse à une devinette : quelle est la valeur de la racine carrée que je cherche ? Plus je sais répondre précisément à cette devinette, plus l'exécution est rapide).

Lire la suite...