计算科学 - 时间复杂度l2l2-向量的范数 - 吾爱随笔录

计算科学线性代数浮点复杂

2021-12-18 02:58:55

采用 $l_2$ -向量范数 $\mathbf{v}\in\mathbb{R}^n$ （要么 $\mathbf{v}\in\mathbb{C}^n$ 如果存在差异）。

我们有以下定义 $l_2$ -范数 $\mathbf{v}$ ：

‖ v ‖_{2} = \sqrt{| v_{1} |^{2} + \dots + | v_{n} |^{2}}

$\lVert\mathbf{v}\rVert_2= \sqrt{|v_1|^2+\dots+|v_n|^2}$

其中的绝对值（如果复数，则为复数模）。 $|v_i|$ $v_i$ $v_i$

我想最困扰我的是平方根计算。我发现平方根被认为是一次翻牌，因此复杂度是翻牌。 $2n$

这难道不是错误的，因为平方根应该花费更多时间来计算？

1个回答

平方根在IEEE 754-2008 标准中被视为单个浮点运算，但这并不意味着它与其他运算花费相同的时间。在英特尔至强处理器上，平方根的延迟（一条指令完成所需的周期数）可能比求和或乘法长 5 到 7 倍。您可以通过比较英特尔至强可扩展处理器吞吐量延迟文档中的指令 FADD、FMUL 和 FSQRT 的延迟报告来检查这一点。

以上假设您正在以最直接的方式实现范数，而不使用融合乘法加法、矢量化操作等。 $\ell^2$

其它你可能感兴趣的问题