# Russian peasant multiplication algorithm

Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 15 minutes | Coding time: 10 minutes

Russian peasant multiplication is an interesting way to multiply numbers that uses a process of halving and doubling without using multiplication operator. The idea is to **double the first number and halve the second number repeatedly till the second number doesn’t become 1**. In the process, whenever the second number become odd, we add the first number to result (result is initialized as 0).

### Explanation

The value of a×b is same as (a×2)×(b/2)

- for even values of b: a×b = (a×2)×(b/2).
- for odd values of b :a×b = ((a×2)×(b/2) + a).

In the while loop, we keep multiplying ‘a’ with 2 and keep dividing ‘b’ by 2. If ‘b’ becomes odd in loop, we add ‘a’ to ‘res’. When value of ‘b’ becomes 1, the value of ‘res’ + ‘a’, gives us the result.

**Example:**

Let a and b be 13 , 12 .

**Halving**

for 12 :

- 12/2 = 6 remainder 0

6/2 = 3 remainder 0

3/2 = 1 remainder 1

1/2 = 0 remainder 1.

Reading the remainders from bottom to top, we get 1100, so 12 in base two is 1100.

- 12 = 1100 (base 2)

= 1×2^3 + 1×2^2 + 0×2 + 0×1

= 23 + 22

= 8 + 4.

By halving 12 repeatedly, we have broken it down into powers of two.

### The Distributive Property

We are trying to multiply 12 by 13. We can break 12 down any way we like,

- 12×13

= (4 + 8) × 13

= (2^2 + 2^3) × 13

= 2^2 × 13 + 2^3 × 13.

If we can multiply 13 by 2^2 and 2^3, we will be finished.

### Doubling

when the number in the remainder column is 0, the corresponding row for Russian peasant multiplication is crossed out.

- 2^2 × 13 + 2^3 × 13 = 52 + 104 = 156, so 12 * 13 = 156.

### Pseudocode

```
Let the two given numbers be 'a' and 'b'.
1) Initialize result 'res' as 0.
2) Do following while 'b' is greater than 0
a) If 'b' is odd, add 'a' to 'res'
b) Double 'a' and halve 'b'
3) Return 'res'.
```

### Complexity

- Worst case time complexity:
**Θ(logn)** - Space complexity:
**Θ(1)**

### Implementations

- C++

### C++

`#include <iostream> using namespace std; unsigned int russianPeasant(unsigned int a, unsigned int b) { int result = 0; while (b > 0) { if (b & 1) result = result + a; a = a << 1; b = b >> 1; } return result; } int main() { unsigned int a,b; cout << "Enter two numbers to multiply" << endl; cin >> a >> b; cout << "product: "<< russianPeasant(a, b) << endl; return 0; }`