# 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   [68]
4  [136]
2  [272]
1   544


Sum the remaining numbers in the right-hand column:

17    34
8   [68]
4  [136]
2  [272]
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 [1708]
2 [3416]
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  [555]
4 [1110]
2 [2220]
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 '17 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. – Arnauld Sep 8 '17 at 7:49
• As noted in the sandbox, related, possible dupe. @FelixPalmen, yes, this is long multiplication in binary. – Peter Taylor Sep 8 '17 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? – WallyWest Sep 11 '17 at 8:34
• @WallyWest The title is linked to the GitHub page and from there you can read the wiki for more information. – Neil Sep 11 '17 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:


# 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+" ");} – Nevay Sep 8 '17 at 11:20
• @Nevay a%2*b nice and simple, thank you – Roberto Graham Sep 8 '17 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 [1708]
2 [3416]
1  6832
======
8113

• You could probably save a whopping one byte by using infix notation on s=Quotient[s,2] :) – numbermaniac Oct 11 '17 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... – WallyWest Aug 16 at 1:28 • – edc65 Aug 24 at 12:17 • Would suck to be running this in IE! ;) – WallyWest Aug 24 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[20],p[20];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[20],p[20];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);} – Zacharý Sep 9 '17 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. – Zacharý Sep 9 '17 at 14:53 • @Zacharý in fact, i was wrong, you're right – HatsuPointerKun Sep 9 '17 at 15:04 • Do you even need to include <cstdio>, can't you use the same trick you did here? – Zacharý Oct 5 '17 at 16:50 # [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! – WallyWest Jun 6 '18 at 21:15
• Thank you. I hope to do more in the weeks to come, too. – JustinCB Jun 7 '18 at 14:19

# Excel VBA, 183 bytes

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

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


## Ungolfed

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


## Output

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