Math 版 (精华区)

作  家: oli (西西 ) on board 'Math'
题  目: 小烟谈数学（1）————并行算法浅谈（五）
来  源: 哈尔滨紫丁香站
日  期: Sat Aug 16 10:01:56 1997
出  处: bbs@s1000e.whnet.edu.cn

发信人: smoke (小烟), 信区: Mathematics
标  题: 小烟谈数学（1）————并行算法浅谈（五）
发信站: 武汉白云黄鹤站 (Mon Apr 28 18:05:52 1997)

大结局！

假如小烟手里有N/2个Penitum处理器，把它们毫不可惜地用到上面那个求和
过程中去。每个Penitum负责作一次上面所说的加法：
                 (k)     (k-1)      (k-1)
                a (i) = a (2i-1) + a (2i), i=1,...,N/(2^k)

虫虫们看出来了吧，当k = 1时，每个Penitum都作了一次加法，
当k = 2时，只要N/4个Penitum作一次加法就够了。
当k = log N 时，则只要一个处理器作一次加法就能算出最后结果呢。
         2
这么着，咱们总共只要计算log N次加法就能得到结果。而由单处理器
                           2
来求和需要作N-1次加法。两者的速度比就无需小烟赘言了。
熟悉信号处理的虫虫也许看出来了，怎么这个并行计算方法跟那些个
傅里叶啊，WALSH啊，小波等等的快速算法如此相似来着？小烟无言以对，
也许这就是所谓数学的统一美，协调美，和谐美吧。

--
      * 流水带走光阴的故事，我轻轻地悠唱 *                      

※ 来源:．武汉白云黄鹤站 s1000e.whnet.edu.cn．[FROM: 202.114.2.60]

--
※ 来源:·哈尔滨紫丁香站 bbs1.hit.edu.cn·[FROM: bbs@s1000e.whnet.edu]