ダブリング

[アルゴリズム]

ダブリング

ダブリング(Doubling?)で検索しても、いい資料が出てこない。TODO：蟻本でダブリングの章を読む

• KAHN Academy - Fast modular exponentiation

  アルゴリズム

• 以下のような構造があるとする

• サイズ n の配列 T

愚直な方法

• 配列の指す先は以下のように求められる

• １回ループ

• ２回ループ

• Rubyでやってみる

T = [0, 1, 2, 3, 4].shuffle
puts T.to_s
N = 3

puts "...itarate suffix of array indices"
T1  = T[N]
puts "T1 = T[N] (#{T[N]})"
T2  = T[T[N]]
puts "T2 = T[T[N]] (#{T[T[N]]})"
T3  = T[T[T[N]]]
puts "T3 = T[T[T[N]]] (#{T[T[T[N]]]})"
T4  = T[T[T[T[N]]]]
puts "T4 = T[T[T[T[N]]]] (#{T[T[T[T[N]]]]})"

• 出力
  • 当然ちゃんと行き先がわかる

[3, 1, 0, 2, 4]
...itarate suffix of array indices
T1 = T[N] (2)
T2 = T[T[N]] (0)
T3 = T[T[T[N]]] (3)
T4 = T[T[T[T[N]]]] (2)

ダブリング

• 累乗したやつは同じになるやろ！という話。ほんとか？

• Rubyでやってみる

T = [3, 1, 0, 2, 4]

def doubling(array, n)
    src = array.dup
    dst = (0...array.length).to_a
    
    0.upto(n) do
        for e in dst.dup
            dst[src[e]] = e
        end
    end
    dst
end

T1 = doubling(T,1)
T2 = doubling(T,2)
T4 = doubling(T2,1)