Adding trick

multiply-with-add.rb

# Limitations:
# 1. Only math allowed is addition.
# 2. No Ruby API calls.
# 3. Inputs are natural numbers.

require 'benchmark'

def min_max(a, b)
  smaller = a
  larger = b
  if smaller > larger
    temp = smaller
    smaller = larger
    larger = temp
  end

  [smaller, larger]
end

def multiply_dumb(a, b)
  smaller, larger = min_max(a, b)

  muls = smaller
  product = 0
  while muls > 0 do
    product = product + larger
    muls = muls + (-1)
  end

  product
end

def multiply_fancy(a, b)
  smaller, larger = min_max(a, b)

  return 0 if smaller == 0
  return larger if smaller == 1

  last_probe = 0
  probe = 2
  product = larger
  while probe <= smaller
    product = product + product
    last_probe = probe
    probe = probe + probe
  end
  probe = last_probe
  product = 0 if probe == 0

  return product + multiply_fancy(smaller - probe, larger)
end

def benchmark
  inputs = [
    [5, 10],
    [5000, 1000],
    [2, 2],
    [0, 10],
    [1, 123],
    [10 ** 7, 10 ** 7],
    [10 ** 9, 10 ** 9],
  ]

  inputs.each do |a, b|
    print "multiply_dumb(#{a}, #{b}) = "
    puts Benchmark.measure { puts multiply_dumb(a, b) }
  end

  inputs.each do |a, b|
    print "multiply_fancy(#{a}, #{b}) = "
    puts Benchmark.measure { puts multiply_fancy(a, b) }
  end
end

#puts multiply_fancy(1000, 1600)

benchmark