乘法算法是计算两个数值相乘乘积的算法。为了提高运算效率,不同大小的数字适用不同的乘法算法。自十进制数字系统诞生以来,就已开始发展乘法算法。
网格法(英语:Grid method multiplication) (或盒式法)是一种用于给小学生进行乘法计算启蒙的简单乘法算法。自1990年代后期以来,它一直是英格兰和威尔士公立小学数学课程的标准部分。
将两个乘数分解(“划分”)为百位、十位或个位的部分,然后在相对简单的乘法步骤中直接算出这些部分的乘积,再将其一一相加以算出最终结果。用这种方法计算 和分别是被乘数及乘数的第位数字,和 的最高位都已补0,补到位数,而是乘积的第位,而是计算后产生的进位(i=1表示是个位),则
or
简单的推论可以证明进位不会超过,的总和不会超过 * :第一栏的进位是0,其他栏最多有个数字,最多也只会从前一栏进位。总和最多是 * ,进位到下一位的最多是 * / 或。因此这些数字都可以用O(log )位数储存。
伪代码下的对数空间算法为
:multiply(a, b, base) // Operands containing rightmost digits at index 1 tot = 0 for ri = 1 to p + q - 1 //For each digit of result for bi = MAX(1, ri - p + 1) to MIN(ri, q) //Digits from b that need to be considered ai = ri − bi + 1 //Digits from a follow "symmetry" tot = tot + (a * b) product = tot mod base tot = floor(tot / base) product = tot mod base //Last digit of the result comes from last carry return product
热门信息
阅读 (128)
1 童子命的口诀对照表,是不是童子命一查就知道阅读 (88)
2 让男人爱你的咒语——和合术咒语阅读 (71)
3 自己怎么简单的做和合术?找道长做快速挽回阅读 (70)
4 和合术真都有用吗?效果好吗?阅读 (68)
5 阳宅风水学入门图解大全100例,让你马上成为风水专家