这是 C++ 中保证最快的正弦函数:
double FastSin(double x)
{
return 0;
}
哦,您想要比 |1.0| 更高的精度吗?好吧,这是一个同样快的正弦函数:
double FastSin(double x)
{
return x;
}
这个答案,当 x 接近于零时。对于较小的 x,sin(x) 约等于 x https://en.wikipedia.org/wiki/Small-angle_approximation,因为 x 是 sin(x) 泰勒展开式的第一项。
什么,对你来说还不够准确?继续阅读吧。
20 世纪 70 年代的工程师在这一领域取得了一些奇妙的发现,但新程序员根本不知道这些方法的存在,因为它们没有作为标准计算机科学课程的一部分进行教授。
你需要首先了解这一点没有“完美”的实施这些功能适用于所有应用程序。因此,对“哪一个最快”之类的问题的肤浅回答肯定是错误的。
问这个问题的人大多不明白这个问题的重要性性能和准确性之间的权衡。特别是,在执行其他操作之前,您必须对计算的准确性做出一些选择。您可以容忍结果中有多少误差? 10^-4? 10^-16?
除非您可以用任何方法量化错误,否则不要使用它。请参阅我下面的所有随机答案,这些答案发布了一堆随机的未注释的源代码,没有清楚地记录所使用的算法及其exact输入范围内的最大误差? “我猜这个错误大约是一种咕哝声。”这完全是丛林联盟。如果您不知道如何计算PRECISE最大误差,至FULL精度,在你的近似函数中,跨越ENTIRE输入的范围...那么您不知道如何编写近似函数!
没有人单独使用泰勒级数来近似软件中的超越数。除了某些高度具体的案例 https://math.stackexchange.com/questions/1344627/how-to-use-chebyshev-polynomials-to-approximate-sinx-and-cosx-within-t,泰勒级数一般缓慢接近目标跨越常见的输入范围。 https://math.stackexchange.com/questions/1344627/how-to-use-chebyshev-polynomials-to-approximate-sinx-and-cosx-within-the-int
您的祖父母用来有效计算超越数的算法统称为CORDIC https://en.wikipedia.org/wiki/CORDIC并且足够简单,可以在硬件中实现。这里有一个C 中记录良好的 CORDIC 实现 https://people.sc.fsu.edu/%7Ejburkardt/cpp_src/cordic/cordic.html。 CORDIC 实现通常需要一个非常小的查找表,但大多数实现甚至不需要可用的硬件乘法器。大多数 CORDIC 实现都可以让您在性能和准确性之间进行权衡,包括我链接的那个。
多年来,原始 CORDIC 算法已经有了很多渐进式改进。例如,去年日本的一些研究人员发表了一篇article http://www.jiii.org/uploadfile/2015/0911/20150911044421219.pdf改进的 CORDIC 具有更好的旋转角度,从而减少了所需的操作。
如果你有硬件乘法器(你几乎肯定有),或者如果你买不起像 CORDIC 需要的查找表,你总是可以使用切比雪夫多项式 https://www.embeddedrelated.com/showarticle/152.php做同样的事情。切比雪夫多项式需要乘法,但这在现代硬件上很少成为问题。我们喜欢切比雪夫多项式,因为对于给定的近似值,它们具有高度可预测的最大误差 https://math.stackexchange.com/questions/1344627/how-to-use-chebyshev-polynomials-to-approximate-sinx-and-cosx-within-t。在输入范围内,切比雪夫多项式最后一项的最大值限制了结果中的误差。并且随着项数变多,这个误差会变小。这是一个例子 https://web.archive.org/web/20200628195036/http://mooooo.ooo/chebyshev-sine-approximation/切比雪夫多项式在大范围内给出正弦近似,忽略正弦函数的自然对称性,只是通过向其投入更多系数来解决近似问题。这是将正弦函数估计到 5 个 ULP 以内的示例 https://web.archive.org/web/20200628195036/http://mooooo.ooo/chebyshev-sine-approximation/。不知道什么是ULP?你应该。 https://en.wikipedia.org/wiki/Unit_in_the_last_place
我们也喜欢切比雪夫多项式,因为近似误差在输出范围内均匀分布。如果您正在编写音频插件或进行数字信号处理,切比雪夫多项式可以“免费”为您提供廉价且可预测的抖动效果。
如果您想在特定范围内找到自己的切比雪夫多项式系数,许多数学库将查找这些系数的过程称为“切比雪夫拟合 https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.polynomial.chebyshev.Chebyshev.fit.html“ 或类似的东西。
平方根,无论当时还是现在,通常都是用以下公式的一些变体来计算:牛顿-拉夫森算法 https://www.youtube.com/watch?v=2158QbsunA8,通常具有固定的迭代次数。通常,当有人制作出一个“惊人的新” https://stackoverflow.com/questions/1349542/john-carmacks-unusual-fast-inverse-square-root-quake-iii求平方根的算法,它只是伪装的牛顿拉夫森算法。
Newton-Raphson、CORDIC 和 Chebyshev 多项式可让您以速度换取准确性,因此答案可以像您想要的那样不精确。
最后,当您完成所有精美的基准测试和微优化后,请确保您的“快速”版本实际上比库版本更快。这是 fsin() 的典型库实现 http://www.netlib.org/fdlibm/k_sin.c限制在从 -pi/4 到 pi/4 的域上。而且速度并没有那么慢。
最后要提醒您的是:您几乎肯定会使用 IEEE-754 数学来执行估计,并且每当您使用一堆乘法执行 IEEE-754 数学时,几十年前做出的一些晦涩的工程决策就会再次出现。你,以舍入误差的形式。这些错误一开始很小,但它们会变得越来越大,越来越大!在你生命中的某个时刻,请阅读“每个计算机科学家都应该了解浮点数” https://www.itu.dk/%7Esestoft/bachelor/IEEE754_article.pdf并有适当程度的恐惧。请记住,如果您开始编写自己的超越函数,则需要对浮点舍入造成的实际误差进行基准测试和测量,而不仅仅是最大理论误差。这不是一个理论上的问题;而是一个问题。在不止一个项目中,“快速数学”编译设置让我很恼火。
TL:博士;去谷歌“正弦近似”或“余弦近似”或“平方根近似”或“近似理论 https://en.wikipedia.org/wiki/Approximation_theory."