# Ethiopian Multiplication

This question is inspired by this answer. Coincidentally, I used to use Ethiopian Multiplication when I was a kid, but had never known the name of the method until recently.

Ethiopian multiplication is a method of multiplying integers using only addition, doubling, and halving.

Method:

1. Take two numbers to be multiplied and write them down at the top of two columns.
2. In the left-hand column repeatedly halve the last number, discarding any remainders, and write the result below the last in the same column, until you write a value of 1.
3. In the right-hand column repeatedly double the last number and write the result below. stop when you add a result in the same row as where the left hand column shows 1.
4. Examine the table produced and discard any row where the value in the left column is even. Sum the values in the right-hand column that remain to produce the result of multiplying the original two numbers together.

For example: 17 x 34

17    34


Halving the first column:

17    34
8
4
2
1


Doubling the second column:

17    34
8    68
4   136
2   272
1   544


Strike-out rows whose first cell is even, we'll do this by encasing those numbers on the right in square brackets:

17    34
8   
4  
2  
1   544


Sum the remaining numbers in the right-hand column:

17    34
8   
4  
2  
1   544
=====
578


So 17 multiplied by 34, by the Ethiopian method is 578.

Golf code that takes two numbers between 1 and 1000 and perform the same layout and algorithm, displaying the product below.

Input Method: However you choose...

Example Input:

19 427


Resulting Output:

19   427
9   854
4 
2 
1  6832
======
8113


Please note the alignment of the digits. This is most important in the layout. Also note that the double line laid out by equal signs must be two characters longer than the overall answer and must be centre justified.

Testing

How will you be testing this? By providing a run of your program using two numbers. These numbers can be extracted from your user ID number (this can be obtained by hovering your cursor over your avatar on the top window). Take your number and take the last three digits, this will be number B, take whatever else remains at the front, that will be number A. Then test for A times B.

Testing example:

My user ID number is 8555, so my numbers are 8 and 555. So my output should look like this:

8  
4 
2 
1  4440
======
4440


Restrictions:

No native multiplication operators permitted save for in the use of "doubling", as per mentioned in the algorithm. In other words, if you're using an operator like *, it can only be used for multiplying by 2 only.

Entries that do not adhere to this will not be considered and the user will be escorted off the premises with a cardboard box full of their belongings. Each entry will have code, plus the test based on your user ID number.

This is code golf. Shortest number of bytes will receive the prize, glory and admiration of their peers... (And maybe a Lamborghini... I said "maybe"!)

• "No actual multiplication must take place." - This is unobservable. You may restrict using of some characters (like * or x), but it is impossible to detect if multiplication is used or not. Except that part, the challenge is interesting.
– user72349
Sep 8, 2017 at 7:14
• Maybe you should either ask for a full description of the code proving that the algorithm is implemented with no multiplication OR an unrestricted simulation that provides the desired output. But that looks like two distinct challenges to me. Sep 8, 2017 at 7:49
• As noted in the sandbox, related, possible dupe. @FelixPalmen, yes, this is long multiplication in binary. Sep 8, 2017 at 11:57

# Charcoal, 91 bytes

≔⟦⟧τ≔⁰σＮθＮηＷθ«⊞τ⪫  Ｉθ⊞υ⪫⎇﹪θ²  ¦[]Ｉη≔⁺σ∧﹪θ²ησ≔÷θ²θ≔⁺ηηη»⊞υ…=⁺²ＬＩσ⊞υ⪫  Ｉσ←Ｅ⮌τ⮌ιＭ⌈ＥυＬιＬυ←Ｅ⮌υ⮌ι


Try it online! Link is to verbose version of code. Explanation:

≔⟦⟧τ≔⁰σ


Sets t to the empty list and s to 0. (u already defaults to the empty list.)

ＮθＮη


Inputs the two numbers.

Ｗθ«


Repeats while q is nonzero.

   ⊞τ⪫  Ｉθ


Wrap q in padding and append it to the list t.

   ⊞υ⪫⎇﹪θ²  ¦[]Ｉη


Wrap h either in padding or [] depending on whether q is odd, and append it to the list u.

   ≔⁺σ∧﹪θ²ησ


Add h to s if q is odd.

   ≔÷θ²θ


Integer divide q by 2.

   ≔⁺ηηη»


Add h to itself.

⊞υ…=⁺²ＬＩσ


Append a suitable string of = signs to the list u.

⊞υ⪫  Ｉσ


Append the padded sum s to the list u.

←Ｅ⮌τ⮌ι


Rotate the list t by 180° and print it up-side down, thus right-justifying it.

Ｍ⌈ＥυＬιＬυ←Ｅ⮌υ⮌ι


Move the cursor so that when u is right-justified its top left corner lines up with the top-right corner we just reached, and print u right-justified.

• Amazing work. You have the lead so far, @Neil. Where can I find out more about the language, is there a link? Sep 11, 2017 at 8:34
– Neil
Sep 11, 2017 at 8:56

# Python 2, 203202187 133 bytes

a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=[0,b][a%2];a/=2;b*=2
print'%10s==\n%11s'%(''.rjust(len(s),'='),s)


Try it online!

If I can use * for string multiplication ('='*R) and as a 'selector' (b*(a%2) instead of [0,b][a%2]), I get:

## 118 bytes

a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=a%2*b;a/=2;b*=2
print'%10s==\n%11s'%('='*len(s),s)


Try it online!

## Explanation:

a,b=input()                   #Get input
L=len(a)                    #Get length of first number for adjusting text
l=[]                          #Output list
s=0                           #Sum
while a:
B=['[%d]',' %d '][a%2]%b     #B is either '[b]' or ' b ' depending on if a is odd/even
l+=[(a,B)]                 #Add a,B to output list
s+=[0,b][a%2]                #Add b to sum if a is odd
a/=2;                        #Halve a
b*=2;                        #Double b
R=len(B)                      #Length of last B for adjusting output
l+=[('',''.rjust(R,'='))]     #Add double line ==== to output list
l+=[('','%d '%s)]             #Add sum to output list
for x,y in l:

• 189 bytes Sep 8, 2017 at 8:50

# Java (OpenJDK 8), 353316267214 210 bytes

(a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");}


Try it online!

• 214 bytes: (a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":" "+b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");} Sep 8, 2017 at 11:20
• @Nevay a%2*b nice and simple, thank you Sep 8, 2017 at 11:35

# Mathematica, 264 bytes

(s=#;k=(i=IntegerLength)@s;t=#2;w=0;P=Print;T=Table;While[s>0,If[OddQ@s,P[""<>T[" ",k-i@s],s,"  ",""<>T[" ",i[s(t)]-i@t],t];w=w+t,P[""<>T[" ",k-i@s],s,""<>T[" ",i[s(t)]-i@t]," [",t,"]"]];s=Quotient[s,2];t=2t];P[" "<>T[" ",k],""<>T["=",i@w+2]];P["  "<>T[" ",k],w])&


input

[19,427]

output

19   427
9   854
4 
2 
1  6832
======
8113

• You could probably save a whopping one byte by using infix notation on s=Quotient[s,2] :) Oct 11, 2017 at 11:09

# Perl 5, 157 bytes

155 bytes of code + 2 command line flags (-nl)

$\=<>;$w=y///c;$y=2+length$\<<((log)/log 2);while($_){$s+=$\if$_%2;printf"%${w}s %${y}s\n",$_,$_%2?$\.$":"[$\]";$_>>=1;$\<<=1}say$"x++$w,'='x$y;say$"x++$w,$s  Try it online! # JavaScript 2017, 221 bytes Mostly a problem of output formatting (a,b)=>{for(t=b,r=0,l=[],w=${a}.length;a;l.push([a,t]),a>>=1,t+=t)z=${r+=a&1&&t}.length+2;P=(s,w)=>${s}.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':[${b}],z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join }  Less golfed (a, b) => { var w=${a}.length, r=0, l=[]
while(a) {
r += a&1 && b
l.push([a,b])
a >>= 1
b += b
}
// algo complete, result in r, now display it and the steps in l[]
var z=${r}.length+2 var P= (s,w) => ${s}.padStart(w)
return [... l.map( ([a,b]) => P(a,w) + P(a&1?b+' ' : [${b}], z+1) ) , P('='.repeat(z), z+w+1) , P(r, z+w) ].join\n }  Test var F= (a,b)=>{for(t=b,r=0,l=[],w=${a}.length;a;l.push([a,t]),a>>=1,t+=t)z=${r+=a&1&&t}.length+2;P=(s,w)=>${s}.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':[{b}],z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join } function update(){ var i=I.value, [a,b]=i.match(/\d+/g) O.textContent=F(+a,+b) } update() <input id=I value='21x348' oninput='update()'><pre id=O></pre> • just revisiting this question... what's padStart do exactly? I don't recognize this method... Aug 16, 2019 at 1:28 • Aug 24, 2019 at 12:17 • Would suck to be running this in IE! ;) Aug 24, 2019 at 15:04 ## C, C++, 319313301 299 bytes -8 bytes thanks to Zacharý Great thanks to printf magic i just learnt in 60 minutes between the edits #include<string.h> #include<stdio.h> #define O printf("%*d %c%*d%c\n",5,a,a%2?32:91,9,b,a%2?32:93); void m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t,p;memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);memset(p,61,strlen(t)+2);printf("%*c%*s\n%*d",5,32,12,p,16,r);}  ### C++ optimization, replace header stdio.h by cstdio and string.h by cstring, saves 2 byte Compilation with MSVC requires to add #pragma warning(disable:4996) in order to use sprintf Testing with my PPCG ID : 72 x 535 =>  72 [ 535] 36 [ 1070] 18 [ 2140] 9 4280 4 [ 8560] 2 [ 17120] 1 34240 ======= 38520  It respects the rules, digit are aligned, and the equal signs will always be 2 char larger than the final number. Example with 17 x 34 =>  17 34 8 [ 68] 4 [ 136] 2 [ 272] 1 544 ===== 578  • I think you can change the last two lines to #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']'); and void m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t,p;memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);for(;i<strlen(t)+2;++i)p[i]='=';printf("%*c%*s\n%*d",5,' ',12,p,16,r);} Sep 9, 2017 at 14:01 • Yeah, I know that, but why does that matter?. Ad also, the precedence of % and * are the same, so r+=a%2*b should work. Sep 9, 2017 at 14:53 • @Zacharý in fact, i was wrong, you're right Sep 9, 2017 at 15:04 • Do you even need to include <cstdio>, can't you use the same trick you did here? Oct 5, 2017 at 16:50 • 240 bytes Nov 21, 2019 at 3:23 # [Bash], 144142140131 128 bytes Better respect of display, note there is a trailing space character read a b;for((;a;));{ ((a%2))&&((r+=b))&&x=b\ ||x=[$b];printf %3s%9s\\n$a "$x" ((a/=2,b+=b));};printf %12s\\n =${r//?/=}= $r\  First answer read a b;while((a));do ((a%2))&&((r+=b))&&printf "%6s %6s "$a $b||printf "%6s [%6s] "$a $b;((a/=2,b+=b));done;printf "%6s %7s " \ ==== \$r


i=iterate
s=show
l=length.s
a!b=zip((takeWhile(>0).i(div2))a)(i(*2)b)
a?b=sum[y|(x,y)<-a!b,rem x 2>0]
a%b=l(snd.last$a!b) a#b=unlines$[(' '<$[1..l a-l x])++s x++(' '<$[-1..a%b-l y])++if mod x 2<1then show[y]else(' ':s y)|(x,y)<-a!b]++map((++)(' '<$[-1..l a+a%b-l(a?b)]))['='<$[1..l a+1+a%b],' ':(s\$a?b)]


Try it online!

The ! operator creates the two lists, ? computes the product. % and # are used for the ascii layout.

# C, 205201190183156150 143 bytes

This will compile with warnings as C89, & I don't believe it's valid C99, but it ends up being smaller than HatsuPointerKun's version, as it saves bytes by ommitting #include's, not using dynamic lengths to printf as they're unneeded, & using log10() to calculate the number of ='s needed:

r;m(a,b){r=0;while(a){printf(a%2?"%4d%10d\n":"%4d [%8d]\n",a,b);r+=a%2?b:0;a/=2;b<<=1;}printf("%15.*s\n%14d",(int)log10(r)+3,"==========",r);}


As my number is 64586, I used this test program to calculate 64 * 586:

#include <stdio.h>
int m(int a, int b);
int main(void)
{
m(64, 586);
putchar('\n');
}


& it outputs:

  64 [     586]
32 [    1172]
16 [    2344]
8 [    4688]
4 [    9376]
2 [   18752]
1     37504
=======
37504


### edit

saved 4 bytes by the "implicit int" rule

### edit 2

saved 11 bytes by changing to a do...while() loop & moving the printf into the loop from a macro. Also should work correctly if a=1.

### edit 3

saved 7 bytes & made the code work right.

### edit 4

Saved 26 bytes with some printf trickery.

### edit 5

saved 6 bytes by collapsing extra padding into 1 number.

### edit 6

saved 7 bytes by printf trickery with the ternary operator & not declaring an unused variable

• Great work, Justin! Look forward to seeing more from you in the weeks to come! Jun 6, 2018 at 21:15
• Thank you. I hope to do more in the weeks to come, too. Jun 7, 2018 at 14:19

# Excel VBA, 183 172 bytes

An anonymous VBE immediate window function that takes input from range [A1:B1] and outputs to the console.

a=[A1]:b=[B1]:k="     ":While a:c=a Mod 2:?Right(k &a,2)Right(k &IIf(c,b &" ","["&b &"]"),7):s=s+IIf(c,b,0):a=a\2:b=b*2:Wend:?Right(k &String(Len(s)+2,61),9):?Right(k &s,9)


## Ungolfed

Sub EthiopianMultiply(ByVal a As Integer, b As Integer)
Const k As String = "     "
While a
Let c = a Mod 2
Debug.Print Right(k & a, 2);
Debug.Print Right(k & IIf(c, b & " ", "[" & b & "]"), 7)
Let s = s + IIf(c, b, 0)
Let a = a \ 2
Let b = Int(b * 2)
Wend
Debug.Print Right(k & String(Len(s) + 2, 61), 9)
Debug.Print Right(k & s, 9)
End Sub


## Output

61   486
30  
15  1944
7  3888
3  7776
1 15552
=======
29646


# Excel, 201 Bytes

An anonymous worksheet function that takes no input and outputs as plain text to the calling cell. Output is best viewed with word wrapping, a wide column width, and a monospace font on the calling cell.

Functions for all inputs such that $$\(A<10^5)\land(B*2^{\lceil Log_2 A\rceil}<10^7)\$$.

### Golfed

=Let(s,"            ",z,2^Sequence(Log(A1,2)+1,,0),a,Int(A1/z),b,B1*z,c,Sum(IsOdd(a)*b),TextJoin("
",,Right(s&a,4)&Right(s&If(IsOdd(a),b&" ","["&b&"]"),8),Right(s&Rept("=",Len(c)+2),12),Right(s&c,11)))


### Commented

=Let(s,"          ",                   ' Define var block, hold 10 spaces in s
z,2^Sequence(Log(A1,2)+1,,0),      ' z=array of powers of 2
a,Int(A1/z),                       ' a=⌊Input 1/z⌋            - left array
b,B1*z,                            ' b=B1*2^{0...⌈log2(A1)⌉}  - ~right array
c,Sum(IsOdd(A)*B),                 ' c=∑(If a(i)Is Odd b(i)) - Sum
TextJoin("\n",,                    ' concat w. \n delimiter from below:
Right(s&a,4)&	               ' a value, padded to 4 chars concat with
If(IsOdd(a),b&" "," ["&b&"]")'     b value, wrapped in [] if a val is even
Right(s&   ...,8),             '   padded to 8 chars
Right(s&Rept("=",Len(c)+2),12),  ' the = line
Right(s&c,11)))		       ' the sum


# Output 