karatsuba.rb

# Multiplies two n-length integers using recursively the Karatsuba altorithm
class Karatsuba
  
  def initialize
  
  end  

  def self.karatsuba(x, y)
    return x * y if (x < 10) || (y < 10)
    n = [x.to_s.size, y.to_s.size].max
    n2 = n/2    
  
    # Initial values
    a, b = x.divmod(10**n2)
    c, d = y.divmod(10**n2)
    
    # Terms used on the algorithm computation
    t1 = karatsuba a, c
    t2 = karatsuba b, d
    t3 = karatsuba((a+b), (c+d)) -  t1 - t2
    
    (t1*10**(2*n2))+(t3*10**n2)+(t2)

  end
  
end

puts 'We will multiply two numbers karatsuba-way'
puts 'What is the first number?'
x = gets.to_i
puts 'What is the second number?'
y = gets.to_i

product = Karatsuba.karatsuba(x, y)
puts "#{x} . #{y} = #{product}"