Algorithm - Russian multiplication

Non-mainstream algorithm for multiplying two positive integers

Assume n and m are two positive integers, calculate n*m, and now use the input of n as a measure of instance size.

Assuming n is an even number, an instance with half the original size must process n/2, n*m=n/2 * 2m

Assuming n is an odd number, only a simple adjustment is needed to the formula, n*m=(n-1)/2 * 2m

And use 1*m=m as the termination condition.

When we write down an example, we will find that when all the current n values ​​are odd, we only need to add the corresponding m values ​​to get the product of n*m.

For example: 50*65=25*130=12*260 (130)=6*520=3*1040=1*2080===2080 1040 130=3250

Let’s start the code implementation:
#include <iostream><br> using namespace std;</iostream>

int main()
{
int n,m,mul=0;
cin>>n>>m;
for(int i=n>>1;i>=1;i=i>>1)
{
m=m

The above is the detailed content of Algorithm - Russian multiplication. For more information, please follow other related articles on the PHP Chinese website!