Racine carrée

[edje]

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?

[edje]

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

[doryphore]

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.

[edje]

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?

[TToufik]

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

[TToufik]

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.

[TToufik]

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

[doryphore]

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.

[cricri]

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

[Jack]

salut,

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

A+

[edje]

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é).

[shokin]

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

[alaink]

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.

[edje]

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.

[alaink]

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?