Discussion :

[Nanoc]

Bonsoir,

J'ai un programme qui doit calculer entre autre la racine carrée inverse d'un nombre en simple ou double précision. Soit:

Code :

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

1. / sqrt(x);

et ceci des millions de fois. Des mesures avec callgrind montrent que le programme passe en effet près de 25% de son temps dans cette opération.

La question que je me pose est de savoir si il existe une fonction permettant d'obtenir directement 1/sqrt(x) sans passer par sqrt(x) et une division ?
Ou alors est-ce que le compilateur est capable d'optimiser cela en utilisant des instructions processeurs ?

Auriez-vous des informations à ce sujet ?

Merci d'avance !

P.S.: Je ne cherche PAS des trucs approchés comme on trouve dans les jeux vidéo. J'ai besoin d'une solution aussi exacte que 1./sqrt(x).

[Davidbrcz]

Ce PDF devrait de brancher. Attention, ce ne sont pas des maths de bas niveau.

P.S.: Je ne cherche PAS des trucs approchés comme on trouve dans les jeux vidéo. J'ai besoin d'une solution aussi exacte que 1./sqrt(x).

Va faire des maths alors . En informatique, tu auras forcément une valeur approchée. Peut être à 10^(-10), 10^(-100) mais elle reste approchée.

[deadalnix]

La solution n'est précise qu'a 10^-3 près environs. Ce n'est donc pas ce que cherche notre homme.

A priori, il est existe des instructions processeur pour faire cela. Pourquoi ne regardes-tu pas le code généré par le compilo afin de savoir si tu ne peux pas résoudre ton problème par des réglages compilo ? (pour g++ -O3 et -ffast-math)

[Davidbrcz]

La solution n'est précise qu'a 10^-3 près environs. Ce n'est donc pas ce que cherche notre homme.

A priori, il est existe des instructions processeur pour faire cela. Pourquoi ne regardes-tu pas le code généré par le compilo afin de savoir si tu ne peux pas résoudre ton problème par des réglages compilo ? (pour g++ -O3 et -ffast-math)

La méthode proposée se base sur l'extraction de racines par la méthode de Newton, qui est un algorithme à convergence quadratique, donc si la précision n'est pas suffisante, il suffit de recommencer

[Mac LAK]

Question bête : sachant que 1/sqrt(x) est égal à (x^(-1/2)), as-tu essayé un appel à pow avec -0.5 en guise d'exposant, pour voir ce que ça donne en terme de performances ?

Sinon, faudrait peut-être regarder du côté des instructions SSE. Mais de mémoire, il n'y a pas d'opération native du FPU qui effectue directement 1/sqrt(x).

[screetch]

_mm_rsqrt_ps en SSE
http://msdn.microsoft.com/en-us/libr...8VS.71%29.aspx
sous GCC tu pourrais peut etre augmenter les perfs avec les options
'-mfpmath=sse', '-msse2'

[mohira]

Bonjour,
Vous pourriez peut-être essayer de programmer ceci pour un calcul de 1/sqrt(x): si on considère que y est une valeur approchée,on pose (y+a)^2=1./x et on approxime par y^2+2*a*y=1./x d'où a = (1./(x*y)-y)/2.,on fait y=y+a,et on itère avec un test de convergence.
A la question de l'initialisation de y,je pense que,si on sait identifier l'exposant et la mantisse de x,on pourrait prendre la même mantisse pour y(initial) et pour exposant l'exposant de x divisé par -2.

[deadalnix]

La méthode proposée se base sur l'extraction de racines par la méthode de Newton, qui est un algorithme à convergence quadratique, donc si la précision n'est pas suffisante, il suffit de recommencer

Ça sera de toute façon moins rapide et moins précis que l'instruction cablée.

[mohira]

Il est certain que,si l'instruction est câblée,la discussion sur une méthode logicielle n'a plus lieu.Bien sûr,quand je pensais à une méthode logicielle,c'est parce que je pensais qu'on supposait a priori que ce n'était pas le cas.C'était l'intérêt de la question initiale.Si la fonction sqrt() est câblée,la discussion est close d'elle-même.