三角函数计算的源代码

4
对于需要确定性并在不同平台(编译器)上提供相同结果的程序,不能使用内置三角函数,因为计算它的算法在不同系统上是不同的。测试结果值是不同的。
(编辑:结果需要与最后一位完全相同,因为它用于在所有客户端上运行的游戏模拟。这些客户端需要确切地具有模拟状态才能使其正常工作。任何小错误都可能导致随着时间的推移越来越大的错误,还使用了游戏状态的crc作为同步检查。)
所以我想到的唯一解决方案是使用我们自己的自定义代码来计算这些值,问题是(出乎意料地),很难找到易于使用的三角函数源代码集。
这是我修改了的代码(https://codereview.stackexchange.com/questions/5211/sine-function-in-c-c)用于sin函数。在所有平台上都是确定性的,并且该值几乎与标准sin的值相同(均已测试)。
#define M_1_2_PI 0.159154943091895335769 // 1 / (2 * pi)

double Math::sin(double x)
{
  // Normalize the x to be in [-pi, pi]
  x += M_PI;
  x *= M_1_2_PI;
  double notUsed;
  x = modf(modf(x, &notUsed) + 1, &notUsed);
  x *= M_PI * 2;
  x -= M_PI;

  // the algorithm works for [-pi/2, pi/2], so we change the values of x, to fit in the interval,
  // while having the same value of sin(x)
  if (x < -M_PI_2)
    x = -M_PI - x;
  else if (x > M_PI_2)
    x = M_PI - x;
  // useful to pre-calculate
  double x2 = x*x;
  double x4 = x2*x2;

  // Calculate the terms
  // As long as abs(x) < sqrt(6), which is 2.45, all terms will be positive.
  // Values outside this range should be reduced to [-pi/2, pi/2] anyway for accuracy.
  // Some care has to be given to the factorials.
  // They can be pre-calculated by the compiler,
  // but the value for the higher ones will exceed the storage capacity of int.
  // so force the compiler to use unsigned long longs (if available) or doubles.
  double t1 = x * (1.0 - x2 / (2*3));
  double x5 = x * x4;
  double t2 = x5 * (1.0 - x2 / (6*7)) / (1.0* 2*3*4*5);
  double x9 = x5 * x4;
  double t3 = x9 * (1.0 - x2 / (10*11)) / (1.0* 2*3*4*5*6*7*8*9);
  double x13 = x9 * x4;
  double t4 = x13 * (1.0 - x2 / (14*15)) / (1.0* 2*3*4*5*6*7*8*9*10*11*12*13);
  // add some more if your accuracy requires them.
  // But remember that x is smaller than 2, and the factorial grows very fast
  // so I doubt that 2^17 / 17! will add anything.
  // Even t4 might already be too small to matter when compared with t1.

  // Sum backwards
  double result = t4;
  result += t3;
  result += t2;
  result += t1;

  return result;
}

但我没有找到其他函数的合适选择,比如asin,atan,tan(除了sin/cos之外)等。
这些函数不需要像标准函数一样那么精确,但至少8位数字会很好。

1
不要忘记浮点数的计算是实现定义的,通常取决于架构和编译器选项!如果您只需要8位数字的精度,请使用标准库。我怀疑您这样做并不能节省时间。 - rubenvb
2
我知道标准库已经足够精确了,但是在四舍五入时,第20位的差异仍然可以改变第8位的值(例如0.99999999999999999与1.0)。正如我在帖子开头所述,为了实现确定性,计算必须精确到最后一位。这是网络游戏模拟,其中游戏状态被crc校验并检查在所有客户端上是否相同。 - kovarex
那么你必须(严格按照字面意思)使用某种整数固定点数学。除非你的编译器可以保证严格符合IEEE 754标准,否则无法使用浮点数来实现这一点。 - rubenvb
2
我们使用的编译器可以保证严格的IEEE 754,我们已经测试过了。除非我们使用自定义实现的三角函数,否则一切都是严格和精确的。不得不重写整个程序以使用基于整数的定点数学将会是非常艰巨的工作(我猜可能需要几个月的时间),而且会带来很多麻烦。 - kovarex
切换到自定义数字类应该只需要在整个代码库中进行一次重命名(或者如果您已经使用了typedef,则更改typedef)。这不是我所说的很多工作。然而,性能会受到影响。无论如何,我建议使用现有的实现(请参见我的答案)。 - rubenvb
4个回答

4
“测试结果表明,输出值是不同的。”
“有多大的差异足以引起重视?你声称希望达到8个有效数字(小数位?)的一致性,我不相信你在符合ISO/IEC 10967-3:2006 §5.3.2标准的任何实现中找到了少于该标准的输出精度。”
“你明白千亿分之一的三角函数误差代表了多么微小的数值吗?它在一个地球轨道大小的圆上只有不到3公里。除非你计划前往火星并使用次标准的实现,否则你所声称的“不同”没有意义。”
“针对评论添加:”
“请阅读What Every Programmer Should Know About Floating-Point Arithmetic。认真阅读。”
“既然你声称:”
“精度不如位对位的相等性重要”
“你只需要8个有效数字”

如果您的值超过了8个有效数字,那么您应该将其截断为8个有效数字。


3
任何差异都太多了。结果必须完全相同,一直到最后一个位。数值不需要非常精确,但必须始终如一。当我想要具有确定性的模拟器时,没有比这更重要的了。 - kovarex
@kovarex 请看上面的 "added"。 - msw
1
截断并不能解决问题,总会有两个“相邻”的双精度数,它们将进入不同的截断区间。因此,即使在第15位上的小差异也可能会影响(虽然不太可能)截断到第8位的数字的值。 - kovarex

3
我想最简单的方法就是选择一个实现所需数学函数的自由运行库: 然后使用它们的实现。请注意,上面列出的选项是公共领域或BSD许可证或其他自由许可证。如果您使用该代码,请遵守许可证。

2
你可以使用泰勒级数(实际上看起来你正在使用,可能不知道)。
在维基百科(或其他地方)上查看: https://en.wikipedia.org/wiki/Taylor_series 这里有最常见函数的列表(exp、log、cos、sin等)https://en.wikipedia.org/wiki/Taylor_series#List_of_Maclaurin_series_of_some_common_functions,但是如果你有一些数学知识,就可以找到/计算几乎所有东西(好吧,显然不是所有东西,但...)
一些例子(还有许多其他例子)。

Taylor1

注释:
  1. 你添加的术语越多,精度就越高。
  2. 我不认为这是计算所需内容的最有效方法,但它是一个相当“简单”的方法(我的意思是这个想法)
  3. 如果您决定使用它,那么factorial(n)函数可能非常有用
希望能对你有所帮助。

是的,这个函数使用泰勒级数。这可能是我必须要做的事情,但我想,这已经被转换为带有正确步骤和准备工作的C ++代码许多次了,我想避免再做同样的工作。 - kovarex

0
我建议研究使用查找表和线性/双三次插值。这样你可以精确控制每个点的值,而且不需要进行大量的乘法运算。sin/cos函数的泰勒展开也不太好用。
Spring RTS曾经与这种失同步错误进行了长期搏斗:尝试在他们的论坛上发布,虽然很少有老开发人员留下,但那些人仍然应该记得问题和解决方法。
在这个帖子中http://springrts.com/phpbb/viewtopic.php?f=1&t=8265,他们具体讨论了libm确定性(但是不同的操作系统可能有不同的libc,具有微妙的优化差异,因此您需要采取适当的方法并排除库)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接