[旧]计算量统计相关问题

Nobody

数值分析书中，评价多项式插值方法时，忽略了加减法，我不知道原因，请指教。

说一下，我的想法吧：

我认为计算机执行一个加法和减法运算的过程，实际上和乘除法是相同的，都是取指令（操作和数据），然后

由运算器执行的，两者在时间上的差异主要出现在运算器上的差异。但是众所周知，计算机取数据是从内存或者

cache取得的，内存和cache的速度显然要比cpu的要慢很多的，也就是取数据的时间要比运算器运算加减乘除

的时间多不少，或者说不是一个级别上的。这样的话，思考一下，一个运算周期的时间，就是取指令和运算加

起来吧，那么是不是就可以将乘除运算和加减运算的时间近乎的等于呢？

这样的话，将加减略掉是不是不准确呢？至少也要加权一下吧。

不当之处，还望指出。谢！！

（ 注： 略看了一点计算机方面的书，cpu的运算过程和我所说类似，但稍微做了些许简化。）



XuQiang

很高兴看到你的问题。
我以前也考虑过这个问题，仅仅记住了乘法比加减法复杂，注意力更多放在了程序编写上。我想我需要查一点资料再来回复。


Liping Gao

一般地我们只考虑乘法和除法，因为乘除占用的时间比加减占用的时间多得多。如果需要取数据的话，这些运算都取数据，这样不就可以不考虑存取数据所占用的时间吗？

只是我个人的理解，不当之处，请指证



XuQiang

我来补充一下。

事实上，早期的数值计算的参考书中，统计计算量仅统计乘除运算的次数，这是因为当初的计算机作乘除运算要比加减运算慢的缘故。

后来，计算机运算速度大幅度提高，加减运算与乘除运算的速度相差的就不是太大了，所以后来统计计算量时是将一个算法的所有运算次数的综合作为计算量的
（在这种情况下，仍会有人统计计算量时分别考虑加减法的次数和乘除法的次数）。关于这种统计，一般称为一个浮点运算为一个flop，我们通过flop数
来衡量程序或算法的效率，但是不太容易统计cpu取数据取指令及运算的总时间（如果想加权处理的话，根据不同的cpu，这个权数难以确定）。可以感觉出
来，一个算法具体实现过程中，其速度与程序中的数据结构及计算机的硬件都是有关系的，统计flop数可以给我们对算法好坏一个直观感觉，真正的速度需要
用实际问题或数值算例来测试。更多需要注意的地方，大家可以参考[1]中的向量化与数据重复使用那一节的内容。

另外，需要注意的是，计算量仅能在一定程度上反映算法的快慢，我们却不能完全依据计算量来判定一个算法的快慢。因为flop数的统计相对粗糙，忽略了内
存通信和其他执行程序的负荷等问题；有一个问题就是计算机运算速度与数据传输速度之间相当的不匹配，也就通常说的访存延迟（这是一个物理约束，不易改
善，有一种办法就是增加每次传输的数据量，用大数据量来降低延迟占用时间的比例）。

所以，我认为，在我们现在接触的基础数值算法中，只需要能够了解计算量的统计过程和结果就可以了，以后我们可以回头查阅的。

参考
[1]《矩阵计算》[美]戈卢布，范洛恩著，袁亚湘等译，科学出版社
[2]《数值线性代数》 徐树方等，北大出版社



Nobody

恩，首先非常感谢老师能抽空回复我的问题。

Very Very Happy and Very Very Lucky ！You are the best teachers！

我感觉xuqiang （抱歉，不知道汉语改怎样拼写，就只好写拼音了）老师的话非常合我的想法。我的想法和老师大体相同吧。

我们课本中，既然以此考虑必有其认为理性的一面，可能这更适合我们的现阶段的知识吧，就如同高中时所学数学定理的证明的不完整性。

但从精确来说，我认为忽略了加减对于评价算法来说，有点粗，不全面。