🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Russian Peasant Multiplication in C
Multiply two numbers using only halving, doubling and addition, then discover why this ancient trick is the same shift-and-add loop inside simple embedded CPUs.
Russian peasant multiplication in C is a short and beautiful loop problem. It multiplies two positive integers without using the * operator, relying only on division by 2, multiplication by 2 and addition. It is a perfect exercise for a free C tutorial because it teaches loops, the modulus operator and bit shifting in one go, and it reveals how small embedded C programming targets without a hardware multiplier can still multiply. Our free C programming course uses it to connect a classroom algorithm to real processor behaviour.
What You Will Learn
- The halve, double and add rule of the Russian peasant method.
- Why the method works, explained with binary numbers.
- How to write it with a
whileloop,%and then with shift operators. - How to choose data types so the product does not overflow.
- How the same idea appears in microcontrollers and hardware multipliers.
Prerequisites
You should know the while loop, if, the modulus operator and the idea of binary numbers. The bitwise operators >>, << and & from the operators chapter are used in the second version of the program.
How Russian Peasant Multiplication Works
Write the two numbers side by side. Repeatedly halve the left number (dropping any remainder) and double the right number until the left number becomes 1. Then add up only those right-hand values whose left partner is odd. The total is the product.
Take 19 × 25:
| Left (halve) | Right (double) | Left odd? | Added to sum |
|---|---|---|---|
| 19 | 25 | Yes | 25 |
| 9 | 50 | Yes | 50 |
| 4 | 100 | No | 0 |
| 2 | 200 | No | 0 |
| 1 | 400 | Yes | 400 |
Sum: 25 + 50 + 400 = 475, and indeed 19 × 25 = 475.
Why Does the Trick Work?
The secret is binary. Any number is a sum of powers of two, and the odd/even test on each halving step simply reads the binary digits of the left number from the lowest bit upward.
Doubling the right number each round produces 25 × 1, 25 × 2, 25 × 4, 25 × 8 and 25 × 16. A row is added exactly when that power of two is part of 19, that is, when the corresponding bit is 1. So the method is long multiplication done in base 2.
Writing the Program in C
We print a trace table while computing so you can compare it with the paper version. The product is accumulated in a wider type, unsigned long long, because doubling grows numbers quickly.
#include <stdio.h>
int main(void)
{
unsigned int left, right_start;
unsigned long long right, sum = 0;
printf("Enter two positive numbers: ");
if (scanf("%u %u", &left, &right_start) != 2 || left == 0 || right_start == 0)
{
printf("Need two positive integers\n");
return 1;
}
right = right_start;
printf("%10s %12s %s\n", "halve", "double", "action");
while (left >= 1)
{
printf("%10u %12llu ", left, right);
if (left & 1u)
{
sum += right;
printf("odd -> add\n");
}
else
printf("even -> skip\n");
left >>= 1;
right <<= 1;
}
printf("Product = %llu\n", sum);
return 0;
}
Build, Run and Expected Output
gcc -Wall -Wextra -std=c11 -o peasant peasant.c
./peasant
Entering 19 25:
halve double action
19 25 odd -> add
9 50 odd -> add
4 100 even -> skip
2 200 even -> skip
1 400 odd -> add
Product = 475
Entering 13 7:
halve double action
13 7 odd -> add
6 14 even -> skip
3 28 odd -> add
1 56 odd -> add
Product = 91
Line by Line
- Input check. Zero is rejected because the loop would never run and the answer is trivial. Negative numbers are also excluded by the unsigned types.
left & 1utests the lowest bit. It gives the same answer asleft % 2 != 0, but compiles to a single instruction on most processors.left >>= 1divides by two and drops the remainder, exactly the halving step.right <<= 1doubles the number.- Loop ends after the iteration where left equals 1, because halving 1 gives 0 and the condition
left >= 1fails.
| Math version | Bit version | Meaning |
|---|---|---|
a % 2 != 0 | a & 1 | Is the number odd? |
a / 2 | a >> 1 | Halve (unsigned) |
b * 2 | b << 1 | Double |
Embedded connection
Small microcontrollers such as some 8-bit and Cortex-M0 class cores have no single-cycle multiplier or no multiplier at all. Compilers then replace a * b with a shift-and-add routine that follows this very algorithm. Even when hardware exists, its multiplier circuit performs shifted additions of partial products.
Overflow and Data Types
Each pass doubles right. With a 32-bit input the left number needs at most 32 halvings, so right can grow to about 263 and the sum to just under 264, which still fits in unsigned long long. If you used plain int for everything, a product like 100000 × 100000 would overflow silently and print nonsense.
| Type used for result | Largest safe product | Behaviour on overflow |
|---|---|---|
int (32-bit) | About 2.1 billion | Undefined behaviour |
unsigned int | About 4.29 billion | Wraps around silently |
unsigned long long | About 1.8 × 1019 | Fine for two 32-bit inputs |
Common Mistakes and Troubleshooting
right_start.
- Using
while(left > 1). The loop then stops before the last row is added and the answer is short by the final doubled value. - Adding when left is even. Only odd rows count.
- Wrong printf specifier.
%dwith anunsigned long longprints garbage. Use%llu. - Forgetting the sum starts at zero. Uninitialised sum gives random answers.
- Allowing zero or negative input. Signed negative numbers halved with
>>behave in an implementation defined way.
Best Practices and Performance
- The loop runs once per bit of the left number, about 32 times at most, so it is fast and predictable. Pick the smaller number as the left one to finish sooner.
- Prefer unsigned types for bit manipulation; shifting signed values has corner cases.
- On a CPU with a hardware multiplier, simply use
*. This algorithm teaches the idea and helps when no multiplier exists. - Remove the trace printing in production code. The printing is for learning and slows the loop a lot.
- Test with 1 as an input, powers of two and the maximum values to prove no overflow occurs.
Real-World Uses
- Software multiplication routines on cores without a multiply instruction.
- Modular exponentiation and the “square and multiply” idea used in cryptography follow the same halving pattern.
- Digital signal processing code that replaces multiplication by shifts for speed.
- Hardware design: array multipliers are shift-and-add in silicon.
Summary and Key Takeaways
- Halve the left number, double the right, add the right value whenever the left is odd.
- It works because the odd/even test reads the binary digits of the left number.
- Use
& 1,>>and<<for the efficient embedded style. - Choose a wide enough type to hold the product.
The next file in this free embedded C course is the chapter quiz with interview questions, which also includes practice problems to try on your own.
Frequently Asked Questions
Is Russian peasant multiplication faster than the * operator?
No. On modern CPUs the hardware multiplier is faster. The algorithm matters on processors without one and as a learning tool.
Does it work if the first number is even at the start?
Yes. Even rows are simply skipped, and the odd rows later still produce the correct sum.
Why is it also called the ancient Egyptian method?
The same doubling and adding idea appears in ancient Egyptian arithmetic. Different cultures used equivalent procedures.
Can I use it with negative numbers?
Multiply the absolute values and fix the sign afterwards. The basic version here is meant for positive integers.
What is the time complexity?
It is proportional to the number of bits in the left number, so about 32 iterations for a 32-bit input.
How is this used in embedded systems?
Compilers emit shift-and-add sequences for multiplication on cores that lack a hardware multiplier.
Free Embedded C Course
Keep building real skills with the EmbeddedPathashala free C programming course, designed to take beginners all the way to embedded systems and Linux development.

2 Comments