EXTRACTION D'UNE RACINE CARRÉE

Commentaire de BruNews le 04/08/2005 12:13:00 administrateur CS

Tu es certain que c'est plus performant que sqrt() ???

Commentaire de Tripo le 04/08/2005 12:40:22

Je ne sais pas s'il est plus rapide...
Le but n'était pas d'améliorer mais de montrer comment extraire une racine "à la main".

Pour ce qui est du String retourner, c'est juste une question d'affichage, le programme pet être modifier pour retourner autre chose, je souhaitais juste montrer le traitement, pas faire un programme tip top.

Commentaire de BruNews le 04/08/2005 12:55:51 administrateur CS

ah je n'aurais pas cru, je vais tester sur 32 et 64 bits.

Commentaire de BruNews le 04/08/2005 14:05:23 administrateur CS

Alors après tests, sqrt() est énormément + rapide.
J'ai enlevé les String(eries) pour essayer d'accélérer mais rien n'y fait.
bnPrecis.dll dans mes sources pour bnTicksStart() et bnTicksResult().

void racine(__int64 nbr, int pres, char *psz)
{
  char *c;
  int precision = 0;
  __int64 res, tmp, courant;
  // compteurs
  int cpt, tmpVar, compteur=0;
  precision = pres;
  courant = (__int64) premiers(nbr);
  nbr = apresPremiers(nbr);
  cpt = carreInferieur((int) courant);
  res = cpt;
  // stockage pour l'affichage
  //var.getIntValue(cpt);
  //renvoie = renvoie + var;
  ultoa(cpt, psz, 10);
  c = psz;
  while(*c) c++;
  courant = courant - (cpt*cpt);
  while(nbr != 0) {
    cpt = premiers(nbr);
    courant = (courant*100) + cpt;
    nbr = apresPremiers(nbr);
    tmp = res*2;
    tmpVar = (int) ((courant/10)/tmp);
    while(courant < (((tmp*10)+tmpVar) * tmpVar) ) tmpVar--;
    res = (res*10) + tmpVar;
    //var.getIntValue(tmpVar);
    //renvoie = renvoie + var;
    ultoa(tmpVar, c, 10);
    while(*c) c++;
    courant -= ((tmp*10)+tmpVar) * tmpVar;
  }
  if(precision != 0) {
    *c++ = ','; *c = 0;
    while(compteur != precision) {
      courant *= 100;
      tmp = res*2;
      tmpVar = (int) ((courant/10)/tmp);
      while(courant < (((tmp*10)+tmpVar) * tmpVar) ) tmpVar--;
      res = (res*10) + tmpVar;
      //var.getIntValue(tmpVar);
      //renvoie = renvoie + var;
      ultoa(tmpVar, c, 10);
      while(*c) c++;
      courant -= ((tmp*10)+tmpVar) * tmpVar;
      compteur++;
    }
  }
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE x, PSTR y, int z)
{
  char buf[40];
  int n, i;
  tmps = 0;
  tmps1 = 0;
  i = 1000;
  bnTicksStart();
  do {
    racine(99986984, 0, buf);
    tmps += bnTicksResult();
  } while(--i);
  MessageBox(0, buf, szappname, 0);
  
  i = 1000;
  bnTicksStart();
  do {
    n = (int) sqrt(99986984);
    itoa(n, buf,10);
    tmps1 += bnTicksResult();
  } while(--i);
  MessageBox(0, buf, szappname, 0);
  
  _ui64toa(tmps, buf, 10);
  MessageBox(0, buf, szappname, 0);
  _ui64toa(tmps1, buf, 10);
  MessageBox(0, buf, szappname, 0);
  
  return 0;
}

Commentaire de skone007 le 04/08/2005 15:02:18

Ouaih en effet c'est plus rapide mais si on fait racine de -1 ca donne quoi faudrait gerer ce cas et c'est parfais et même le faire en ASM ca serai encore plus rapide ...

Commentaire de BruNews le 04/08/2005 15:57:00 administrateur CS

y a même quasi rien à gagner en asm, les multiplications et divisions en boucle plombent les perfs.
En tout cas c'est sympa comme algo, tu peux nous en sortir d'autres.

Commentaire de vecchio56 le 04/08/2005 19:17:17 administrateur CS

Justement je cherche a calculer rapidement la partie entiere de la racine carrée d'un entier, mais j'y arrive pas
Pour cette source: http://www.cppfrance.com/code.aspx?ID=19105
Si quelqu'un a une piste

Commentaire de vecchio56 le 04/08/2005 19:44:06 administrateur CS

C'étati une classe protable au debut, si je commence a mettre de l'asm dedans c'est pas bon

Commentaire de vecchio56 le 04/08/2005 20:24:47 administrateur CS

l'utilisation de sqrt n'est pas immédiate, tu a regardé la mise en oeuvre?
Je peux faire une boucle mais avec une incrémentation variable (je monte de plus en plus, dès que je dépasse je descend un peu puis de plus en plus, et je finis par converger assez vite, mais ca j'arrive pas trop à le faire)

Commentaire de Skaaar le 04/08/2005 22:10:45

Je pense que beaucoup ici n'ont pas compris le but de la source...
Il s'agissait d'expliquer comment on peut calculer une racine carrée à la main, pas d'annalyser les perfs d'une méthode qui est évidement la plus efficace d'un point de vue algorythmique (sqrt()). Ceux qui ont concu ce language à mon avis ont passé quelques heures à concevoir cette fonction pour quelle soit la plus efficace possible.
A bon entendeur,
Ciao ++

Commentaire de Kirua le 05/08/2005 01:56:24

pour trouver la partie entière d'une racine carrée sans utiliser sqrt, j'avais écrit cet algo il y a qq mois, en découvrant une curiosité par hasard, je te tape le code avec le commentaire:

int Racine(unsigned int n)
{
//on évacue d'abord un cas gênant
if(n == 0) return 0;
//on peut énumérer tous les carrés
//naturels très simplement en ajoutant
//le prochain impair dans une liste:
//0
//0 + 1 = 1
//1 + 3 = 4
//4 + 5 = 9
//9 + 7 = 16
//...
//On va parcourir la liste des carrés naturels, et lorsqu'on a dépassé
//le nombre demandé, on sait quelle est sa racine carrée naturelle.
//Illustration: tous les nombres de 9 à 15 compris doivent retourner 3
//comme réponse, donc on peut passer tout de suite de 9 à 16. Si n est
//>= à 9 mais < 16, alors la réponse est 3 (et on retourne Ret).

unsigned int Ret = 0;
unsigned int Carre = 1;
unsigned int ListeImpairs = 1;

for(; Carre <= n; Ret++)
{
ListeImpairs += 2;
Carre += ListeImpairs;
}

return Ret;
}

j'avais écrit ça pour un exercice sur le site de prologin.

Commentaire de cosmobob le 05/08/2005 10:46:17

extraction d'une racine carré d'un entier en un temps en log(n) :

int mysqrt(int a)
{
int gauche = 0;
int droite = a;

while (droite - gauche > 1)
{
int milieu = (droite + gauche) / 2;
if (milieu*milieu > a)
{
droite = milieu;
}
else
{
gauche = milieu;
}
}
return gauche;
}

Commentaire de cosmobob le 05/08/2005 11:50:37

a part pour a = 1 (ca rentre pas ds la boucle), oui
(t'as continuellement gauche² <= a et droite² > a, donc quand droite-gauche<=1, t'es assuré que gauche est le plus grand entier tel que gauche² <= a)

Commentaire de cosmobob le 05/08/2005 12:12:53

non, mais ya un overflow intermédiaire ;) (le milieu²)

Commentaire de BruNews le 05/08/2005 12:24:44 administrateur CS

Va bon ainsi, résultats exacts.

Commentaire de JCDjcd le 05/08/2005 15:17:29

En dix itérations de l'algorithme de Newton (méthode des tangentes) on obtient une bonne approximation.

Commentaire de Arnaud16022 le 06/08/2005 01:50:59

oh et pour Kirua : t'es pas bete toi ^^ tu la tires d'ou cette méthode?

Commentaire de Kirua le 03/09/2005 03:10:20

arnaud, je l'ai trouvée en griffonant sur un bout de papier.
quant à "c'est une trouvaille ça", ben je trouve que oui, dans la mesure où je ne risque vraiment pas d'overflow, que je ne bosse qu'avec des entiers, que c'est élégant, que c'est du sûr, que c'est indirect... la recherche dichotomique je l'ai faite aussi, t'en fais pas, et c'est très bien si tu veux une approximation avec virgule flottante, mais c'était pas la question, comme j'ai précisé: fallait le naturel égal ou inférieur.
au passage, ma recherche dichotomique était environ 25 fois plus lente que la version de la librairie standard, qui, je suppose, fait appel au FPU d'Intel, donc bon ^^.