Russian Peasant Multiplication Calculator

Multiply any two numbers using the ancient halving & doubling algorithm. See every step and the binary connection.

×
Quick examples:

What Is Russian Peasant Multiplication?

Russian Peasant Multiplication — also known as Egyptian multiplication, Ethiopian multiplication, or binary multiplication — is an ancient algorithm for multiplying two integers that requires nothing more than the ability to halve a number, double a number, and add. Unlike standard multiplication which relies on memorized times tables, this method reduces every multiplication problem to a sequence of halvings, doublings, and additions.

The algorithm's elegance lies in what it reveals: it is actually computing a binary multiplication in disguise. The rows you keep (where A is odd) correspond exactly to the positions of 1-bits in the binary representation of A. Summing those rows reconstructs A×B as a sum of powers-of-two times B — the very computation a digital computer performs when multiplying two integers in hardware.

Step-by-Step: How It Works

To multiply A × B using the Russian Peasant method:

  1. Write A in the left column and B in the right column.
  2. On each new row: halve A (discard any remainder) and double B.
  3. Continue until A reaches 1.
  4. Cross out (mark as discarded) every row where A is even.
  5. Add up all the B values in the rows where A is odd. This sum is the product A×B.

Example: 7 × 13. Start with A=7, B=13. Since 7 is odd, keep 13. Next: A=3 (⌊7/2⌋), B=26. Since 3 is odd, keep 26. Next: A=1, B=52. Since 1 is odd, keep 52. A has reached 1 — stop. Sum = 13 + 26 + 52 = 91 = 7 × 13. Correct!

The Binary Connection

The deep reason the algorithm works is that any integer A can be written in binary: A = b₀ + b₁×2 + b₂×4 + b₃×8 + ... where each bᵢ is 0 or 1. Therefore:

A × B = (b₀×B) + (b₁×2B) + (b₂×4B) + (b₃×8B) + ...

The doubling column produces B, 2B, 4B, 8B, ... — exactly the terms. The halving column repeatedly divides A by 2; whenever the remainder is 1 (A is odd), the corresponding bit bᵢ = 1 and that row's doubled value is included in the sum. Rows where A is even have bᵢ = 0 and are discarded. The algorithm is therefore a direct implementation of binary multiplication, performed by hand without needing to know binary explicitly.

For example, 7 in binary is 111₂ = 4+2+1. So 7×13 = 4×13 + 2×13 + 1×13 = 52 + 26 + 13 = 91. Notice these are exactly the three kept rows in the algorithm above!

History: Ancient Egypt to Modern Computing

The earliest known written record of this algorithm appears in the Rhind Mathematical Papyrus (also called the Ahmes Papyrus), an ancient Egyptian document dated to approximately 1650 BCE. The papyrus shows Egyptian scribes solving multiplication problems exclusively through doubling — they would double a number repeatedly and then select the appropriate doublings to sum to reach a target product.

The same technique was independently discovered or transmitted to Ethiopia (where it is still called Ethiopian multiplication in some regions) and later to Russia, where it was reportedly used by peasants and merchants as late as the early 20th century — people who needed to multiply but had not learned formal multiplication tables. Charles Peirce, the American logician, described the method in the 19th century and recognized its logical beauty.

In the computer age, the algorithm returned to prominence as the theoretical basis for hardware multipliers. Every modern CPU uses shift-and-add circuits that implement exactly this algorithm: shifting left multiplies by 2 (doubling), shifting right divides by 2 (halving), and conditional accumulation handles the sum of kept rows.

Comparison with Standard Multiplication

AspectRussian PeasantStandard (Long) Multiplication
PrerequisitesHalving, doubling, addition onlyTimes tables 0–9 memorized
Steps for n-digit numbersO(log₂ A) halvings + additionsO(n²) digit multiplications
Error susceptibilityEasy to verify each stepErrors in times table recall possible
Educational valueReveals binary structure of numbersBuilds place-value understanding
Computer analogyDirectly maps to shift-and-addRequires digit lookup tables

Applications in Computer Science

The Russian Peasant algorithm directly inspired several important areas of computer science. Hardware multipliers in CPUs use a variant called shift-and-add multiplication, where a left shift doubles a number (equivalent to the doubling column) and testing the least-significant bit identifies odd numbers (equivalent to checking the halving column). This makes multiplication O(log n) operations in the number of bits.

Fast exponentiation (also called exponentiation by squaring) applies the same idea to powers: compute aⁿ by repeatedly squaring and selecting which squares to multiply together based on the binary representation of n. This is fundamental to RSA cryptography, where modular exponentiation with 2048-bit exponents must be computed efficiently. The Russian Peasant multiplication algorithm, thousands of years old, is thus at the heart of every secure HTTPS connection you make today.

Frequently Asked Questions

An ancient algorithm that multiplies two numbers by repeatedly halving one and doubling the other, then summing the doubled values that correspond to odd halved values. No times tables required — only halving, doubling, and addition.
Write A and B in two columns. Halve A (discard remainder) and double B on each new row until A = 1. Cross out rows where A is even. Sum the remaining B values — that sum equals A×B.
It appears in the Rhind Mathematical Papyrus (c. 1650 BCE), showing ancient Egyptian scribes multiplying via repeated doubling. The same method was later used in Russia and Ethiopia, giving it multiple names.
The halving sequence produces the binary bits of A from LSB to MSB. Rows with odd A correspond to 1-bits; rows with even A correspond to 0-bits. The algorithm sums B times each power-of-two in A, which is exactly binary multiplication.
For humans: it avoids memorized times tables, needing only halving and doubling. For computers: it maps directly to shift-and-add hardware (O(log n) operations), making it very efficient. Hardware multipliers in modern CPUs implement this principle.
Yes. Historical accounts suggest it was used in Russia and Eastern Europe into the 20th century by people without formal schooling. Since it requires only halving, doubling, and addition, it was accessible to anyone who could count and double.
CPU hardware multipliers use shift-and-add: left-shift doubles (like the doubling column), right-shift halves (like the halving column), and a conditional accumulator adds when the LSB is 1 (A is odd). This 3500-year-old algorithm runs inside every modern processor.

Related Calculators

Arithmetic Calculator Long Addition Calculator Binary/Decimal/Hex Converter Scientific Calculator Bitwise Calculator