Ruby script to multiply big-digit values with Toom-Cook 3-way method.

multiply_toom_cook_3.rb

#! /usr/local/bin/ruby
#*********************************************
# 多倍長乗算 ( by Toom-Cook 法 (3-way) )
#   - 多倍長 * 多倍長
#   - 最下位の桁を配列の先頭とする考え方
#*********************************************
#
class MultiplyToomCook3
  D_MAX = 729  # 計算可能な最大桁数 ( 3 のべき乗 )
  D     = 729  # 実際に計算する桁数 ( D_MAX 以下 )

  def initialize
    # ====================================== #
    # テストなので、被乗数・乗数は乱数を使用 #
    # ====================================== #
    @a, @b = Array.new, Array.new
    rnd_a, rnd_b = Random.new(0), Random.new(1)
    # 被乗数・乗数設定
    0.upto(D - 1) do |i|
      @a << rnd_a.rand(10)
      @b << rnd_b.rand(10)
    end
  end

  # 計算 ( Toom-Cook 法 )
  def calc_toom_cook
    # 配列初期設定 ( コンストラクタで生成した配列を使用 )
    a, b = @a, @b  # 被乗数配列、乗数配列
    z = Array.new  # 計算結果用配列

    begin
      # 最大桁に満たない部分は 0 を設定
      (D_MAX - a.size).times { |i| a << 0 }
      (D_MAX - b.size).times { |i| b << 0 }
      # ====[ TEST ]===>
      # t1 = Time.now      # 計算開始時刻
      # 100.times do |l|  # 100 回 LOOP
      # @cnt_mul = 0       # 乗算回数リセット
      # <===[ TEST ]====
      # 乗算 ( Toom-Cook 法 (3-way) )
      z = multiply_toom_cook_3(a, b)
      # ====[ TEST ]===>
      # end
      # t2 = Time.now      # 計算終了時刻
      # @tt = t2 - t1      # 計算時間
      # <===[ TEST ]====
      # 繰り上がり処理
      z = do_carry(z)
      # 結果出力
      display(a, b, z)
    rescue => e
      raise
    end
  end

  private

  # 乗算 ( 標準(筆算)法 )
  def multiply_normal(a, b)
    # 配列サイズ取得
    a_len, b_len = a.size, b.size
    # 計算結果初期化
    z = Array.new(a_len + b_len, 0)
    # 各配列を各桁とみなして乗算
    b_len.times do |j|
      a_len.times do |i|
        z[j + i] += a[i] * b[j]
        # ====[ TEST ]===>
        # @cnt_mul += 1  # 乗算カウント
        # <===[ TEST ]====
      end
    end
    return z
  rescue => e
    raise
  end

  # 乗算 ( Toom-Cook 法 (3-way) )
  #   結果用配列は以下のように配置し、
  #     +----+----+----+----+----+----+----+----+----+----+
  #     |   c0    |   c2    |   c4    |   c1    |   c3    |
  #     +----+----+----+----+----+----+----+----+----+----+
  #   最後に、c1, c3 を所定の位置に加算する。
  #     +----+----+----+----+----+----+
  #     |   c0    |   c2    |   c4    |
  #     +----+----+----+----+----+----+
  #          +----+----+----+----+
  #          |   c1    |   c3    |
  #          +----+----+----+----+
  def multiply_toom_cook_3(a, b)
    # 各種宣言
    a_m1, a_m2      = Array.new, Array.new
    a_0, a_1, a_inf = Array.new, Array.new, Array.new
    b_m1, b_m2      = Array.new, Array.new
    b_0, b_1, b_inf = Array.new, Array.new, Array.new
    c_m1, c_m2      = Array.new, Array.new
    c_0, c_1, c_inf = Array.new, Array.new, Array.new
    c0, c1, c2      = Array.new, Array.new, Array.new
    c3, c4          = Array.new, Array.new

    begin
      # 配列サイズ取得
      t_len = a.size
      # ９桁（配列９個）になった場合は標準乗算
      return multiply_normal(a, b) if t_len <= 9
      # 配列分割
      a2 = a[(t_len * 2 / 3)..-1]
      a1 = a[(t_len / 3)..(t_len * 2 / 3 - 1)]
      a0 = a[0..(t_len / 3 - 1)]
      b2 = b[(t_len * 2 / 3)..-1]
      b1 = b[(t_len / 3)..(t_len * 2 / 3 - 1)]
      b0 = b[0..(t_len / 3 - 1)]
      # a(-2) = 4 * a2 - 2 * a1 + a0, b(1) = 4 * b2 - 2 * b1 + b0 (by シフト演算)
      (t_len / 3).times do |i|
        a_m2 << (a2[i] << 2) - (a1[i] << 1) + a0[i]
        b_m2 << (b2[i] << 2) - (b1[i] << 1) + b0[i]
      end
      # a(-1) = a2 - a1 + a0, b(1) = b2 - b1 + b0
      (t_len / 3).times do |i|
        a_m1 << a2[i] - a1[i] + a0[i]
        b_m1 << b2[i] - b1[i] + b0[i]
      end
      # a(0) = a0, b(0) = b0
      a_0, b_0 = a0, b0
      # a(1) = a2 + a1 + a0, b(1) = b2 + b1 + b0
      (t_len / 3).times do |i|
        a_1[i] = a2[i] + a1[i] + a0[i]
        b_1[i] = b2[i] + b1[i] + b0[i]
      end
      # a(inf) = a2, b(inf) = b2
      a_inf, b_inf= a2, b2
      # c(-2) = a(-2) * b(-2)
      c_m2 = multiply_toom_cook_3(a_m2, b_m2)
      # c(-1) = a(-1) * b(-1)
      c_m1 = multiply_toom_cook_3(a_m1, b_m1)
      # c(0) = a(0) * b(0)
      c_0 = multiply_toom_cook_3(a_0, b_0)
      # c(1) = a(1) * b(1)
      c_1 = multiply_toom_cook_3(a_1, b_1)
      # c(inf) = a(inf) * b(inf)
      c_inf = multiply_toom_cook_3(a_inf, b_inf)
      # c4 = 6 * c(inf) / 6
      c4 = c_inf
      # c3 = -c(-2) + 3 * c(-1) - 3 * c(0) + c(1) + 12 * c(inf) / 6
      ((t_len / 3) * 2).times do |i|
        c3[i]  = -c_m2[i]
        c3[i] += (c_m1[i] << 1) + c_m1[i]
        c3[i] -= (c_0[i] << 1) + c_0[i]
        c3[i] += c_1[i]
        c3[i] += (c_inf[i] << 3) + (c_inf[i] << 2)
        c3[i] /= 6
      end
      # c2 = 3 * c(-1) - 6 * c(0) + 3 * c(1) - 6 * c(inf) / 6
      ((t_len / 3) * 2).times do |i|
        c2[i]  = (c_m1[i] << 1) + c_m1[i]
        c2[i] -= (c_0[i] << 2) + (c_0[i] << 1)
        c2[i] += (c_1[i] << 1) + c_1[i]
        c2[i] -= (c_inf[i] << 2) + (c_inf[i] << 1)
        c2[i] /= 6
      end
      # c1 = c(-2) - 6 * c(-1) + 3 * c(0) + 2 * c(1) - 12 * c(inf) / 6
      ((t_len / 3) * 2).times do |i|
        c1[i]  = c_m2[i]
        c1[i] -= (c_m1[i] << 2) + (c_m1[i] << 1)
        c1[i] += (c_0[i] << 1) + c_0[i]
        c1[i] += (c_1[i] << 1)
        c1[i] -= (c_inf[i] << 3) + (c_inf[i] << 2)
        c1[i] /= 6
      end
      # c0 = 6 * c(0) / 6
      c0 = c_0
      #  z = c4 * x^4 + c3 * x^3 + c2 * x^2 + c1 * x + c0
      z = c0 + c2 + c4
      ((t_len / 3) * 2).times { |i| z[i + t_len / 3] += c1[i] }
      ((t_len / 3) * 2).times { |i| z[i + t_len    ] += c3[i] }
      return z
    rescue => e
      raise
    end
  end

  # 繰り上がり処理
  def do_carry(a)
    cr = 0  # 繰り上がり

    begin
      a.size.times do |i|
        a[i] += cr
        cr = a[i] / 10
        a[i] -= cr * 10
      end
      # オーバーフロー時
      puts "[ OVERFLOW!! ] #{cr}" unless cr == 0
      return a
    rescue => e
      raise
    end
  end

  # 結果出力
  def display(a, b, z)
    # 上位桁の不要な 0 を削除するために、配列サイズを取得
    len_a, len_b, len_z = D_MAX, D_MAX, D_MAX * 2
    while a[len_a - 1] == 0 do len_a -= 1 if a[len_a - 1] == 0 end
    while b[len_b - 1] == 0 do len_b -= 1 if b[len_b - 1] == 0 end
    while z[len_z - 1] == 0 do len_z -= 1 if z[len_z - 1] == 0 end
    # a 値
    puts "a ="
    (len_a - 1).downto(0) do |i|
      print a[i]
      print " " if (len_a - i) % 10 == 0
      puts if (len_a - i) % 50 == 0
    end
    puts
    # b 値
    puts "b ="
    (len_b - 1).downto(0) do |i|
      print b[i]
      print " " if (len_b - i) % 10 == 0
      puts if (len_b - i) % 50 == 0
    end
    puts
    # z 値
    puts "z ="
    (len_z - 1).downto(0) do |i|
      print z[i]
      print " " if (len_z - i) % 10 == 0
      puts if (len_z - i) % 50 == 0
    end
    puts; puts
    # ====[ TEST ]====
    # puts "Counts of multiply / 1 loop = #{@cnt_mul}"     # 乗算回数
    # puts "Total time of all loops     = #{@tt} seconds"  # 処理時間
    # ====[ TEST ]====
  rescue => e
    raise
  end
end

if __FILE__ == $0
  begin
    # 計算クラスインスタンス化
    obj = MultiplyToomCook3.new
    # 乗算 ( Toom-Cook 法 )
    obj.calc_toom_cook
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
  end
end