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!