eyedia

Peasant Arithmetic

Multiplying huge numbers with nothing but halving, doubling and adding — the way ancient scribes did.

peasant.pl · output · proof · check · try it in the playground

The question

Ancient Egyptian scribes multiplied without times tables. To work out 238 × 13 they wrote two columns: halve the left number (dropping any remainder), double the right one, and add up the right-hand numbers in rows where the left one is odd.

The same trick raises a number to a power, squaring instead of doubling and multiplying instead of adding.

Does this really work — even for numbers with thousands of digits? And can the computer show each row?

The scribe’s table for 238 × 13

Halve	Double	Left odd?
238	13	no
119	26	yes: +26
59	52	yes: +52
29	104	yes: +104
14	208	no
7	416	yes: +416
3	832	yes: +832
1	1664	yes: +1664

26 + 52 + 104 + 416 + 832 + 1664 = 3094.

What we tell Eyedia

prod([0, _], 0).
prod([X, Y], Z) :- X =\= 0, 0 =:= X rem 2, S is X//2, T is Y+Y, prod([S, T], Z).
prod([X, Y], Z) :- X =\= 0, 1 =:= X rem 2, S is X//2, T is Y+Y, prod([S, T], R), Z is R+Y.

pow([_, 0], 1).
pow([X, Y], Z) :- Y =\= 0, 0 =:= Y rem 2, S is X*X, T is Y//2, pow([S, T], Z).
pow([X, Y], Z) :- Y =\= 0, 1 =:= Y rem 2, S is X*X, T is Y//2, pow([S, T], R), Z is R*X.

true :+ prod([238, 13], _).
% … nine more questions

Read the middle prod line as: if X is even, halve X, double Y, and carry on. The next line is the odd row: the same, then add Y.

What Eyedia concludes

prod([5, 6], 30).
prod([238, 13], 3094).
prod([8367238, 27133], 227028268654).
prod([62713345408367238, 40836723862713345], 2561007568948454773873964883391110).
pow([5, 6], 15625).
pow([238, 13], 7861409907565911395902147452928).

6 of the 10 answers. The largest, pow([8367238, 2713], …), is a number with 18,781 digits — computed exactly, since Eyedia’s whole numbers have no size limit.

Why: the proof in plain words

The proof for 238 × 13 is the scribe’s table, row by row:

238 is even: halve to 119, double to 26 — rule 2.
119 is odd: halve to 59, double to 52, and add 26 — rule 3.
… one step per row …
1 is odd: halve to 0, and add 1664 — rule 3.
Anything times 0 is 0 — fact 1.

Adding back up the chain: 1664, 2496, 2912, 2912, 3016, 3068, 3094, 3094.

Checked, not just claimed

A separate checker read the proof’s 1,186 steps against the program:

233 steps are exact instances of the rule they cite;
953 calculations — every halving, doubling, “is it odd?” and sum — were recomputed by the checker and agreed, including those on the 18,781-digit power;
no circular reasoning, and every step serves one of the 10 answers.

Verdict: checked. Nothing taken on trust.

Try it

node bin/eyedia.js examples/peasant.pl            # the answers
node bin/eyedia.js --proof examples/peasant.pl    # every row of every table

Or open it in the playground.

Add true :+ pow([2, 100], _). at the end and run again: a new line appears, pow([2, 100], 1267650600228229401496703205376).

Takeaway

An old method is still a good method when each step is simple enough to check. Eyedia keeps every row, and an independent checker redoes every sum — whether the numbers have three digits or eighteen thousand.

This site is open source. Improve this page.