Ruby で 1 行繰り返し二乗法

はじめに

短いコードを書くと可読性が著しく低下する．自分が楽しむ目的でのみコードを縮めて遊ぶこと．他人に迷惑をかけないように．

繰り返し二乗法とは

累乗計算を愚直に行うとコストがかかる．その問題を解決する方法に，繰り返し二乗法と呼ばれるアルゴリズムがある．

例えば $2^{100}$ は $2^{100} = (2^{50})^2 = ((2^{25})^2)^2...$ としていくことで，計算コストを落とすことができる．奇数乗の場合は $1$ 乗と残りに分ける．この処理を再帰的に行うことで，規模の大きな累乗を非常に少ない時間で計算することができる．

これを一般化すると，$a^{b}$ を求める関数は次のようになる．

Function(x, y)
  If b == 0
    Return 1
  Else if b == 1
    Return a
  Else if b % 2 == 1
    Return a * Function(a, b - 1)
  Else
    c = Function(a, b / 2)
    Return c * c

Ruby で書いてみた

そこそこ記述量が少なくて済む Ruby (インタプリタ言語の中ではそれほどでもないが) で試したら 1 行で書くことができた．

def f(a,b) return eval([%w|1 a|,%w|f(a,b/2)**2 a*f(a,b-1)|][[b/2,1].min][b%2]) end

先のアルゴリズムを次にように言い換える．

Function(x, y)
  If b < 2
    If b % 2 == 0   // b == 0
      Return 1
    Else   // b % 2 == 1
      Return a   // b == 1
  Else   // b >= 2
    If b % 2 == 0
      c = Function(a, b / 2)
      Return c * c
    Else    // b % 2 == 1
      Return a * Function(a, b - 1)

b が 2 以下であるか否かと，b が偶数か奇数かで処理を 4 通りに場合分けする．

Ruby は %w|a b c| と書くと，スペースで区切られた文字列を要素とする配列 ["a", "b", "c"] を生成する．よって eval の中身は [["1", "a"], ["f(a,b/2)**2", "a*f(a,b-1)"]] と等価である．この 2 次元配列を A とする．

A の 1 個目の添字 [b/2,1].min は b を 2 で割った商と 1 のうちより小さい数を返すので，b が 1 以下であれば 0，そうでなければ 1 を得る．A の 2 個目の添字 b%2 は b が偶数なら 0，奇数なら 1 を返す．

これらの添字により選択される A の要素は先述のアルゴリズムで return する式を書いた文字列に等しい．eval は引数として渡された文字列をプログラムとして実行した結果を返すので，関数 f(a,b) は計算結果である数値を返す．eval 様々．

ちなみに累乗の計算は結果が非常に大きくなるので，素数で割った余りを計算することもある．その場合は次のようにする．ただし，r は大きな素数 ($10^9+7$ など) とする．

Function(x, y, r)
  If b == 0
    Return 1
  Else if b == 1
    Return a % r
  Else if b % 2 == 1
    Return (a * Function(a, b - 1)) % r
  Else
    c = Function(a, b / 2)
    Return (c * c) % r

def f(a,b,r) return eval([%w|1 a%r|,%w|f(a,b/2,r)**2%r a*f(a,b-1,r)%r|][[b/2,1].min][b%2]) end

おわりに

ちなみに Ruby にはデフォルトで累乗計算が備わっているので，わざわざこの関数を定義する意味はない．

irb(main):001:0> 2 ** 31
=> 2147483648