使用预先计算的平移arrays的快速Sin / Cos
我有以下代码使用预先计算的内存表进行Sin / Cos函数。 在下面的示例中，该表具有1024 * 128个项目，涵盖从0到2pi的所有Sin / Cos值。 我知道我可以使用Sin / Cos对称并只保留1/4的值，但是在计算值时我会有更多’ifs’。
private const double PI2 = Math.PI * 2.0; private const int TABLE_SIZE = 1024 * 128; private const double TABLE_SIZE_D = (double)TABLE_SIZE; private const double FACTOR = TABLE_SIZE_D / PI2; private static double[] _CosineDoubleTable; private static double[] _SineDoubleTable; 设置转换表
private static void InitializeTrigonometricTables(){ _CosineDoubleTable = new double[TABLE_SIZE]; _SineDoubleTable = new double[TABLE_SIZE]; for (int i = 0; i < TABLE_SIZE; i++){ double Angle = ((double)i / TABLE_SIZE_D) * PI2; _SineDoubleTable[i] = Math.Sin(Angle); _CosineDoubleTable[i] = Math.Cos(Angle); } }
值是弧度的两倍。
Value %= PI2; // In case that the angle is larger than 2pi if (Value < 0) Value += PI2; // in case that the angle is negative int index = (int)(Value * FACTOR); //from radians to index and casted in to an int double sineValue = _SineDoubleTable[index]; // get the value from the table
我正在寻找一种更快的方法来做到这一点。 以上4行是整个过程的约25％（执行数十亿次）。
您可以尝试使用不安全的代码来消除数组边界检查。
但是，即使是不安全的优化版本似乎也不会出现在Math.Sin附近。
基于随机值的1’000’000’000次迭代的结果：
(1) 00:00:57.3382769 // original version (2) 00:00:31.9445928 // optimized version (3) 00:00:21.3566399 // Math.Sin
码：
static double SinOriginal(double Value) { Value %= PI2; if (Value < 0) Value += PI2; int index = (int)(Value * FACTOR); return _SineDoubleTable[index]; } static unsafe double SinOptimized(double* SineDoubleTable, double Value) { int index = (int)(Value * FACTOR) % TABLE_SIZE; return (index < 0) ? SineDoubleTable[index + TABLE_SIZE] : SineDoubleTable[index]; }
测试程序：
InitializeTrigonometricTables(); Random random = new Random(); SinOriginal(random.NextDouble()); var sw = System.Diagnostics.Stopwatch.StartNew(); for (long i = 0; i < 1000000000L; i++) { SinOriginal(random.NextDouble()); } sw.Stop(); Console.WriteLine("(1) {0} // original version", sw.Elapsed); fixed (double* SineDoubleTable = _SineDoubleTable) { SinOptimized(SineDoubleTable, random.NextDouble()); sw = System.Diagnostics.Stopwatch.StartNew(); for (long i = 0; i < 1000000000L; i++) { SinOptimized(SineDoubleTable, random.NextDouble()); } sw.Stop(); Console.WriteLine("(2) {0} // optimized version", sw.Elapsed); } Math.Sin(random.NextDouble()); sw = System.Diagnostics.Stopwatch.StartNew(); for (long i = 0; i < 1000000000L; i++) { Math.Sin(random.NextDouble()); } sw.Stop(); Console.WriteLine("(3) {0} // Math.Sin", sw.Elapsed);
我假设泰勒的扩张对你没用。 所以如果你想使用一个表：你只需要一个表大一半。
-
cos(x) = sin(pi/2-x). -
sin(pi + x) = -sin(x)
您可以使您的代码不分支。 首先转换为int格式。
int index = (int)(Value * FACTOR); index %= TABLE_SIZE; // one instuction (mask) index = (index >= 0) ? index :TABLE_SIZE-index; // one instruction isel double sineValue = _SineDoubleTable[index];
无论如何，与Math.Sin比较。 简介简介Priofile。 （在实际示例中，缓存未命中可能会降低代码速度。）
如果你需要多次计算，
- 使用特定于处理器的数学库，如IKML或ACML和
- 计算组（向量）中的值。
- 如果需要两者，请始终同时计算值的sin和cos。
- 检查算法复杂性和实现设计。
- 确保您正在使用所有处理器提供的function – x64架构，以及任何有用的矢量指令。
关于正弦和余弦的快速计算有一些很好的注意事项： http ： //www.research.scea.com/gdc2003/fast-math-functions.html
他介绍了如何将输入值映射到所需范围，以及使用迷你最大多项式（最小化区间上的最大误差，这与泰勒级数不同），甚至是SIMD优化。
这看起来很不错，除了mod操作。 你能没有它吗？
如果值接近零，则可以使用
while(Value > PI2) Value -= PI2; while(Value < 0) Value += PI2;
或者，首先将索引转换为整数（可能超出范围）可能会更快，然后将其修改为整数。 如果表大小将是2的倍数，您甚至可以使用位操作（如果编译器不已执行此操作）。
不能保证它会带来很多好处，但是根据你的处理器，整数数学通常比浮点数学更快。 在这种情况下，我可能会重新排列前三行，先计算一个整数，然后减小其范围（如果需要）。 当然，正如BlueRaja指出的那样，使用C ++几乎肯定也会有所帮助。 使用汇编语言可能不会有太大的好处 – 对于像这样的表查找，C ++编译器通常可以生成相当好的代码。
如果可能的话，我也会非常努力地看待你的准确度要求 – 不知道你对这些值做了什么，很难说，但是出于很多目的，你的表格大小和存储的精度都是远远超出必要的甚至接近有用的。
最后，我注意到至少值得研究这整个策略是否值得。 毫无疑问，使用表来避免复杂计算是一个可靠的策略。 尽管如此，处理器的速度比内存快得多 – 到目前为止这种表查找通常都是净损失。 事实上，几乎唯一的方法是表格是否足够小，以适应处理器缓存。
你可以尝试的一件事是使用cos（x）= sin（x + pi / 2）的事实。 并使正弦表大四分之一，因此您可以将其重新用作从四分之一开始的余弦表。不确定C＃是否允许您获得指向表格中间的指针，如C所示。 但即使不是，减少的缓存使用量可能比增加到正弦表的偏移量的时间更多。
那是，用C表示：
double* _CosineDoubleTable = &_SineDoubleTable[TABLESIZE / 4];
那将是非常快的。
如果你真的需要从这段代码中挤出所有可以想象的性能下降，你可能要考虑在C ++ dll（甚至ASM）中编写它的这一部分（包括循环数十亿次的循环）。 确保将编译器设置为允许可用的最大可能指令集。
[编辑]我错过了表的大小 – 由于缓存未命中，这可能会大大减慢代码速度。 您是否尝试过针对Math.Cos（）或其他近似trig函数的方法进行基准测试（使用Taylor系列可以通过一些简单的乘法获得非常好的近似值）