Two seemingly different versions of the Egyptian Multiplication Algorithm - how do they relate? Here is a computer-based implementation of the Egyptian Multiplication algorithm which I believe is correct:
def multiply_egyptian(a, b):
    print(f&quot;{a} is the multiplicand, {b} is the multiplier&quot;)
    print(f&quot;a = {a}, b = {b}&quot;)
    result = 0
    while b != 0:
        if b &amp; 1 != 0:  # if b is odd
            result += a
        a &lt;&lt;= 1  # Double it
        print(f&quot;a = {a}, &quot;, end=&quot;&quot;)
        b &gt;&gt;= 1  # Halve it
        print(f&quot;b = {b}&quot;)
    print(f&quot;result is: {result}&quot;)
    return result       
    
    
multiply_egyptian(7, 5)

7 is the multiplicand, 5 is the multiplier
a = 7, b = 5
a = 14, b = 2
a = 28, b = 1
a = 56, b = 0
result is: 35
&gt;&gt;&gt;

Here is the written version:
b    a
1  ✓ 7
2    14
4  ✓ 28
8    56

How do they relate?
The algorithm seems to go backwards in some sense. For one thing, the powers of 2 are chosen at the end in the written version.
b starts at 5, but a starts at 7, so contrary to the written version, the movement seems to be &quot;diagonal&quot; - b starts at the bottom, but a starts at the top.
I get that if b is odd, then it must lie between a power of 2, and thus give a remainder when divided by 2. so the remainder at that step of the algorithm is added to the result. What is the remainder at that step of the algorithm?
5//2 = 2 r 1, so I would have expected to add 28, maybe, at that stage, as much as I would expect anything from my current level of understanding - at least 28 is opposite the nearest power of 2 to 5.
Could someone please explain the relationship of the the written algorithm to the computer-based one given, in as much detail as possible?
There are two strands:
The product of two numbers, one of which is written in binary form is: $$A \times (c_n2^n+c_{n-1}2^{n-1}+\cdots+c_12+c_0)=c_n(2^nA)+\cdots+c_1(2A)+c_0A$$ where $c_i=0$ or $1$. Hence one needs to add the doublings of $A$ only for $c_i=1$.
To write a number in binary form, one can use repeated divisions by $2$:
\begin{align*}
35\div2&amp;=17+1\\
17\div2&amp;=8+1\\
8\div2&amp;=4+0\\
4\div2&amp;=2+0\\
2\div2&amp;=1+0\\
1\div2&amp;=0+1
\end{align*} The binary expansion is then the remainders of $1$s and $0$s in reverse order: $35=100011_2$.
The computer program combines these two in one. As it halves $b$ and doubles $a$, it adds the $a$s that correspond to odd $b$s, equivalently the $c_i(2^iA)$ when $c_i=1$. An odd $b_i$, of course, gives a remainder of $c_i=1$.
The written algorithm (which I think is the form actually used by the ancient Egyptians, though they used other short-cuts as well) builds the number $b$ in a binary form visually, for example $5=1+4=c_0+c_12^2$, and transfers those $c_i$ as ticks to the doublings of $a$, i.e. $c_07+c_1(2^27)$.
In the written version, they're just picking out the powers of $2$ in the binary representation of the multiplier: $1+4=5$.  I'm not sure why the last line is included.  Once you get as high as $4$, you're done.  Perhaps their method is to keep doubling until you get a number bigger than the multiplier, but then why bother to double the second column?
After all this is how the algorithm works.  In the computer version, the rows where you have odd numbers in the first column correspond to the places where you have $1$s in the binary representation of the multiplier.
To carry out the algorithm, you check off the largest power of $2$, lees than or equal to the multiplier, then subtract it from the multiplier.  The you check off the largest power of $2$ less than or equal to the difference, subtract it, and continue until you get a difference of $0$.  This is neat.  No division at all, just doubling and subtraction.
Where did you find this called &quot;Egyptian multiplication?&quot;  I've always known it as &quot;Russian peasant multiplication.&quot;