karatsuba

gistfile1.rb

class Karatsuba
  attr_reader :ab, :cd, :result, :right_result, :multipliers

  def right?
    @right_result == @result
  end

private
  def initialize ab, cd, right_result
    @right_result = right_result
    @ab           = ab
    @cd           = cd
    @multipliers  = {}

    @result       = multiplicate ab, cd
  end

  def multiplicate ab, cd
    if ab.length == 1 && cd.length == 1
      ab.to_i * cd.to_i
    else
      maxLen  = ab.length > cd.length ? ab.length : cd.length
      maxLen  = closest_2_pow maxLen

      while ab.length < maxLen
        ab = "0" + ab
      end

      while cd.length < maxLen
        cd = "0" + cd
      end

      a, b = split_even_by_half ab
      c, d = split_even_by_half cd

      ac = multiplicate a, c
      bd = multiplicate b, d

      apb_cpd = multiplicate (a.to_i + b.to_i).to_s, (c.to_i + d.to_i).to_s 

      multiplier = apb_cpd - ac - bd

      add_multiplier multiplier

      (10**maxLen) * ac + (10**(maxLen/2)) * multiplier + bd
    end
  end

  def split_even_by_half num
    n         = num.length
    boundary  = (n / 2).to_i
    [num.slice(0, boundary), num.slice(boundary, n)]
  end

  def add_multiplier multiplier
    if @multipliers[multiplier].nil?
      @multipliers[multiplier] = 1
    else
      @multipliers[multiplier] += 1
    end
  end

  def closest_2_pow num
    pow = 1
    while pow < num
      pow = pow*2
    end

    pow
  end
end

v1 = Karatsuba.new("1685287499328328297814655639278583667919355849391453456921116729", "7114192848577754587969744626558571536728983167954552999895348492", 11989460275519080564894036768322865785999566885539505969749975204962718118914971586072960191064507745920086993438529097266122668)

p v1.multipliers[105]
p v1.multipliers[72]
p v1.multipliers[12]

p v1.right?