如何在计算C中两个向量的点积符号时，权衡精度和速度？（非特定于硬件）

Question

假设我有浮点数A和B的两个向量，我需要找到A和B的点积，即符号（A. B）-如果它是正的或负的或0。向量的大小很小，小于100。然而，我需要非常快地做到这一点！
您可以假设A中的所有元素都是[0,1]范围内的浮点数，B的元素是[-500,500]。我在寻找精确的解决方案，但是如果实际上没有给出很多错误的答案，近似的html" target="_blank">html" target="_blank">解决方案也可以做到（我知道，“很多”是主观的，但是我不能在不谈论硬件或实现的情况下给它一个精确的数字）

我探索了使用-O4工作最快的Pragma编译器指令。我探索了实现中的一些更多改进，使其基于底层处理器的自动矢量化支持可并行化。就像avx指令集一样，保持8个自变量并找到点积，这样寄存器容量的所有8个都被利用了。但我认为我们仍然可以更快！基本想法是，我们只需要确定点积的符号，因此有很大的空间来权衡精度以提高速度。所以我试图想出一些数学或算法解决方案来实现这种权衡。我的一个想法是使用FFT（快速傅里叶变换）来减少乘法的数量。我试图探索的另一个想法是按位技巧，但意识到浮点数按位是不可能的。（当您使用像奥法斯特或O3这样的快速实用程序时，IEEE标准不会受到限制）

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

• 这个问题的创造性解决方案可以推广到其他需要精确而不是速度权衡的类似情况。
• 点积符号是一个非常广泛适用的子问题，它出现在十几种场景中（想想复数操作，几个ML算法中的超平面等）

Answer 1

在现代架构上，点积的浮点计算已经非常快，加法需要1个周期，乘法需要1-2个周期。

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