Racine carré en binaire

[inviteadeaae55]

Bonjour à tous.
J'ai longuement cherché sur le net mais en vain, alors je vous pose la question, savez-vous si il existe un algorithme pour trouver des racines carrés en binaire ?

Merci de vos réponses Bonne soirée.
-----

[Jack]

je ne comprends pas la question. La racine carrée d'un nombre est la même quelle que soit la base. Donc n'importe quel algo d'extraction de racine carrée conviendra.

[inviteadeaae55]

En effet,je ne pensais pas que les algorithmes de bases 10 marchaient forcément dans d'autres bases. Merci de ta réponse.

[Jack]

La base n'a rien à voir la dedans. Au bout du compte dans un ordinateur, c'est toujours du binaire.

A+

[A voir en vidéo sur Futura]

[invitebac61674]

Tu peux facilement diviser par deux en binaire en décalant tout les bits vers la droite. (et multiplier en décalant vers la gauche).

Mais il n'y a pas d'astuce équivalente pour les racines carrées. Comme dit Jack la racine carrée d'un nombre sera toujours la même quelle que soit la base.

[invitefa15af9f]

Bonjour

Bonjour à tous.
J'ai longuement cherché sur le net mais en vain, alors je vous pose la question, savez-vous si il existe un algorithme pour trouver des racines carrés en binaire ?

Merci de vos réponses Bonne soirée.

pourquoi ne pas faire l'opération dans la base 10 ? ensuite tu n'as qu'à faire la conversion de la base 10 vers la base 2.
A+

[invite936c567e]

Bonjour

Sur le principe, l'algorithme d'extraction de racine carrée en base 2 est la même que celle en base 10 qu'on réalise à la main.

Toutefois, la base 2 procure des avantages qui permettent une grande simplification.

Voici par exemple le code source en C du calcul de la racine carrée d'un entier sur 32 bits :

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;
}

(u16 et u32 définissent des types entiers non signés, respectivement sur 16 et 32 bits)

[invite936c567e]

Pour la petite histoire, voici la méthode d'extraction "à la main", telle qu'elle était enseignée au lycée il y a une cinquantaine d'années (comme quoi les bonnes choses se perdent) :

REGLE PRATIQUE
1. Ecrire le nombre dont on veut extraire la racine comme le dividende d'une division.
2. Séparer en tranches de deux chiffres à partir de la droite ; la dernière tranche à gauche peut n'avoir qu'un chiffre.
3. Extraire la racine de la première tranche à gauche ; on obtient ainsi le premier chiffre de la racine cherchée qu'on écrit à la place du diviseur habituel.
4. Retrancher le carré de ce nombre d'un chiffre de la première tranche à gauche.
5. Abaisser à droite du résultat de la soustraction précédente (premier reste partiel), la tranche suivante.
6. Séparer dans le nombre obtenu le dernier chiffre à droite et diviser le nombre restant par le double du nombre d'un chiffre écrit à la place du diviseur ; on écrit le double de ce nombre à la place du quotient.
7. Si le quotient est inférieur à 10 l'essayer, sinon commencer par essayer 9 ; l'essai se fait en écrivant ce quotient à droite du double de la racine de la première tranche et en multipliant le nombre obtenu par le quotient considéré. Si le produit peut être retranché du nombre formé au 5, le quotient convient, sinon on essaie un nombre inférieur jusqu'à ce que la soustraction soit possible.
8. Le résultat de la soustraction est le deuxième reste partiel. Ecrire le nombre essayé à droite du premier chiffre écrit à la place du diviseur.
9. Recommencer avec le deuxième reste partiel comme avec le premier et ainsi de suite, jusqu'à ce que l'on ait utilisé toutes les tranches. Le dernier reste partiel est le reste de la racine carrée.

(Source: manuel de Terminale C et T - V. Lespinard et R. Pernet - 1968)

[invite936c567e]

Les calculs de racine carrée entière que je viens de donner ci-dessus peuvent être continués en suivant le même procédé afin d'obtenir autant de chiffre après la virgule que nécessaire.