来福网

乘法算法

乘法算法是计算两个数值相乘乘积的算法。为了提高运算效率,不同大小的数字适用不同的乘法算法。自十进制数字系统诞生以来,就已开始发展乘法算法。

网格法(英语:Grid method multiplication) (或盒式法)是一种用于给小学生进行乘法计算启蒙的简单乘法算法。自1990年代后期以来,它一直是英格兰和威尔士公立小学数学课程的标准部分。

将两个乘数分解(“划分”)为百位、十位或个位的部分,然后在相对简单的乘法步骤中直接算出这些部分的乘积,再将其一一相加以算出最终结果。用这种方法计算 34 × 13 {displaystyle 34times 13} 和分别是被乘数及乘数的第位数字,和 的最高位都已补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

后台-插件-广告管理-内容底部广告位PC端
后台-插件-广告管理-内容底部广告位手机端

评论

全部评论