Discussion :

[Roud9]

Bonjour,

Je dois trouver la racine carrée d'un nombre, mais pas avec Math.sqrt ou d'autres façons.
La methode que je dois utiliser est basé sur ce tableau:

Code:
CARRÉE 0 1 2 3 4 5 6 7 8 9 10 .. 15 16 17 .. 24 25 26 27
RACINE 0 1 1 1 2 2 2 2 2 3 3 .. 3 4 4 .. 4 5 5 5


Qui est sur wikipédia après le milieu de la page : http://fr.wikipedia.org/wiki/Racine_carr%C3%A9e
J'ai remarqué le zéro se répète une seule fois, le un trois fois, le trois cinq fois ... 2n-1 fois globalement.

ça fait plusieurs jours que j'essaie de trouver l'algorithme de ce tableau, mais je n'ai rien trouvé. Je demande donc votre aide pour essayer de voir les choses plus clairement.

Merci pour votre aide

[tupac25]

Tu as la formule sous le tableau:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(a+1)^2 -a^2 = 2a + 1

D'apres cette ligne tu peux recuperer la racine entiere du nombre que tu cherches:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

((a+1)^2-a^2-1)/2= la racine entiere que tu recherches

Vu que tu ne peux pas faire ^2, utilise la multiplication.

[Ivelios]

Bonjour,

Tu as besoin de 4 entiers :
n = le carré
racine = 1-2-3-4-5-6-7-8-...
impair = 3-5-7-9-11-13-15-...
sommeImpair = 3-8-15-24-35-48-...

1/ tu fais un cas particulier si n =0
2/ tu initialise racine, impair et sommeImpair
3/ tu fait une boucle tant que sommeImpair<n
3 bis/ dans la boucle tu modifie les valeurs de racine, impair et sommeImpair
4/Sortie de boucle, tu retournes racine.

Voila

[tupac25]

L'inconvéniant de ton code est qu'il doit initialiser des variables. Si il a besoin de la racine de 1.000.000, je pense pas qu'il aura la réponse.

Avec la formule donnée précédement, il lui suffit de connaitre le chiffre dont il veut la racine.

[Ivelios]

L'inconvéniant de ton code est qu'il doit initialiser des variables.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int racine = 1;
int impair = 3;
int sommeImpair = 3;
 
//Boucle
//...

Je ne vois pas en quoi c'est un inconvénient

Si il a besoin de la racine de 1.000.000, je pense pas qu'il aura la réponse.

Bâ... si il fera 999 tours dans la boucle (normal vu que 1000 c'est la racine carré)

Avec la formule donnée précédement, il lui suffit de connaitre le chiffre dont il veut la racine.

C'est surement vrai, mais je n'ai pas réussi à utiliser la réponse que tu as donné(Je sais, je suis pas doué ), donc j'ai fais ma propre version. Si tu veux m'expliquer(ré expliquer par contre je suis ouvert

[tupac25]

Oups c'est moi qui fait l'erreur. Je me suis trompé dans mes calculs. Il ne faut pas procéder de la maniere que j'ai expliquer plus haut. Mais on peut quand meme utiliser la formule car elle nous apprend que :

Le nombre de fois que l’entier n est répété est le n-ième entier impair.

Il doit etre possible d'utiliser ceci dans une boucle.

[Ivelios]

En faite, je peux optimiser un peu mon code :
Suppression de Impair et SommeImpair. Mais on garde Racine

Et pour la condition 3/ tu fait une boucle tant que sommeImpair<n,
on remplace par 3/ tu fait une boucle tant que ((racine+1)^2) -1<n

ça évite de ce trimballer 3 ints

[tchize_]

avec les flottants 16 bits, il y avait aussi cette formule d'approximation pour 1/sqrt(x) , utilisée par le code de quake III Y a surement moyen de la retourner

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;
 
  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) )
}

[Roud9]

Merci beaucoup pour vos réponses, j'ai finalement trouvé ce que je cherchais