# yaox023's blog # Russian Peasant Multiplication

Speaking of multiplication, we all learn it in school. It is called grade-school multiplication. Below content I copy from wiki show the basic process.

``````      23958233
×         5830
———————————————
00000000 ( =  23,958,233 ×     0)
71874699  ( =  23,958,233 ×    30)
191665864   ( =  23,958,233 ×   800)
+ 119791165    ( =  23,958,233 × 5,000)
———————————————
139676498390 ( = 139,676,498,390)
``````

It turns out that this kind of operations is not suitable for CPU. There is an algorithm call Russian Peasant Multiplication, which can do multiplication only by shifting and adding operations, which is more suitable for computers. Let's see how it works.

Suppose we want to calculate `a*b`. We can rewrite this expression into `a*2*b/2`. So we make `a=a*2` and `b=b/2`, and then calculate `a*b` again. As you can see, in this way, we make `a` bigger and `b` smaller. Follow the same process, until we make `b` as value 1, then we stop. Then the final result is `a`. Let's see an example.

``````5 * 8 =>
(5*2) * (8/2) =>
(10*2) * (4/2) =>
(20*2) * (2/2) =>
40
``````

Another thing we need to consider is that as we divide `b` by 2, `b` could become odd number. We can't divide an odd number by 2, so we need to somehow make it even. The most easy way is to subtract 1. So follow this formula: `a*b => a*(b-1) + a`, we can make `b` even again.

Before we go to code, last thing you may notice that from above process is that there are still muliplications(`*2`, `/2`). But this 2 multiplications can be achieved by bit shifting operations, so we will not do multiplication in code. Check my previous article about bit operations if you are not familar with them.

Now let's implement this algorithm in code.

``````function multiply(x: number, y: number): number {
let res = 0;

// loop until y becomes 1
while (y > 1) {

// check if y becomes odd
if ((y & 1) > 0) {
res += x;
}

// x * 2
x <<= 1;

// y / 2
y >>= 1;
}

return res + x;
}
``````