Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Egyptian multiplication

Original Problem

Goal

You have to multiply two integers (a&b) by means of a method used in Ancien Egypt, described in Rhind’s hieratic papyrus written circa −1650 by Ahmes. This method is still used in Russia.

First, sort the two numbers.
Then follow the steps below, the algorithm uses base-2 decomposition of the biggest number.
We multiply 12 by 5, here is what you have to print, excepted the comments after hashes.

12 * 5
= 12 * 4 + 12 # Divide 5 by 2, the remain is 1 and 5=2×2+1, thus 12*5=12*(2*2+1)=12*2*2+12=24*2+12
= 24 * 2 + 12 # Divide 2 by 2, 2=1*2+0 and 12*5=24*(1*2+0)+12=48*1+12
= 48 * 1 + 12 # Divide 1 by 2, 1=0*2+1 and 12*5=48*(0*2+1)+12=12+48
= 48 * 0 + 12 + 48 # End of the algorithm
= 60
Input
Two integers separated by a space.
Output
The description of the successive operations.
Constraints
0<= a, b <= 32768

Solution

When we observe the output, the first line is simply the sorted input printed out, separated by a multiplication sign. After that intermediate steps are printed in the form of a times b and the already found summands. These intermediate steps have two different formats. When b is odd it is printed with an additional a summand and if it is even, only a and b get doubled or halved. When we modify a and b in every iteration, we need two printing lines and additional zero-checks. Or we use only the main loop as zero check. This way the whole algorithm can be implemented pretty short:

a, b = gets.split.map(&:to_i)

if a < b
  a, b = b, a
end

puts "#{a} * #{b}"

r = ""
s = 0

while b > 0

  if b.odd?
    r+= " + #{a}"
    s+= a
    b-= 1
  else
    a*= 2
    b/= 2 
  end

  puts "= #{a} * #{b}#{r}"
end
puts "= #{s}"

« Back to problem overview