La mise en œuvre rapide des fonctions trigonométriques pour c++
Version courte: j'aimerais savoir s'il existe des implémentations de la norme fonctions trigonométriques qui sont plus rapides que celles incluses dans math.h.
Version longue: j'ai un programme assez lourd sur les objets numériques (c'est une simulation physique) et que les besoins à l'appel de fonctions trigonométriques, surtout sin et cos, beaucoup. Actuellement, je suis tout simplement en utilisant les implémentations inclus dans math.h. Profilage montre que les appels à ces fonctions de coût plus que je m'attendais (en espérant).
Alors qu'il est certainement plus beaucoup de place pour l'optimisation dans d'autres parties du code, plus rapides sin et cos pourrait me donner quelques autres pour cent. Donc, avez-vous des suggestions?
Dans un autre post l'utilisation de tables de consultation est suggéré. Mais peut-être qu'il existe des alternatives? Ou ready-made et testé de recherche de solutions, dans certaines bibliothèques?
- La plupart des fast-des êtres transcendantaux sont orientées vers les moteurs de jeu, qui ne se soucie pas que beaucoup au sujet de l'exactitude. Quelle est l'importance de la précision à votre problème?
- Profil en premier. "peut donner un certain pourcentage supplémentaire" n'est pas la peine d'essayer de l'optimiser.
- Comme indiqué dans ma question, je SUIS de profilage et de mon attente serait "un couple de pour cent" dans l'exécution, peut-être de 2% ou 3%, mais c'est une estimation très approximative certainement. Mais avec des durées maximales de l'ordre de jours, n'importe quel pourcentage je peux obtenir, peut-être bien la peine..
- Les tables de recherche type de 1985. Les Processeurs modernes sont beaucoup plus rapides à effectuer des calculs de lecture de la mémoire. À moins que votre table de recherche est très petite, et vous faites beaucoup de sin/cos dans un lot, donc vous avez la garantie que le LUT au niveau-1 cache c'est pas la peine. J'ai vu minimax polys dans l'ESS lancer efficacement dans 18-20 cycles (pipelining ftw). C'est environ deux fois plus que le meilleur des cas pour un LUT, et légèrement plus rapide que la moyenne des cas, surtout si vous faites autre chose que la forme synthétique de référence (mais, il n'enlève pas les lignes de cache à partir d'un autre code).
- Oui, ce serait finalement la question. Je serais éventuellement avoir à le tester, mon instinct me dit que la précision d'-à-dire 4 ou 5 chiffres serait suffisant dans la plupart des endroits..
- Cependant, comme les précédents intervenants ont déjà laissé entendre, vous devez d'abord déterminer si une douzaine de cycles est un problème. Sauf si vous avez plusieurs millions de trig appels de fonction, image par image, il ne devrait pas question sur un CPU qui n'est pas l'âge de 15 ans (et si vous faites cela, vous êtes susceptible de faire quelque chose de mal).
- Lorsque le goulot d'étranglement est fonctions trigonométriques, une chose à considérer est l'utilisation de formules trigonométriques pour réduire le nombre d'appels. Si par exemple vous êtes le calcul de sin(nx) et cos(nx) pour un tas de nombres entiers consécutifs n, il peut être intéressant de calculer cos x et sin x et utiliser les récidives (cos(a+b) = cos a cos b - sin a sin b et sin(a+b) = sin a cos b + cos a sin b)
- Voir stackoverflow.com/questions/523531/... C'est pour Java, mais les formules de travail en C++.
math.hne comprend pas tout de la mise en œuvre. La mise en œuvre dans la bibliothèque qui sera lié à votre code. Pour répondre à votre question, vous avez à dire ce PROCESSEUR cible et le compilateur que vous utilisez.- J'ai mis en œuvre rapide de la fonction sinus sur le cpu côté qui est au moins deux fois plus rapide de mathématiques.h ' s la fonction sinus cependant, j'ai utilisé une très petite table de recherche(20 chars). la précision est également pas mal du tout; moyenne relative des taux d'erreur est 0.095%. vous pouvez le vérifier à partir de http://www.hevi.info/tag/fast-sine-function/
- Avez-vous déjà vérifier si votre algorithme est parallélisable? Si vous pouvez l'obtenir pour fonctionner sur un (GPU via openCL par exemple), alors au lieu de 2%-3% vous pourriez être à la recherche à 90%-95% plus rapide (developer.nvidia.com/opencl)
Vous devez vous connecter pour publier un commentaire.
Voici quelques bonnes diapos sur la façon de faire de la puissance de la série d'approximations (PAS la série de Taylor si) de fonctions trigonométriques: http://www.research.scea.com/gdc2003/fast-math-functions.html
Il est orienté vers les programmeurs de jeux, ce qui correspond à la précision devient sacrifié pour la performance, mais vous devriez être en mesure d'ajouter un autre terme, ou les deux à la approximations pour obtenir certains de l'exactitude de retour.
La bonne chose à ce sujet est que vous devez aussi être capable de l'étendre à SIMD facilement, de sorte que vous pourrait calculer le sin ou cos de 4 valeurs (2 si vous utilisez la double précision).
Espère que ça aide...
Ce doit être sacrément rapide si vous pouvez l'optimiser davantage veuillez et postez le code comme pastie.org ou quelque chose.
Spécifications de l'ordinateur -> 512 mo de Ram , Visual Studio 2010 , microsoft Windows XP Professionnel Version 2002 SP3 , Intel (R) Pentium (R) 4 CPU 2.8 GHZ.
C'est incroyablement précis et sera effectivement fournir des résultats légèrement meilleurs dans certaines situations. E. g. 90, 180, 270 degrés en C++ renvoie non 0 chiffres après la virgule.
COMPLÈTE de la TABLE DE 0 à 359 Degrés: https://pastee.org/dhwbj
FORMAT -> DIPLÔME d' # -> MINE_X(#) , CosX(#) , MINE_Z(#) , SinZ(#).
Ci-dessous est le code utilisé pour construire le tableau ci-dessus. Vous pouvez probablement le faire encore plus précis si vous utilisez un plus grand type de données. J'ai utilisé un unsigned short et ne N/64000. Donc, Ce que jamais le cos(##) et sin(##) où le plus proche j'ai arrondi à l'indice. J'ai aussi essayé d'utiliser le moins de données que possible, de sorte à ne pas être certains encombré de table avec 720 float valeurs de cos et sin. Ce qui devrait donner de meilleurs résultats, mais d'une perte totale de la mémoire. Le tableau ci-dessous est aussi petit que je pouvais le faire. J'aimerais voir si il est possible de faire une équation qui pourrait ronde à l'ensemble de ces valeurs courtes et utiliser à la place. Je ne sais pas si il serait pas plus rapide, mais elle permettrait d'éliminer la table complètement et probablement pas réduire la vitesse par quelque chose ou beaucoup.
De sorte que la précision en comparaison à la C++ cos/sin opérations est 99.99998% à 100%.
Ci-dessous est la table utilisée pour calculer le cos/sin valeurs.
Ci-dessous est le code qui ne le cos/sin calculs.
Des VITESSES ci-DESSOUS à l'aide de l'origine de la mention " spécifications de l'ordinateur. J'ai été en cours d'exécution en mode debug avant c'est le mode de débogage, mais il est couru par le biais de l'exécutable qui, je crois, est de débogage sans débogage.
MA MÉTHODE
COS/SIN MÉTHODE
Donc, pour résumer le dessus de réaliser les deux cos(###) et sin(###) avec ma stratégie permet à peu près 220,000,000 exécutions par seconde. En utilisant l'ordinateur spécifications indiquées à l'origine. C'est assez rapide, et utilise très peu de mémoire c'est donc un excellent substitut pour les mathématiques cos/sin fonctions normalement trouvé dans C++. Si vous souhaitez voir la précision ouvrir le lien indiqué ci-dessus et il y a une impression de degrés 0 creux 359. Aussi cette charge de 0 à 89 et quadrants de 0 à 3. Donc, vous devez soit utiliser ou exécuter (DEGRÉS % 90).
sin(90)n'est pas de 0 dans C++ est facile: C++ utilise des radians, pas de degrés.Quake 3 de source a un peu de code pour précalculées sinus/cos visant à la vitesse à la précision, ce n'est pas de l'ess, que donc tout à fait portable(à la fois sur l'architecture et intrinsèque de l'api). Vous pouvez également trouver ce résumé du sse et sse2 fonctions très intéressantes: http://gruntthepeon.free.fr/ssemath/
Si vous souhaitez utiliser une implémentation personnalisée, regardez ici, ici et ici
Aussi ici (défilement Universel SIMD-Mathlibrary) si vous avez besoin de calculer sin/cos pour les grands tableaux
Vous pouvez également essayer d'utiliser le C++ intrinsèques SSE. Regarder ici
Remarque que plus les compilateurs modernes supportent SSE et SSE2 optimisations. Pour Visual Studio 2010, par exemple, vous devez l'activer manuellement. Une fois que vous faites cela, une mise en œuvre différente sera utilisé pour la plupart des fonctions mathématiques.
Une autre option est d'utiliser DirectX HLSL. Regarder ici. Notez qu'il y a une belle sincos fonctions qui retournent à la fois sin et cos.
Habituellement, j'utilise le protocole IPP (qui n'est pas gratuit). Pour plus de détails, regardez ici
A) en Essayant de sauver les petits pourcents ne sera pas très satisfaisant. Finition en 97 au lieu de 100 heures est encore un long moment.
B) vous dites que Vous profilé, et que les fonctions trigonométriques prendre plus de temps que vous le souhaitez.
Combien? et que dire de tout le reste du temps?
Il est fort possible que vous avez de plus gros poissons à frire.
La plupart des profileurs basé sur les concepts gprof ne pas vous parler de milieu de la pile des appels que vous pouviez vous concentrer afin d'économiser de grandes quantités de temps. Voici un exemple.
J'ai mis en œuvre rapide de la fonction sinus sur le cpu côté qui est au moins deux fois plus vite que les mathématiques.h ' s la fonction sinus cependant, j'ai utilisé une très petite table de recherche(20 chars). la précision est également pas mal du tout; moyenne relative des taux d'erreur est 0.095%. vous pouvez le vérifier à partir de http://www.hevi.info/tag/fast-sine-function/
Explication de la méthode est assez simple et repose sur le fait que pour les petits un de sin(a) = a * pi /180 (voir le lien ci-dessus pour la preuve)
Certains Trigonométrie
Bien qu'il est possible de réaliser relativement précise des résultats avec la formule ci-dessus pour les angles entre 0 et 10, l'angle devient plus large qu'elle en perd accuricy. Par conséquent, nous devons utiliser la formule pour les angles inférieurs à 10, mais comment?!
La réponse vient de la trigonométriques sinus plus de la formule;
sin(a+b) = sin(a) cos(b) + sin(b) cos(a)
Si nous pouvons garder le ‘b’ à moins de 10 alors nous serons en mesure d'utiliser notre formule afin de trouver le sinus avec un couple de aritchmetic opérations.
Disons que nous sommes demandé le sinus de la valeur pour 71.654, alors;
a = 70
b = 1.654
et,
sin(71.654) = sin(70 + 1.654) = sin(70) cos(1.654) + sin(1.654) cos (70)
Dans cette formule, nous sommes en mesure d'utiliser le calcul rapide pour le péché(1.654) et pour le reste, malheureusement, nous avons besoin d'avoir des sinus et cosinus des tables. La bonne chose est que nous avons seulement besoin de les multiplier des dizaines pour le sinus et le nombre naturel angles entre 0 et 10 pour le cosinus.
Longtemps sur les machines lentes, les gens utilisés un des tableaux avec des valeurs précalculées. une autre option pour calculer avec votre propre précision comme cette: (cherchez "Série de définitions")
Vous pouvez regarder cette. Il parle de l'optimisation de sin, cos.
Pendant 2 à 3% de gain, c'est presque certainement pas la peine le risque d'inexactitude, d'erreur, les hypothèses n'est plus vrai (par exemple, ne jamais tomber en dehors de
[-1,-1]), etc., sauf si vous envisagez sur l'exécution de ce sur un grand nombre de machines (où 2 à 3% représente des milliers ou des millions de dollars dans l'électricité et le coût après amortissement de la machine).Cela dit, si vous avez un domaine spécifique de connaissances sur ce que vous voulez accomplir, vous pouvez être en mesure d'accélérer vos calculs par un facteur de deux ou plus. Par exemple, si vous avez toujours besoin
sinetcosde la même valeur, calculer proches les uns des autres dans le code et assurez-vous que votre compilateur traduit en FSINCOS instruction de montage (voir cette question). Si vous avez besoin seulement d'une petite partie de la gamme complète de la fonction, vous pouvez éventuellement utiliser un ensemble de basse-ordre des polynômes suivie par une itération de la méthode de Newton pour obtenir la pleine machine de précision (ou autant que vous avez besoin). Encore une fois, c'est beaucoup plus puissant, si vous savez que vous avez seulement besoin de certaines valeurs (par exemple, si vous pouvez l'utiliser sin(x) est proche de x proche de zéro, et vous aurez seulement besoin de valeurs proches de zéro, alors vous pouvez réduire considérablement le nombre de termes dont vous avez besoin.Mais, encore une fois, mon conseil principal est de: 2 à 3% n'est pas la peine. Penser plus sur les algorithmes utilisés et d'autres goulots d'étranglement potentiels (par exemple, la fonction malloc de manger trop de temps?) avant d'optimiser cette.