The Universe of Discourse

Egyptian fraction multiplication

(Very much previously: Egyptian Fractions)

Back in March, I had been reading On the Egyptian method of decomposing !!2/n!! into unit fractions by Abdulrahman A. Abdulaziz, and I reported that:

There is some indication that Ahmes preferred fractions with even denominators, because they are easier to double, and the usual Egyptian method of multiplication required repeated doubling.

Although I had long ago written an article about why the Rhind mathematical papyrus (RMP) has a table of Egyptian fraction expansions of !!\frac23, \frac25, \frac27\ldots!! but no similar table for any other numerator. I had proposed a very reasonable algorithm for how the table of !!\frac2n!! would give you the ability to compute !!\frac mn!! for any !!n!!, but for some reason I never connected this in my head with how the Egyptians actually did multiplication. The Egyptian multiplication algorithm makes my original surmise very plausible, but a little bit inside-out.

Also, this blog has somehow never discussed the ancient Egyptian method of multiplication, which reduces multiplication to addition without a need for multiplication tables. You don't have to remember complicated facts like !!7×8=56!!, only simple facts like !!7+7=14!!.

Egyptian multiplication

Let's say we'd like to multiply !!364!! by !!41!!. First let's observe that it's quites easy to double a number like !!364!!, significantly easier than to multiply it by anything else. First, !!4+4=8!!, so write down an !!8!! under the !!4!!:

$$ \begin{array}{} 3 & 6 & 4 \\ & & {\bf 8} \end{array} $$ Now !!6+6=12!! so write down a !!2!! under the !!7!! and note a carry in the next column. Or just remember it until the next step — when doubling, the carry is never bigger than !!1!!, so we don't have to remember how much it is, just that there is one:

$$ \begin{array}{} 3{\bf {}^\bullet} & 6 & 4 \\ & {\bf 2} & 8 \end{array} $$

The little mark by the !!3!! means that we are remembering there was a carry from the previous column.

Now !!3+3!! plus the carry is !!7!!, so write the !!7!! under the !!3!!:

$$ \begin{array}{} 3^1 & 6 & 4 \\ {\bf 7} & 2 & 8 \end{array} $$

And yes, !!364+364=728!!, quick and easy. Between each step and the next we only need to remember one thing: is there a carry? And someone can do the whole thing with minimal training, knowing only that !!1+1=2, 2+2=4, 3+3=6,\dots, 9+9=18!!.

Let's double again:

$$ \begin{array}{} 7 & 2{\bf {}^\bullet} & 8 \\ & & {\bf 6} \\[10pt] 7 & 2^\bullet & 8 \\ & {\bf 5 } & 6 \\[10pt] 7 & 2^\bullet & 8 \\ {\bf 14} & 5 & 6 \end{array} $$

When the Egyptians wanted to multiply !!364×41!!, they would do a series of these doublings, and label each one (perhaps just mentally) with the corresponding power of 2:

$$ \begin{array}{rr} 1 & 364 \\ 2 & 728 \\ 4 & 1456 \\ 8 & 2912 \\ 16 & 5824 \\ 32 & 11648 \\ \end{array} $$

Then they'd find the numbers in the left-hand column that added to 47, and mark them. This is easy to do, using the greedy method: !!32 < 41!!, so mark the !!32!!, then subtract !!41-32=9!! and proceed up to the next line. !!16\not\lt 9!!, so don't mark the !!16!!, but do mark the !!8!!, and so on:

$$ \begin{array}{rrr} 1 & 364 & ✅ \\ 2 & 728 & \\ 4 & 1456 & \\ 8 & 2912 & ✅ \\ 16 & 5824 & \\ 32 & 11648 & ✅ \\ \end{array} $$

Now just add up the middle column of numbers, but ignore the lines with no check marks:

$$ \begin{array}{rrr} 1 & 364 & ✅ \\ 8 & 2912 & ✅ \\ 32 & 11648 & ✅ \\ \hline & {\bf 14924} & \end{array} $$

And that's the answer, !!364 \times 41 = 14924!!. Isn't that cute?

The algorithm is really quite practical. It is often known as the Russian Peasant algorithm, apparently because it was also used by actual Russian peasants.

Once again, with fractions

Now fractions. Say we want to multiply !!4+\frac{1}{35}!! by !!29!!. The !!4!! we already know how to do and it is easy enough, we just do it like above, doubling !!4!! repeatedly and adding the correct doubles. Or if we're even a little clever we realize we can do it by doubling !!29!! twice, which is quicker.

But Egyptian notation for fractions was terrible. They had a notation for !!\frac1{35}!!, and a special notation for !!\frac 23!!, but no general quotient operation like the fraction bar. Instead they wrote fractions as sums of “unit fractions” with numerator !!1!!, and they had tables like the one in the Rhind Mathematical Papyrus, for converting non-unit fractions to sums of unit fractions, for example $$\frac2{35} = \frac1{30} + \frac1{42}.$$

!!\def\uf#1.{\frac1{#1}}\def\u#1.{\uf#1.}!!

So now we want to multiply !!19\times \frac1{35}!!. Per the algorithm we need to double !!\frac1{35}!! four times until we get !!\uf35. \times 16!!. For the first doubling we go to the table for !!\frac2{35}!!:

$$ \begin{array}{} 1 & \uf35. \\ 2 & \uf30. + \uf42. \\ \end{array} $$

For the next doubling, we don't have to go to the table, because the double of !!\uf30.!! is just !!\uf15.!! and the double of !!\uf42.!! is !!\uf21.!!. That's why the table prefers expansions with even denominators.

$$ \begin{array}{} 1 & \uf35. \\ 2 & \uf30. + \uf42. \\ 4 & \uf15. + \uf21. \\ \end{array} $$

For the third doubling we do go back to the table to find !!\frac2{15}!! and !!\frac2{21}!!:

$$ \begin{array}{} 1 & \uf35. \\ 2 & \uf30. + \uf42. \\ 4 & \uf15. + \uf21. \\ 8 & \uf10. + \uf30. + \uf14. + \uf42. \\ \end{array} $$

Since the denominators in the fourth row are all even, we don't need to consult the table to write the fifth row:

$$ \begin{array}{} 1 & \uf35. \\ 2 & \uf30. + \uf42. \\ 4 & \uf15. + \uf21. \\ 8 & \uf10. + \uf30. + \uf14. + \uf42. \\ 16 & \uf5. + \uf15. + \uf7. + \uf21. \\ \end{array} $$

Now we wanted !!29\times\uf35.!!, so add rows !!16, 8,4,!! and !!1!! because !!16+8+4+1=29!!. We get this:

$$ \begin{array}{rl} \frac{29}{35} = & \u35. \\ & + \color{darkgreen}{\u15.} + \color{purple}{\u21.} \\ & + \u10. + \u30. + \u14. + \u42. \\ & + \uf5. + \color{darkgreen}{\uf15.} + \uf7. + \color{purple}{\uf21.} \\ \end{array} $$

Oh no…

There are duplicates of !!\color{darkgreen}{\u15.}!! and !!\color{purple}{\u21.}!! and that's not allowed, so we use the !!\frac2n!! table to replace the !!\color{darkgreen}{\u15.+\u15.}!! with !!\u10.+\u30.!! and the !!\color{purple}{\u21.+\u21.}!! with !!\u14.+\u42.!!:

$$ \begin{array}{rl} \frac{29}{35} = & \u35. \\ & + \u10. + \u30. + \u14. + \u42. \\ & + \u5. + \u7. \\ & + \u10. + \u30. \\ & + \u14. + \u42. \end{array} $$

Now we have duplicate !!\u10., \u14., \u30.!! and !!\u42.!!. Fortunately all the denominators are even:

$$ \begin{array}{rl} \frac{29}{35} = & \u35. \\ & + \u5. + \u7. \\ & + \u5. + \u7. + \u15. + \u21. \end{array} $$

Now we go again to the table to eliminate the two !!\u5.!!'s and !!\u7.!!'s:

$$ \begin{array}{rl} \frac{29}{35} = & \u35. \\ & + \u3. + \u15. + \\ & + \u4. + \u28. + \\ & + \u15. + \u21. \end{array} $$

Once again we have two !!\u15.!!'s:

$$ \begin{array}{rl} \frac{29}{35} = & \u35. \\ & + \u3. \\ & + \u4. + \u28. + \\ & + \u21. \\ & + \u10. + \u30. \end{array} $$

and we are finally done, having discovered that !!\frac{29}{35} = \u3. + \u4. + \u10. + \u21. + \u28. + \u30.!!. Wow.

A slightly cleverer method would be to observe that !!29\times\u35. = \u35. + 28\times\u35. !!, and that !!28\times\u35. !! is simply !! 4\times \u5.!!. I imagine that a competent Egyptian scribe would have noticed this.

Did they really do this?

Wikipedia hints that perhaps the Egyptian didn't actually do go through all of this trouble, that perhaps they computed !!\frac{29}{35}!! first the way we did, as a vulgar fraction, and then only converted to the awful sum-of-unit-fractions notation when they needed to record the final answer.

This would have been analogous to how for hundreds of years Europeans would convert awful Roman numerals into an arrangement of counting board tokens (an abacus, essentially), do the calculation on the counting board, and then convert back to awful Roman numerals to record the answer.

While prearing this article I wondered: how can we even be sure that the algorithm will terminate? It's not clear to me. There was that point where we got rid of a !!\frac2{15}!! and then it came back and we had to get rid of it again.

I had Claude implement the algorithm, using the actual RMP !!\frac2n!! table, and run it for every product up to !!100\times \u101.!! to see if it would get stuck in any loops. It didn't.

It's possible that it would have looped if the !!\frac2n!! table I used had been a little different, and it would be very interesting to learn if the table itself had been somehow constructed so as to prevent the algorithm from looping. But I think it's more likely that it terminates for any reasonable !!\frac2n!! table, because the algorithm has some invariant that always decreases — one which I'm not yet clever enough to see.

I mentioned in the previous article:

The Egyptians, like everyone, often had to multiply by 10.

Most of the really big denominators in the !!\frac2n!! table are multiples of !!10!!. For example it has !!\frac2{47} = \u30. + \u141. + \u470.!! and if you're multiplying by !!2!! or even by !!10!!, only the middle part of this is any trouble. I wouldn't want to multiply !!10\times\u141.!! by the algorithm above, though — the !!\frac2n!! table doesn't even go that high. But maybe they would have done something like: !!10\times \u141. = 10\times(\u3. \times \u47)

$$ \begin{array}{rl} 10\times \u141. & = 9\cdot\u141. + \u141. \\ & = 9\left(\u3. \times \u47.\right) + \u141. \\ & = \frac2{47} + \u47. + \u141. \end{array} $$

which doesn't seem too awful.

This whole thing raises a big question for me. To have useful numbers, you need three things:

1. Addition
2. Multiplication
3. Comparison

People often forget #3, but it is crucial, because in the real world you are using the numbers to answer questions like “do we have enough bread to feed 119 laborers for 21 days?” or “will the bridge hold if I drive two loaded ox-carts across it” or similar questions that involve comparisons.

Say we're trying to figure out how to divide nine heaps of grain among !!99!! workers. Supposing that you had somehow failed to notice that the answer was !!\u11.!!, you might use the multiplication algorithm above, and after some grinding it would tell you that:

$$\frac9{99} = \u22. + \u33. + \u99. + \u198.$$

This is a useless answer because the !!\u198.!! means that you should start by taking half of one heap and dividing it into !!99!! equal shares of !!\u198.!! heap for each worker. This is impractical to say the least. So there must be some way to recognize that !!\u22. + \u33. + \u99. + \u198.!! is ⸢actually⸣ !!\u11.!!.

[Other articles in category /math] permanent link