我正在开发一种游戏,它可以为物理和渲染调用许多数学函数.已知Quake3中使用的"Fast inverse sqrt"比sqrt()快,并且它的背景很漂亮.
您是否知道任何其他比平时更快的算法,并且具有可接受的准确度损失？
Ste*_*non 13
任何连续函数(包括最常见的数学运算)都可以通过多项式在有界区间内很好地近似.这与常见数学函数通常满足的相对简单的标识(如加法则)和表查找一起,提供了构建快速逼近算法的标准技术的基础(以及系统数学中使用的高精度方法的基础).图书馆).
泰勒系列通常是一个糟糕的选择; 对于大多数计算用途,Chebyshev或Minimax多项式具有更好的误差特性.拟合minimax多项式的标准技术是使用Remes的算法,该算法在许多商业数学软件中实现,或者如果你知道你正在做什么,你可以用一天的工作来完成你自己的实现.
为了记录,在现代处理器上应避免使用"快速反平方根",因为使用浮点倒数平方根估计指令(rsqrtss/ rsqrtps在SSE上,vrsqrte在NEON上,vrsqrtefp在AltiVec上)要快得多.在当前的英特尔处理器上,即使(非近似)硬件平方根也非常快.
这些算法在文献中称为"近似算法".有大量例子的标准书是Vijay V. Vazirani的近似算法.
sin x ~~ x的情况是稍微更一般的特殊情况:查看函数的泰勒级数(或周期函数的傅里叶级数)并仅计算前几个项.
另一种(有点残酷的)技术是随机组合你的函数的几个点,然后对它进行线性回归.这样,你也可以得到一个很好的多项式来描述你的函数:).
| 归档时间： |
|
| 查看次数： |
1548 次 |
| 最近记录： |