Algorithme de la racine carrée en binaire implémentée

[invite457e1a8a]

Bonjour, je dois implémanter la racine carrée en binaire. J'ai trouvé un algorithme qui permet de faire sa et le voila :

u16 racine(u32 valIn)
{
	u16 valOut = 0;
	u32 diff = 0L;

	for( int i=0 ; i<16 ; i++ ) {
		diff <<= 2;
		valOut <<= 1;

		diff |= valIn>>30;
		valIn <<= 2;

		if( diff>2*valOut ) {
			diff -= 2*valOut+1;
			valOut++;
		}
	}
	return valOut;
}

Ici u16 et u32 représentent des entiers respectivement de 16 et 32 bits.
Je l'ai implémenté en c++ et voici le code :

unsigned int racine(unsigned long int valIn)
{
	unsigned int valOut = 0;
	unsigned long int diff = 0L;

	for( int i=0 ; i<16 ; i++ ) {
		diff <<= 2;
		valOut <<= 1;

		diff |= valIn>>30;
		valIn <<= 2;

		if( diff>2*valOut ) {
			diff -= 2*valOut+1;
			valOut++;
		}
	}
	return valOut;
}

int main() {
unsigned int valIn = 0b00000000000000000000000000010000;
cout << racine(valIn) << endl;
return 1;
}

Comme vous avez pu le voir, j'ai essayé l'algorithme en rentrant la valeur 16 en binaire et cela me retourne 5.
Je me demande donc s'il y a un problème avec mon implémentation.
Je vous remerci d'avance de votre aide m'excuse du dérangement occasioné.
-----

[PA5CAL]

Bonsoir

L'algorithme est bon, et le code ci-dessus donne des résultats corrects sous Windows, compilé avec GCC.

Néanmoins, tout-à-l'heure j'ai pu reproduire le problème sous MacOs X, avec une version plus ancienne de GCC.

Peut-être s'agit-il d'un problème lié à l'interprétation du code par le compilateur ??

Je tenterai de trouver où se situe l'erreur et comment la contourner quand j'aurai de nouveau mon Mac sous la main.

[PA5CAL]

J'ai trouvé la source du problème. En fait elle n'est pas liée à la version du compilateur, mais à l'architecture de la machine cible.

En effet, ce code a été conçu pour une architecture 32 bits, de sorte que la ligne de code :

    valIn <<= 2;

supprime les deux bits de poids fort décalés.

Or, dans une architecture 64 bits (unsigned long sur 8 octets), ces deux bits sont conservés, et faussent le calcul.

Pour régler le problème, il suffit de rajouter, immédiatement après, une ligne :

    valIn &= 0xFFFFFFFFUL;

La fonction devient donc :

unsigned int racine(unsigned long int valIn)
{
	unsigned int valOut = 0;
	unsigned long int diff = 0L;

	for( int i=0 ; i<16 ; i++ ) {
		diff <<= 2;
		valOut <<= 1;

		diff |= valIn>>30;
		valIn <<= 2;
		valIn &= 0xFFFFFFFFUL;

		if( diff>2*valOut ) {
			diff -= 2*valOut+1;
			valOut++;
		}
	}
	return valOut;
}

[invite457e1a8a]

Oui c'est parfait cela marche très bien merci beaucoup.

[A voir en vidéo sur Futura]