Le moyen le plus rapide pour obtenir la partie entière de sqrt(n)?
Comme nous le savons si n
n'est pas un carré parfait, alors sqrt(n)
ne serait pas un nombre entier. Car j'ai besoin d'uniquement la partie entière, j'ai l'impression que l'appel de sqrt(n)
ne serait pas rapide, il faut du temps pour calculer la fraction de la partie également.
Donc ma question est,
Pouvons-nous obtenir uniquement la partie entière de sqrt(n) sans calculer la valeur réelle de sqrt(n)
? L'algorithme devrait être plus rapide que sqrt(n)
(défini dans <math.h>
ou <cmath>
)?
Si possible, vous pouvez écrire le code dans asm
bloc également.
- La plupart des Processeurs effectuer sqrt dans le matériel, il est donc peu probable que vous serez en mesure d'aller plus vite en calculant uniquement la partie entière.
- Voici un lien intéressant pour un plus déterministe de l'algorithme: embedded-systems.com/98/9802fe2.htm
sqrt()
dans la bibliothèque C est rare d'être directement mis en œuvre en tant que matérielsqrt
instruction sur toutes les machines, depuis le matériel pourrait ne pas traiter tous les cas particuliers requis par la norme IEEE 754. Si vous n'aimez pas, vous pouvez utiliser inline asm ou du ccg-ffast-math
pour accéder directement au matériel.- Peut-être que c' link peut vous aider.
- assemblyrequired.crashworks.org/2009/10 montre quelques façons différentes de calculer la racine carrée de la PF en mathématiques;
sqrt(x)
(qui est justeFSQRT
) est le plus lent à 24ns, avec SIMD versions étant le plus rapide, en moyenne moins de 1ns pour un rapprochement. - Quelle est la portée de n êtes-vous intéressé?
- Toute la gamme, tant qu'un type peut la représenter.
- avez-vous le profil de votre application? Êtes-vous sûr que vous avez besoin pour améliorer la sqrt(n) vitesse?
Vous devez vous connecter pour publier un commentaire.
Je voudrais essayer le Rapide Inverse De La Racine Carrée truc.
C'est un moyen d'obtenir une très bonne approximation de la
1/sqrt(n)
sans branche, sur la base des bits de se tourner afin de ne pas portable (notamment entre les 32-bits et 64-bits pour les plates-formes).Une fois que vous l'obtenez, vous avez juste besoin d'inverser le résultat, et prend la partie entière.
Il pourrait être plus rapide des astuces, des cours, puisque celui-ci est un peu ronde.
MODIFIER: let's do it!
D'abord une petite aide:
Puis le corps principal:
Et les résultats:
Où comme prévu, le Rapide calcul effectue beaucoup mieux que le Int calcul.
Oh, et par la manière,
sqrt
est plus rapide 🙂-ffast-math
donnerait poursqrt
.sqrt
serait encore plus rapide. En fait,sqrt
est incroyablement plus vite!!86
, donc je n'ai pas trouversqrt
que rapide, j'aurais espéré une accélération matérielle version d'effectuer beaucoup mieux :/Edit: cette réponse est stupide utilisation
(int) sqrt(i)
Après profilage avec bon paramètres (
-march=native -m64 -O3
) ci-dessus a été un beaucoup plus rapide.Bien, un peu vieille question, mais le "le plus rapide" réponse n'a pas encore été donné. La manière la plus rapide (je pense) est le Binaire de la Racine Carrée de l'algorithme, expliqué en détail dans cette Embedded.com l'article.
Bref il revient à ceci:
Sur ma machine (Q6600, Ubuntu 10.10) je profilé en prenant la racine carrée des nombres 1-100000000. À l'aide de
iqsrt(i)
a pris 2750 mme. À l'aide de(unsigned short) sqrt((float) i)
a pris 3600ms. Cela a été fait à l'aide deg++ -O3
. À l'aide de la-ffast-math
option de compilation les temps étaient 2100ms et 3100ms respectivement. Remarque c'est sans même en utilisant une seule ligne d'assembleur, de sorte qu'il peut être encore plus rapide.Le code ci-dessus fonctionne en C et en C++ et avec de légères modifications de syntaxe aussi pour Java.
Ce qui fonctionne encore mieux pour une gamme limitée est une binaire de recherche. Sur ma machine ce coups la version ci-dessus de l'eau par un facteur 4. C'est malheureusement très limitée dans la gamme:
Une version 32 bits peut être téléchargé ici: https://gist.github.com/3481770
cmov
pour votre version?for (s=squares, i=128; i; i=i>>1) s += s[i]-x-1>>31 & i; return s-squares;
cmov
. Aussi, la main de dérouler la boucle est en fait plus rapide d'environ 20%. Voici l'asm de sortie pour les deux versions (à noter que j'ai pris la version 32 bits): gist.github.com/3481749 La pleine version 32 bits peut être téléchargé ici: gist.github.com/3481770;-)
Bien que je soupçonne que vous pouvez trouver un beaucoup de les options de la recherche pour "fast entier racine carrée", voici quelques potentiellement de nouvelles idées qui pourraient bien fonctionner (chaque indépendant, ou peut-être vous pouvez combiner entre eux):
static const
tableau de tous les carrés parfaits dans le nom de domaine que vous souhaitez soutenir, et d'effectuer une rapide sans branches binaire de recherche sur elle. L'indice dans le tableau est la racine carrée.static const
. Il n'y a pas de coût à l'informatique parce que c'est arrivé avant que votre programme a été compilé. Et même si vous prenez en charge la gamme complète des nombres entiers de 32 bits, votre table ne seront 256 ko.sqrt
; binaire de recherche sur une liste de 999999 entiers seraient les plus susceptibles d'être lent que sqrt!square[i]
qui, commei*i
est un entier de l'opération. Donc, même si l'accès àsquare[i]
serait libre, il ne serait pas encore plus rapide.left
index de la recherche binaire d'un entier d'expression qui prend la valeur 0 oulen/2
basée sur la différence de la valeur de l'essai et la valeur recherchée, par exemple en faisant un masque de la haute bit. Il peut aussi être fait en utilisantcmov
-type d'instructions.(int) sqrt
sur gcc -O3. Vous pouvez la regarder ici: gist.github.com/3481295 . Peut-être que vous pouvez améliorer mon application?<
les opérateurs de compiler à une branche conditionnelle (ou au moins conditionnelle déplacer), car le compilateur ne peut pas supposer quoi que ce soit à propos de la gamme de valeurs. Vous pouvez, si vous le pouvez (par exemple) l'utilisationunsigned
expressions et il suffit d'utiliser bit 31 de la différence pour obtenir un 0/1 résultat basé sur ce qui est plus grand.for (s=squares, i=128; i; i=i>>1) s+=-((unsigned)(s[i]-x-1)>>31) & i; return s-squares;
Notez que vous pouvez réparer votre table pour supprimer les indésirables-1
à partir du code. Il n'y a pas besoin de dérouler la boucle à la main;gcc -O3
va le faire pour vous.Je pense que
recherche Google
fournit de bons articles commeCalculer la racine carrée d'un nombre entier
qui a discuté à propos de trop nombreuses manières possibles de calcul rapide et il y a de bons articles de référence, je pense qu'ici, personne ne peut fournir de meilleurs qu'eux (et si quelqu'un peut première sera de produire du papier à ce sujet), mais si vous les lisez et il y a ambiguïté avec eux, alors peut-être nous pouvons vous aider à bien.Si vous n'avez pas l'esprit un rapprochement, comment à ce sujet entier fonction sqrt j'ai bricolé.
Il utilise l'algorithme décrit dans ce Wikipédia article.
Sur ma machine c'est presque deux fois plus rapide que sqrt 🙂
union { float f; int32_t x } v; v.f = (float) x; v.x -= ... return (int)((float)v.x);
.Faire entier sqrt vous pouvez utiliser cette spécialisation de la méthode de newton:
Fondamentalement, pour tout x la racine carrée se situe dans la gamme, ... x N/x), donc nous avons juste traversent cet intervalle à chaque boucle pour la nouvelle deviner. Une sorte de recherche binaire, mais il converge plus rapidement.
Ce converge en O(loglog(N)) ce qui est très rapide. Il également ne pas utiliser de virgule flottante à tous, et il fonctionne également bien pour les entiers en précision arbitraire.
Pourquoi personne ne suggère la méthode la plus rapide?
Si:
puis créer
int[MAX_X]
rempli (au lancement) avecsqrt(x)
(vous n'avez pas besoin d'utiliser la fonctionsqrt()
pour elle).Toutes ces conditions s'adapter à mon programme assez bien.
En particulier, un
int[10000000]
tableau va consommer40MB
.Quelles sont vos pensées sur cette?
C'est tellement court que 99% inlines:
Pourquoi nettoyer
xmm0
? La Documentation decvtsi2ss
GCC Intrinsèque version (fonctionne uniquement sur GCC):
Intel Intrinsèque version (testé sur GCC, Clang, CPI):
^^^^ Ils ont besoin de l'ESS 1 (même pas de l'ESS 2).
__builtin_ia32_cvtsi2ss
,__builtin_ia32_sqrtss
__builtin_ia32_cvtss2si
) à partir de ici? Quand en vient à l'aide de asm inline, less is more.t
à sa dernière ligne:return _mm_cvtt_ss2si(xmm0);
. Ce sont 5-6x plus rapide quesqrt()
sur ma machine), mais de mauvaises réponses commencent à apparaître lorsquenum
>= 16,785,407 cause des erreurs d'arrondi sur le flotteur. Pour résoudre ce problème dans la CCG Intrinsèque, modifiez la première ligne de__v2df xmm0 = {0, 0};
et de remplacer chaquess
avecsd
(avertissement: réduction de la vitesse de moitié). Je ne vois pas_mm_cvt_si2sd()
d'Intel Intrinsèques Guide pour une raison quelconque.Dans de nombreux cas, même exacte entier à la racine carrée de la valeur n'est pas nécessaire, suffit d'avoir une bonne approximation. (Par exemple, il arrive souvent dans la DSP de l'optimisation, lors de la 32 bits de signal doit être comprimé à 16-bits ou 16-bits à 8 bits, sans perdre beaucoup de précision autour de zéro).
J'ai trouvé ce utile équation:
Cette équation génère une courbe lisse (n, sqrt(n)), ses valeurs ne sont pas très différents des vrais sqrt(n) et peut donc être utile lorsque la précision est assez.
Si vous avez besoin de performances sur le calcul de la racine carrée, je suppose que vous permettra de calculer beaucoup d'entre eux.
Alors pourquoi ne pas mettre en cache la réponse? Je ne connais pas la gamme de N dans votre cas, ni si vous permettra de calculer plusieurs fois la racine carrée de la même entier, mais si oui, alors vous pouvez mettre en cache le résultat à chaque fois que votre méthode est appelée (dans un tableau serait la plus efficace si pas trop gros).
Sur mon ordinateur avec gcc, avec -ffast-math, la conversion d'un entier de 32 bits à flotter et à l'aide de sqrtf prend 1,2 s par 10^9 ops (sans -ffast-math il faut 3.54 s).
L'algorithme suivant utilise 0.87 s par 10^9 au détriment de la précision: les erreurs peuvent être autant que -7 ou +1 si l'erreur RMS est à seulement 0.79:
Le tableau est construit à l'aide d':
J'ai trouvé que le raffinage de la bissection en utilisant encore si les états à améliorer la précision, mais il ralentit aussi les choses au point que sqrtf est plus rapide, au moins avec -ffast-math.