Défi : racine carrée ... sans sqrt()

International Français Le bar
1

bonjour/bonsoir à tous (suivant l'heure à laquelle vous allez me lire)

ce sujet m'a inspiré

à mon tour je vous propose un ''défi'', comme on pouvait en trouver au cours des années '80 dans les pages de l'Ordinateur de Poche (p.t..n de nostalgie pour ceux qui ont connu !)

je précise d'emblée qu'il n'est ici aucunement question de concurrencer la fonction sqrt() de la bibli math.h fournie avec le langage C/C++ et ses divers compilateurs : elle est, au vu des tests que j'ai déjà effectués, tellement efficace qu'il me semble inutile d'essayer de la surpasser.

non, ce que j'attends de vous (c'est pompeux cette formulation, je sais, mais je n'ai rien d'autre sous la main, je manque de vocabulaire) c'est de calculer une racine carrée sur un entier (et non un nombre à virgule : ça peut sembler plus simple ... et rapide ?) en n'utilisant que les ''4 opérations'' de base, à savoir + - * /, plus bien sûr les décalages de bits (rapides) et éventuellement d'autres fioritures, mais seulement des instructions ''de base''.

le but du jeu est ici de créer la fonction (ou les fonctions, suivant la taille du nombre fourni en paramètre, le langage C étant capable de différencier les différentes fonctions suivant le cas) qui permettra de calculer la valeur le plus rapidement possible.

pour vous aider dans vos recherches de solutions, l'une de mes préférées est basée sur une méthode perso (même si inspirée par d'autres, mais je ne vous dirai pas qui ... avant d'avoir vos solutions) mais ne me donne pas entière satisfaction ... et pourtant elle me permet de calculer une racine carrée à la main, juste avec un crayon et du papier, même sans calculette ! (mais avec du temps !)

EDIT:
au vu des incompréhensions (l'expression de l'énoncé n'était pas assez claire) j'apporte après certaines réponses quelques précisions :

  • pour commencer, et pour mettre toutes les solutions sur un même pied d'égalité, la fonction doit être compilée pour un classique cœur AVR, c'est-à-dire un ATMega (328 ou 2560, par exemple) ;

  • on cherche à calculer la racine carrée d'un nombre entier, sous la forme d'un entier également (pas de partie décimale, donc) mais tous les chiffres calculés doivent être exacts, ou à la rigueur représenter un arrondi exact : xxx5,6 peut éventuellement donner xxx6 ;

  • la fonction doit, sur la même machine (Uno, Nano, Mega ...), s'exécuter le plus rapidement possible ... mais prenez vous-même le temps nécessaire à sa mise au point ; j'utilise pour mes chronométrages un timer avec un prescaler de 1/1, ce qui me donne des durées d'exécution mesurées en cycles de 62,5ns pour une horloge à 16MHz.

mon but est de permettre une compilation des différentes méthodes (connues, moins connues, voire carrément nouvelles) et d'amener à une discussion sur l'efficacité de l'une ou l'autre.

(merci, déjà, à ceux qui ont commencé à participer)

2

Je vais essayer avec un condensateur comme dans le défi précédent. Vu que E=½CV2 (E c'est l'énergie, V c'est l'attention) soit encore V=√(2E/< je sais >)
J'ai de l'énergie pour résoudre ce problème, il me suffit alors d'avoir de l'attention. et ce sera réglé!
J'ai la nuit pour cela...

3

Il existe une théorie mathématique (sous forme de divisions) pour le faire, je l'ai vu au lycée,ce devait être en terminale, je l'ai totalement oublié.
Si quelqu'un pouvait l'a rexpliquer je suis preneur.

1 Like
4

Bonjour, @68tjs
https://fr.wikihow.com/calculer-une-racine-carr%C3%A9e-%C3%A0-la-main

5

J'ai trouvé!

uint32_t entier = 1234567890ul; // Nombre pour lequel je veux sa racine
uint32_t racine; // résultat qui d'ailleurs tient dans un uint16_t, mais c'est pour éviter des casts

void setup()
{
  Serial.begin(115200);
  racine = 0; // Comme moi, la racine est nulle au commencement
  while ((racine+1) * (racine+1) < entier) racine++; // Petit à petit l'oiseau fait son nid

  // Vérification
  Serial.print("La racine carrée de "); Serial.print(entier); Serial.print(" est "); Serial.println(racine);
  Serial.print("Car ");
  Serial.print(racine); Serial.print("x"); Serial.print(racine); Serial.print("="); Serial.print(racine*racine); 
  Serial.print(" < ");
  Serial.print(entier);
  Serial.print(" < ");
  Serial.print(racine+1); Serial.print("x"); Serial.print(racine+1); Serial.print("="); 
  Serial.println((racine+1)*(racine+1));
}

void loop(){}

résultat:

La racine carrée de 1234567890 est 35136
Car 35136x35136=1234538496 < 1234567890 < 35137x35137=1234608769

Je n'ai mis moins d'une minute à écrire la partie qui extrait la racine. Toute autre méthode me prendra plus de temps.
Dans "le plus rapidement possible", j'ai supposé que c'était "pour moi".

6

Ya bien une solution, mais elle n'utilise pas ni les divisions ni les multiplications:


uint32_t racineCarree(uint32_t entier)
{
  uint32_t racine = 0, // Résultat qui d'ailleurs tient dans un uint16_t, mais c'est pour éviter des casts
           reste = 0, // Reste à traiter
           temp; // Pour faire des calculs

  for (byte boucle=0; boucle<16; boucle++) // 32 bits, pris deux à deux soit 16 boucles
  {
    reste = (reste << 2) + (entier >> 30); // Nouveau nombre à traiter
    entier <<= 2; // On se prépare pour la prochaine fois
    temp = (racine <<=1) << 1;
    if (temp < reste) // Le chiffre suivant est 1
    {
      reste -= temp+1;
      racine++;
    }
  }
  return racine;
}


void setup()
{
  Serial.begin(115200);
}


uint32_t entier, racine;
void loop()
{
  // Calcul
  entier=random(); // [edit] au lieu de random(0x7FFFFFFF);
  racine=racineCarree(entier);

  // Vérification
  if ((racine*racine <= entier) && ((racine+1)*(racine+1) > entier))
  {
    Serial.print("\nLa racine carrée de "); Serial.print(entier); Serial.print(" est "); Serial.println(racine);
    Serial.print("Car ");
    Serial.print(racine); Serial.print("x"); Serial.print(racine); Serial.print("="); Serial.print(racine*racine); 
    Serial.print(" <= ");
    Serial.print(entier);
    Serial.print(" < ");
    Serial.print(racine+1); Serial.print("x"); Serial.print(racine+1); Serial.print("="); 
    Serial.println((racine+1)*(racine+1));
  }
  else Serial.println("Erreur!");

  // Pas trop souvent
  delay(1000);
}
1 Like
7

hello
celle ci, je l'aime bien :+1:

8

Merci,
C'est la méthode 2.

9

Si on ne veut pas faire de tests, on peut utiliser la méthode de Newton.

Pour calculer la racine carrée du nombre a, on prend la fonction f(x) = 0.5 (x + a/x) et on itère à partir d'une valeur initiale, par exemple la valeur de a.
Bien sûr il faut calculer avec des float mais ça converge assez rapidement vers une valeur proche de la racine carrée recherchée.

Ce n'est pas très dur à écrire en C.

1 Like
10

oups !

je m'aperçois m'être mal exprimé :
quand j'ai écrit ''le plus rapidement possible' je me référais au temps d'exécution de la fonction (sur un même cœur de calcul), pas de celui nécessaire à sa création.

j'ai modifié mon message d'entrée (#1) en conséquence.

11

Dans ce sas le post #6 répond au problème.

D'ailleurs cela fonctionne aussi si on veut un résultat avec un réel (mais c'est hors sujet défi).

uint32_t racineCarree(uint32_t entier)
{
  uint32_t racine = 0, // Résultat qui d'ailleurs tient dans un uint16_t, mais c'est pour éviter des casts
           reste = 0, // Reste à traiter
           temp; // Pour faire des calculs

  for (byte boucle=0; boucle<32; boucle++) // 32 bits, pris deux à deux soit 16 boucles
  {
    reste = (reste << 2) + (entier >> 30); // Nouveau nombre à traiter
    entier <<= 2; // On se prépare pour la prochaine fois
    temp = (racine <<=1) << 1;
    if (temp < reste) // Le chiffre suivant est 1
    {
      reste -= temp+1;
      racine++;
    }
  }
  return racine;
}


void setup()
{
  Serial.begin(115200);
}


uint32_t entier;
float racine;
void loop()
{
  // Calcul
  entier=random(0x7FFFFFFF);
  racine=float(racineCarree(entier))/65536.0;

  // Vérification
  if ((racine*racine <= entier) && ((racine+1)*(racine+1) > entier))
  {
    Serial.print("\nLa racine carrée de "); Serial.print(entier); Serial.print(" est "); Serial.println(racine,6);
    Serial.print("Car ");
    Serial.print(racine); Serial.print("x"); Serial.print(racine); Serial.print("="); Serial.print(racine*racine); 
    Serial.print(" <= ");
    Serial.print(entier);
    Serial.print(" < ");
    Serial.print(racine+1); Serial.print("x"); Serial.print(racine+1); Serial.print("="); 
    Serial.println((racine+1)*(racine+1));
  }
  else Serial.println("Erreur!");

  // Pas trop souvent
  delay(10000);
}
12

Mais non, c'était très clair, mais j'avais pas le choix, je ne savais pas extraire une racine carrée. J'avais essayé il y a longtemps mais je n'y avais rien compris. Cela s'appelle plutôt du détournement de consignes.

Note: Au passage, vu qu'il n'y avait qu'une seule réponse, c'était la plus rapide! Et comme je ne savais faire qu'elle, c'était le plus rapidement possible (pour moi). Tant qu'à être de mauvaise foi, autant l'être jusqu'au bout!

Note: le temps de chronométrage dépend pas mal du nombre, si c'est un entier 8, 16, 32 ou 64 bits, ainsi que de la valeur elle même suivant par exemple que le résultat est 10000 ou 11111; les tests donnent un temps d'exécution différent si on rentre dans des test conditionnels ou pas.

13

Version 3: Sans doute plus rapide. Ecrit pour des bytes, mais on devrait pouvoir le faire pour des words:

byte racineCarree(byte entier)
{
  if (entier >= 8*8)
  {
    if (entier >= 12*12)
    {
      if (entier >= 14*14)
      {
        if (entier >= 15*15) return 15;
        else return 14;
      }
      else
      {
        if (entier >= 13*13) return 13;
        else return 12;
      }
    }
    else
    {
      if (entier >= 10)
      {
        if (entier >= 11*11) return 11;
        else return 10;
      }
      else
      {
        if (entier >= 9*9) return 9;
        else return 8;
      }
    }
  }
  else
  {
    if (entier >= 4*4)
    {
      if (entier >= 6*6)
      {
        if (entier >= 7*7) return 7;
        else return 6;
      }
      else
      {
        if (entier >= 5*5) return 5;
        else return 4;
      }
    }
    else
    {
      if (entier >= 2*2)
      {
        if (entier >= 3*3) return 3;
        else return 2;
      }
      else
      {
        if (entier >= 1*1) return 1;
        else return 0;
      }
    }
  }
}


void setup()
{
  Serial.begin(115200);
}


byte entier, racine;
void loop()
{
  // Calcul
  racine=racineCarree(entier=random(0xFF));

  // Vérification
  if ((racine*racine <= entier) && ((racine+1)*(racine+1) > entier))
  {
    Serial.print("\nLa racine carrée de "); Serial.print(entier); Serial.print(" est "); Serial.println(racine);
    Serial.print("Car ");
    Serial.print(racine); Serial.print("x"); Serial.print(racine); Serial.print("="); Serial.print(racine*racine); 
    Serial.print(" <= ");
    Serial.print(entier);
    Serial.print(" < ");
    Serial.print(racine+1); Serial.print("x"); Serial.print(racine+1); Serial.print("="); 
    Serial.println((racine+1)*(racine+1));
  }
  else Serial.println("Erreur!");

  // Pas trop souvent
  delay(10000);
}

Ce code est sans doute plus rapide que celui de mes versions 1 et 2, mais on ne le passera jamais avec des uint32_t.

Il y a des catégories (nombres dans un byte, un word...)?

14

Version n°4 pour la catégorie entiers de 1 bits. Je pense qu'on ne peut pas aller plus vite:

boolean racineCarree(boolean entier)
{
  return entier;
}


void setup()
{
  Serial.begin(115200);
}


boolean entier, racine;
void loop()
{
  // Calcul
  entier=random(2);
  racine=racineCarree(entier);

  // Vérification
  if (racine*racine == entier)
  {
    Serial.print("\nLa racine carrée de "); Serial.print(entier); Serial.print(" est "); Serial.println(racine);
    Serial.print("Car ");
    Serial.print(racine); Serial.print("x"); Serial.print(racine); Serial.print("="); Serial.println(racine*racine); 
  }
  else Serial.println("Erreur!");

  // Pas trop souvent
  delay(1000);
}
15

J'ai relu les règles du post du début : je propose ça (tapé ici, pas vérifié)

void setup() {
Serial.begin(115200);
}

uint32_t entier, racine;
void loop()
{
  // Calcul
  entier=random(0x7FFFFFFF);
  float x = entier;
  x = 0.5 * (x + entier / x);
  x = 0.5 * (x + entier / x);
  x = 0.5 * (x + entier / x);
  x = 0.5 * (x + entier / x);
  x = 0.5 * (x + entier / x);
  racine = (int) x;
  Serial.print("\nLa racine carrée de "); Serial.print(entier); Serial.print(" est "); Serial.println(racine);
  // Pas trop souvent
  delay(1000);
}

J'ai repris des lignes du code d'Olivier... Merci !

@5_cylindres : tu vas faire un benchmark ?

16

hello
chatGPT et moi :innocent: :grinning:

double racine_newton(double x) {
  double approximation = x;
  double precision = 0.0001;  // Précision souhaitée
  while ((approximation * approximation - x) > precision) {
    approximation = 0.5 * (approximation + x / approximation);
  }
  return approximation;
}
void setup() {
  Serial.begin(115200);
}
void loop() {
  
  double nombre=random(0x7fff);Serial.println(nombre);
  unsigned long deb=micros();
  double resultat = racine_newton(nombre);
  Serial.print(F("racine extraite en "));Serial.print(micros()-deb);Serial.println(F(" microsecondes"));
  Serial.print(F("la racine carrée de ")); Serial.print(nombre);
  Serial.print(F(" est ")); Serial.println(resultat);
  delay(2000);
}
17

En fait cela ne converge pas si vite, total x dépasse souvent l'int. Il faut mettre au moins
racine = (uint32_t) x;
J'ai l'impression qu'il faut 10 à 15 itérations pour que cela converge avec un uint16_t et 20 à 25 pour un uint32_t.

Il est dit aussi

la fonction doit

il faut donc faire une fonction (besoin du chronométrage).

Sauf que là on mesure le temps du Serial.print(F("racine extraite en ")); en plus

La précision de 0,1 suffit largement. En prennant 0,0001 à cause des arrondis sur AVR (

la fonction doit être compilée pour un classique cœur AVR

), la série converge vers un nombre qui ne satisfait pas le while, et la fonction a un temps infini.

Si on travaille avec des bytes ou des word, on peut utiliser des float (= doubles pour les AVR), mais la précision des réels est de 6 à 7 chiffres, on ne peut plus représenter les uint32_t à une unité près, et donc plus calculer avec. Mais à priori, on devrait pouvoir travailler avec des entiers et pas des réels.
18

J'avais mis cela pour avoir un nombre le plus grand possible. et random admet un long et pas un unsigned long. En mettant un nombre négatif, cela ne fonctionne pas. Il suffit en fait de mettre:

pour avoir un pseudo-aléatoire sur 32 bits

19

bonsoir,

tout d'abord merci pour les réponses, je ne m'attendais pas à vous passionner autant avec ça !

j'examinerai les solutions proposées plus tard, pour l'instant je vais essayer de répondre au coup par coup.

20

salut @68tjs
je ne me souviens plus non plus de cette méthode (pourtant vue aussi) mais le problème ici est que les AVR ne possédant pas la division câblée l'algorithme créé par le compilateur induit des temps de calcul trop longs ...