C++ 中正弦、余弦和平方根的最快实现(不需要太准确) [英] Fastest implementation of sine, cosine and square root in C++ (doesn't need to be much accurate)

问题描述

我在谷歌上搜索了过去一个小时的问题，但只有泰勒级数或一些示例代码太慢或根本无法编译.好吧，我在谷歌上找到的大多数答案是谷歌它，已经有人问过了"，但遗憾的是不是...

我正在低端 Pentium 4 上分析我的游戏，发现大约 85% 的执行时间浪费在计算正弦、余弦和平方根(来自 Visual Studio 中的标准 C++ 库)上，这似乎很严重CPU 依赖(在我的 I7 上，相同的函数只有 5% 的执行时间，而且游戏速度waaaaaaaaaay).我无法优化这三个函数，也无法一次性计算正弦和余弦(相互依赖)，但我的模拟不需要太准确的结果，因此我可以接受更快的近似值.

那么，问题是:在 C++ 中计算浮点数的正弦、余弦和平方根的最快方法是什么?

编辑查找表更加痛苦，因为在现代 CPU 上产生的缓存未命中比泰勒级数要昂贵得多.这些天 CPU 的速度太快了，而缓存却不是.

我犯了一个错误，我认为我需要为泰勒级数计算几个阶乘，现在我看到它们可以作为常量实现.

所以更新的问题是:是否也有平方根的快速优化?

EDIT2

我使用平方根来计算距离，而不是归一化 - 不能使用快速逆平方根算法(如评论中指出的:

有关泰勒级数的更多信息... http://en.wikipedia.org/wiki/泰勒级数

使其正常工作的关键之一是预先计算阶乘并截断合理数量的项.分母中的阶乘增长非常快，因此您不需要携带多个项.

另外...不要每次都从一开始就乘以 x^n...例如将 x^3 再乘以 x 两次，然后再乘以两次以计算指数.

I am googling the question for past hour, but there are only points to Taylor Series or some sample code that is either too slow or does not compile at all. Well, most answer I've found over Google is "Google it, it's already asked", but sadly it's not...

I am profiling my game on low-end Pentium 4 and found out that ~85% of execution time is wasted on calculating sinus, cosinus and square root (from standard C++ library in Visual Studio), and this seems to be heavily CPU dependent (on my I7 the same functions got only 5% of execution time, and the game is waaaaaaaaaay faster). I cannot optimize this three functions out, nor calculate both sine and cosine in one pass (there interdependent), but I don't need too accurate results for my simulation, so I can live with faster approximation.

So, the question: What are the fastest way to calculate sine, cosine and square root for float in C++?

EDIT Lookup table are more painful as resulting Cache Miss is way more costly on modern CPU than Taylor Series. The CPUs are just so fast these days, and cache is not.

I made a mistake, I though that I need to calculate several factorials for Taylor Series, and I see now they can be implemented as constants.

So the updated question: is there any speedy optimization for square root as well?

EDIT2

I am using square root to calculate distance, not normalization - can't use fast inverse square root algorithm (as pointed in comment: http://en.wikipedia.org/wiki/Fast_inverse_square_root

EDIT3

I also cannot operate on squared distances, I need exact distance for calculations

解决方案

The fastest way is to pre-compute values an use a table like in this example:

Create sine lookup table in C++

BUT if you insist upon computing at runtime you can use the Taylor series expansion of sine or cosine...

For more on the Taylor series... http://en.wikipedia.org/wiki/Taylor_series

One of the keys to getting this to work well is pre-computing the factorials and truncating at a sensible number of terms. The factorials grow in the denominator very quickly, so you don't need to carry more than a few terms.

Also...Don't multiply your x^n from the start each time...e.g. multiply x^3 by x another two times, then that by another two to compute the exponents.

这篇关于C++ 中正弦、余弦和平方根的最快实现(不需要太准确)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！