A test to compare the run-times of the Karatsuba Multiplication Algorithm and the Third Grade Multiplication Algorithm

karatsuba_vs_third_grade.rb

def karatsuba x, y
  return x * y if (x < 10) || (y < 10)
  n = [x.to_s.size, y.to_s.size].max
  n2 = n/2
 
  a, b = x.divmod(10**n2)
  c, d = y.divmod(10**n2)
 
  step_1 = karatsuba(a,c)
  step_2 = karatsuba(b,d)
  step_3 = karatsuba((a+b),(c+d))
  (step_1*10**(2*n2))+((step_3-step_1-step_2)*10**(n2))+(step_2)
end
 
def third_grade x, y
  x = to_digits x
  y = to_digits y
  results = []

  x.size.times do |x_index|
    y.size.times do |y_index|
      product = y[y.size - 1 - y_index] * x[x.size - 1 - x_index]
      num_zeros = 10**(y_index+x_index)
      results << product * num_zeros
    end
  end

  results.reduce(:+)
end

def to_digits num
  num.to_s.chars.map(&:to_i)
end

def benchmark iterations, description
  start = Time.now
  iterations.times do
    yield
  end
  p "#{description}: #{Time.now - start} seconds"
end

one_hundred_twenty_eight_digit_num = [*2..69].map(&:to_s).join.to_i
sixty_four_digit_num = [*2..37].map(&:to_s).join.to_i

tests_params = [
  [2, 2],
  [12, 12],
  [1234, 1234],
  [12341234, 12341234],
  [1234123412341234, 1234123412341234],
  [12341234123412341234123412341234, 12341234123412341234123412341234],
  [sixty_four_digit_num, sixty_four_digit_num],
  [one_hundred_twenty_eight_digit_num, one_hundred_twenty_eight_digit_num]
]

tests_params.each do |x, y|
  benchmark 100, "karatsuba #{x.to_s.size + y.to_s.size} digits" do
    karatsuba x, y
  end
end

tests_params.each do |x, y|
  benchmark 100, "third_grade #{x.to_s.size + y.to_s.size} digits" do
    third_grade x, y
  end
end