如何在C++中平衡精度和速度以评估两个向量的点积符号？（不涉及硬件）

Question

假设我有两个浮点向量A和B。我需要找到A和B的点积，即sign(A.B) - 如果它是正数、负数或0。向量大小很小，小于100。然而，我需要非常快地完成这个任务！
你可以假设A中的所有元素都是范围在[0,1]之间的浮点数，而B中的元素是[-500,+500]。我正在寻找确切的解决方案，但近似解也可以，只要实际上不会出现太多错误的答案（我知道，“太多”是主观的，但如果没有谈论硬件或实现，我无法确定一个精确的数字）

我探索了Pragma编译器指令，使用-O4速度最快。我探索了更多的实现改进，使其基于底层处理器的自动向量化支持可并行化。例如，对于AVX指令集，保持8个独立变量并查找点积，以便利用所有8个寄存器容量。

但我认为我们仍然可以更快！基本思想是，我们只需要确定点积的符号，因此可以在精度和速度之间进行权衡。所以我正在尝试想出一些数学或算法解决方案，以实现这种权衡。一个想法是使用FFT（快速傅里叶变换）来减少乘法的数量。我尝试探索的另一个想法是位运算技巧，但意识到浮点数的位运算是不可能的。（当你使用像Ofast或O3这样的快速Pragma时，IEEE标准不能保证）

您可能会想为什么要优化这样一个小任务的重要性，但我认为它可能是一个非常有用的问题：-

• 创造性的解决方案可以推广到其他类似的需要在精度和速度之间进行权衡的情况。
• 点积的符号是一个相当普遍适用的子问题，在许多场景中都会出现（想想复数操作、几种ML算法中的超平面等）

- Xi chan

---

多少维？ - bolov

假设 |A| = 100 = |B|。通过点积，我们将向量 A 中的第 i 个值与向量 B 中的相应第 i 个值相乘，则 |A.B| = 100。现在清楚了吗？ - Xi chan

数值范围是多少？向量是否为单位向量？ - ciamej

此任务看起来是使用OpenCL或类似技术的好机会。 - Marek R

点积背后的数学很简单。问题具有O(n)的复杂度，我从数学角度看不到改进的空间，至少没有更大的视角。 - Marek R

Answer 1

在现代架构中，点积的浮点计算已经非常快速，1个周期将用于加法，1-2个周期将用于乘法。

1. 我认为性能只有在计算了大量点积时才会有所影响。
2. 通常这意味着需要读取大量数据。
3. 这意味着运行时间将受到内存带宽的主导。
4. 这意味着只有使用较小的浮点类型，即32位或16位浮点数，才能获得巨大的性能提升。

- Peter G.