乘法的计算-俄罗斯农夫法

╰+攻爆jí腚メ 2023-01-05 05:23 128阅读 0赞

\*\*

## 乘法的计算-俄罗斯农夫法 ##

\*\*

**假设我想计算35乘以47的乘积是多少，根据俄罗斯农夫法的算法规则有：**

**1. 选取两者中较小数并减去一半，舍去余数得到：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw_size_16_color_FFFFFF_t_70]  
**2.把较大的数每次乘以2再生成一列数。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw_size_16_color_FFFFFF_t_70 1]  
**3.划掉左侧第一列为偶数的所有行**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw_size_16_color_FFFFFF_t_70 2]

**4.把右列中剩余的数相加即可得到两数相乘的结果了**

**47+94+1504=1645=35\*47**

这种算法在计算两数相乘的结果时，只用到了乘以2、除以2和求和运算。对于计算机计算而言，乘以2，除以2能够方便的使用左移和右移实现。

**用Java代码实现**

public static int quickMulti(int A,int B){ 
            int ans = 0;
    
            while(B!=0){ 
            	//如果B为奇数，则和加A
                if((B&1)==1){ 
                    ans = ans + A;
                }
    			//给B除以2，A乘以2
                B = B>>1;
                A = A<<1;
            }
            return ans;
        }
    //分配率
    //B为奇数(Ax2)(B/2)数学中的表示--->(Ax2)(B/2)+A计算机中的表示
    //B为偶数(Ax2)(B/2)

参考文献《极简数学》 克里斯.韦林

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw_size_16_color_FFFFFF_t_70]: /images/20221119/4404077b0dbc4efc9b1b59363a89a008.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210111201519658.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210111201552987.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA0MDAyMw==,size_16,color_FFFFFF,t_70