Répondre à la discussion
Affichage des résultats 1 à 15 sur 15

Racine carrée



  1. #1
    edje

    Racine carrée


    ------

    Bonjours,
    jusqu'a present je ne m'etais jamais posé la question à savoir comment un ordinateur calculais une racine carrée. Or maintenant je dois implémenter cette fonction dans un FPGA et c'est horriblement compliqué! Le manque de precision des divisions m'interdie leurs utilisations, les multiplications prennent trop de ressources! Je ne m'en sors pas. Est-ce que quelqu'un connait un algortihme autre que Newton-Raphson qui soit utilisable?

    -----

  2. Publicité
  3. #2
    edje

    Re : Racine carrée

    Il semblerait apres quelques recherchequ'une bonne solution pourrait etre l'algorithme de CORDIC mais je n'en sais pas plus!

  4. #3
    doryphore

    Cool Re : Racine carrée

    Et les fractions continues, ça ne te tente pas.
    Sinon pour Cordic, je ne connaissais pas.
    Apparemment, c'est utilisé pour les fonctions trigonométriques.
    "Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein

  5. #4
    edje

    Re : Racine carrée

    Oui, cordic est utiliser pour les fonctions trigonometriques mais on peut s'en servir apparement pour retrouver l'amplitude d'un vecteur et meme des systemes du type: R=[X²+mY²]^(1/2), avec m qui peut prendre les valeurs -1,0,1.
    Par contre c'est quoi exactement les fractions continues?

  6. #5
    TToufik

    Re : Racine carrée

    Bonjour,
    essai ce lien tu trouvera peut etre ton bonheur:
    http://cel.ccsd.cnrs.fr/cours/cel-19/numeri.pdf
    amicalement TToufik.

  7. A voir en vidéo sur Futura
  8. #6
    TToufik

    Re : Racine carrée

    Bonjour,
    essai ces deux liens; tu trouvera peut etre ton bonheur:
    http://cel.ccsd.cnrs.fr/cours/cel-19/cel-19.html
    http://cel.ccsd.cnrs.fr/cours/cel-19/numeri.pdf
    amicalement TToufik.

  9. Publicité
  10. #7
    TToufik

    Re : Racine carrée

    essai ça aussi il y a une partie consacré pour l'algoritme de CORDIC
    http://faq.maths.free.fr/html
    http://faq.maths.free.fr/html/node3.html
    Dernière modification par TToufik ; 10/08/2004 à 15h49. Motif: oblie

  11. #8
    doryphore

    Smile Re : Racine carrée

    Citation Envoyé par edje
    Par contre c'est quoi exactement les fractions continues?
    http://villemin.gerard.free.fr/ThNbDemo/Heron.htm

    Approximation de la racine carrée de 2 par la méthode des fractions continues.
    "Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein

  12. #9
    cricri

    Re : Racine carrée

    racine carre c est simple c est
    racine de N =x

    n-1 cest n indice d avant

    tu prend la suite xn =(N/xn-1+xn-1)/2 qui multiplie le nombre de decimale par 2 a chaque iteration

    si tu a besoin de calculer 1 /N
    tu prend la suite xn = 2*xn-1 - xn-1*xn-1* N qui multiplie le nombre de decimale par 2 a chaque iteration

  13. #10
    Jack

    Re : Racine carrée

    salut,

    si ton FPGA ne permet même pas d'implémenter une multiplication, je pense que tu n'y arrivera pas.

    A+

  14. #11
    edje

    Re : Racine carrée

    Bien sur que le FPGA permet d'implementer des multiplications! Mais il faut éviter de le faire car cela prend trop de ressource en cellules logiques (la longueur du bus est doublé).

  15. #12
    shokin

    Re : Racine carrée

    et sinon, il paraît qu'il y a une méthode pour calculer la racine carrée d'un nombre, et cela sans machine, du moins de manière approximative si c'est pas le carré d'un entier.

    Mais je ne la connais pas, mais si vous la connaissez, n'hésitez pas à m'en faire part.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  16. Publicité
  17. #13
    alaink

    Re : Racine carrée

    J'ai deja fait qqchose de similaire il y a tres longtemps, en micro-code.
    Il faut passer en binaire et calculer la racine carre d'un nombre entier.
    Ton nombre se represente sous la forme n = (a+b) ou a est le nombre entier correspondant au bit le plus fort.
    On a n=a(1+b/n) avec b/n = c <1.

    Tu obtient la racine carree de a par decalages.

    Ensuite tu utilise un developpement limité
    de (1+c)^1/2, en arretant la somme au terme dont la valeur est inferieure a la precision requise.

    Ensuite tu multiplie ton DL par a^1/2.

    Tu peux accélerer le processus avec une table de quelques valeurs précalculées permettant d'accelerer la convergence du DL (plus "c" est petit, moins il faut d'iterations pour atteindre la precision requise).

    De facon generale, il faut se ramener à N = a(1+c)
    ou le calcul de a^1/2 est "facile" (table ou decalage) et c le plus petit possible.

    Enfin il faut prevoir de gerer les cas particuliers (nombres negatifs, infinis, NAN etc.) et le traitement des exposants si on utilise des nombres flottants à la norme IEEE.

    Pour l'anecdote j'avais dû aussi coder Ln, exp cos et sin, ch et sh en nombres réels et complexes.
    Dernière modification par alaink ; 17/08/2004 à 15h29.

  18. #14
    edje

    Re : Racine carrée

    C'est vrai que c'est une possibilité. mais les developpement limité ne sont pas facile à implementer et prennent trop d'elements de multiplications. C'est le probleme avec un FPGA, c'est que l'on travaille quasiment en hardware ca change la logique. La solution serait de ne travailler qu'avec des elements logiques et des decalages mais je ne la connais pas encore.

  19. #15
    alaink

    Re : Racine carrée

    La convergence est obtenue avec une dizaine de termes.
    Pour rappel il faut utiliser judicieusement les parentheses:
    ex.: x^(10) = (x*(x*x))*(x*x)

    Soit 3 multiplications, le resultat (x*x) etant stocké et reutilisé.

    Dependant de si on dispose de quelques octets de memoire les coefficients peuvent-etre précalculés.

    On s'en tire avec une 15aine de multiplications.

    On peut diminuer d'un facteur p le nombre de termes a calculer, et donc le nombre de multiplications, en utilisant une table precalculee de 2^p elements de facon a ce que c < 1/(2^p).

    Avec 2 tables on peut arriver a exprimer
    la racine sous forme de r= racine(k)*(table(i)+(x-xi)*alpha(i))


    ou
    - k est une puissance de 4
    - xi est la plus proche valeur de x= N/k dont la racine est stockee dans table
    - table(i) = xi^1/2
    - alpha(i) est une constante valant (table(i+1)-table(i))/p).
    - p est un pas constant valant x(i+1)-xi

    Soit un certain nb de decalages de bits (racine(k))
    3 multiplications (il y en a une implicite dans table(i)),
    2 additions.



    L'essentiel est de s'assurer que la precision obtenue est inferieure a la precision max representable (2^-24 sur un flottant 32 bits)
    Pour cela on calcule le max de racine(N)-r en fonction de p.

    Si l'erreur est trop importante, on ajoute un terme au DL, ce qui diminue la taille des tables necessaires, mais augmente le nb d'operations.

    Il faut faire un compromis entre le nb de cycles de calcul et la taille memoire necessitée par la table.

    De toute facon, le travail d'ingenieur est un travail de compromis n'est-ce pas?

Sur le même thème :

Discussions similaires

  1. Intégration de racine carrée de 1-cost
    Par Potache dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 14/05/2007, 20h31
  2. Calcul de la racine carrée
    Par EaGle58 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 12/04/2007, 13h55
  3. Dérivée de l'inverse de la racine carrée
    Par tipoulette dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 10/11/2006, 21h01
  4. Racine carrée et tangente
    Par chupinette4 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 17/09/2006, 15h53
  5. Racine carrée d'un nombre
    Par fragman dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 13/02/2005, 17h02