更快的数学算法牺牲准确性

我正在开发一个游戏，为物理和渲染调用如此多的数学函数。已知Quake3中使用的"Fast inverse sqrt"比sqrt（）更快，并且其背景非常漂亮。更快的数学算法牺牲准确性

你知道有什么其他算法比平时更快吗？可接受的精度损失？

2009-12-10 grayger

也许你也可以在http://mathoverflow.net上得到答案 – Lucero 2009-12-10 16:13:54

如何使它成为一个维基？ – ATorras 2009-12-10 16:42:11

我不确定在Quake中使用的快速反向根目前是否比RSQRTPS更快，并且它并行执行了四个。现在，将数据从FPU移动到RAM以注册，操作，存储和重新加载到FPU中的成本可能不仅仅是在执行FSQRT。 – Skizz 2009-12-10 16:53:51

这些算法在文献中被称为“近似算法”。标准书中有大量的例子是Approximation Algorithms by Vijay V. Vazirani。

sin x ~~ x的情况是稍微更一般的特例：查看函数的Taylor series（或者在周期函数情况下是傅里叶级数），并且只计算前几项。

另一个（有点残酷的）技术是随机组装几个函数的点，然后对它进行线性回归。这样，你可以得到一个很好的多项式来描述你的功能:)。

来源

2009-12-10 16:10:00 nes1983

线性回归会导致“直线拟合” - 可能不是您想要的。但是你可以用最小平方意义拟合二次或三次多项式，这可能会导致可接受的精度。 – Paul 2009-12-10 16:59:43

您可以通过线性回归找到多项式的系数。 – nes1983 2009-12-10 22:16:40

谢谢，这本书是我正在寻找的。 – grayger 2009-12-11 00:29:01

对于小x：的sin（x）〜= x是一个经常被使用的物理

来源

2009-12-10 16:10:10

请将'=='更改为'〜'。 – jason 2009-12-10 16:11:10

良好的呼叫 - 改变了 – 2009-12-10 16:15:59

任何概率通常是这样的。运行模拟10次会更快，但产生的结果比运行1000次的模拟结果要准确得多。

来源

2009-12-10 16:17:43

Niko有一些很好的建议，我会添加旧的时尚查找表。

我在高性能实时systesm中成功地多次使用查找表来获得循环函数（sin/cos/tan）。 sqrt（）这种方式比较困难，但是如果你的输入范围受到限制（说屏幕像素），速度很难被击败，你可以精确地调整空间/精确度。你也可以使用查找一个常见的范围，然后在少数情况下有一个sqrt（）函数的结果。

保罗

来源

2009-12-10 16:57:36 Paul

任何连续函数（其包括最常见的数学运算）可以很好地近似在由一个多项式有界区间。这与常见数学函数通常满足的相对简单的身份（如加法律）和表查找一起提供了构建快速近似算法的标准技术的基础（并且也是系统数学中使用的高精度方法的基础）图书馆）。

泰勒系列通常是一个糟糕的选择，但是; Chebyshev或Minimax多项式对于大多数计算用途具有好得多的误差特性。拟合最小多项式的标准方法是使用Remes算法，该算法在许多商业数学软件中实现，或者如果你知道自己在做什么，可以在一天的工作中推出自己的实现。

对于记录，“快速逆平方根”应避免对现代处理器的，因为它是基本上更快地使用浮点倒数平方根估计指令（rsqrtss/rsqrtps上SSE，vrsqrte上NEON，vrsqrtefp在AltiVec上）。即使（非近似）硬件平方根在当前的英特尔处理器上也相当快。

来源

2009-12-10 17:27:33

从末日的源代码，用于两个2D点之间近似距离，而不必使用SQRT（）或三角函数：

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy) 
{ 
    dx = abs(dx); 
    dy = abs(dy); 
    if (dx < dy) 
     return dx+dy-(dx>>1); 
    else 
     return dx+dy-(dy>>1); 
}

注意x >> 1相同x/2但稍快 - 良好的现代编译器现在自动执行此操作，但当时他们并不那么棒。

来源

2009-12-10 17:32:29

好吧，这是永远的，但'fixed_t'是一个int类型定义。那么你近似的距离是什么？ – knight666 2009-12-17 22:48:42

更快的数学算法牺牲准确性

回答

相关问题