作者jeunder ()
看板Programming
标题Re: [问题] 快速-九九乘法表
时间Tue May 27 03:00:04 2008
最简单的方法, 没有人想到吗?
首先, i*j = j*i, 所以几乎有一半不用算.
其次, i*(j+1) = i*j + i, 所以只要拿前一项 i*j 加上 i, 就得到 i*(j+1).
同理, (i+1)*j = i*j + j.
所以周围的项目都可以用加法算出来, 而且只用 "一次" 加法.
依此类推扩展.
※ 引述《TKyo (暗黑贵公子)》之铭言：
: ※ 引述《kbslave (ITer)》之铭言：
: : 最近朋友问我一个问题『要如何写一个快速的 N N乘法表』，
: : 也就是要计算出一个Array[n][n]，其中array[i][j]等於ixj，
: : 且全部纪录此array中，当然最简单的做法就是用双for-loop去跑，
: : for
: : for
: : array[i][j]=i*j;
: : 我也想到另一个方法http://blog.kbslave.com/2008/05/1.html，
: : 但感觉效果其实没有很好，不知道有没有人有更快的解法呢？
: 1.以 2^x 为底, 对被乘数做因式拆解
: ps.不知道这 "解释名词" 是否有误?? @@
: ex. 100 = 2^6 + 2^5 + 2^2 = 64 + 32 + 4
: 17 = 2^4 + 2^0 = 16 + 1
: 2.使用被乘数 "位移和加法" 的方法来加快速度, 减少乘法消耗的大量 clock
: ex. 假设乘数为 n
: n * 100 = n * (64 + 32 + 4) = n << 6 + n << 5 + n << 2
: n * 17 = n * (16 + 1) = n << 4 + n
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.64.87.245
1F：推 KanoLoa:所以程式用加法比乘法快喽？＿？ 203.67.89.234 05/27 06:08