karatsuba multiplication

karatsuba.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


p karatsuba(12345678, 12345678) == 152415765279684
p karatsuba(1234, 5678) == 7006652
p karatsuba(12, 34) == 408
p karatsuba(1, 2) == 2
p karatsuba(123, 456) == 56088
p karatsuba(12345, 12345) == 152399025
p karatsuba(123, 345) == 42435