Ethiopian Multiplication

Question

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.

The Task:

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"!)

Answer 1

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.

Answer 2

Python 2, 203 202 187 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:
 print x.rjust(L),y.rjust(R)  #Print adjusted numbers

Answer 3

Java (OpenJDK 8), 353 316 267 214 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!

Answer 4

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  

Answer 5

[Bash], 144 142 140 131 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

Answer 6

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!

Answer 7

C, C++, 319 313 301 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

Answer 8

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>

Answer 9

Haskell, 305 bytes

i=iterate
s=show
l=length.s
a!b=zip((takeWhile(>0).i(`div`2))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.

Answer 10

C, 205 201 190 183 156 150 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

Answer 11

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