Home > System Tutorial > LINUX > Algorithm - Russian multiplication

Algorithm - Russian multiplication

WBOY
Release: 2024-02-16 09:10:18
forward
1268 people have browsed it

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!

source:linuxprobe.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template