【プログラミング】末尾再帰を使って累乗（バイナリ法）を実装する【Kotlin】

Kotlin プログラミング

wrongwrong163377.hatenablog.com
続きです。
ネット上のループや通常の再帰を使った実装に比べ、末尾再帰で書いた方がシンプルにバイナリ法を実装できました。

バイナリ法とは

a^nを a^{2^x}を掛け合わせた形に変形することで乗算回数を抑えるアルゴリズムです。 nが整数の時のみ適用できます。
例えば \displaystyle n = 4 = 100{\rm b}*1とした場合、 a^nは以下のように変形できます。
\displaystyle \begin{align} a^4 &= a^{2^2 \times {\rm flag}_3} \times a^{2^1 \times {\rm flag}_2} \times a^{2^0 \times {\rm flag}_1} \\ &= a^{4 \times {\rm flag}_3} \times a^{2 \times {\rm flag}_2} \times a^{{\rm flag}_1} \end{align}
ここで、 \displaystyle {\rm flag}は \displaystyle nのビットを示しており、 \displaystyle {\rm flag}_3 = 1, {\rm flag}_2 = 0, {\rm flag}_1 = 0です。
つまり上式は以下のようになります。
\displaystyle \begin{align} a^4 &= a^{4 \times {\rm flag}_3} \times a^{2 \times {\rm flag}_2} \times a^{{\rm flag}_1} \\ &= a^4 \times a^0 \times a^0 \end{align}

実装

このアルゴリズムをKotlinで実装したものが以下です。
コメントを書きたかったので改行を挟んでいますが、実質4行で関数全体が実装できています。

tailrec fun pow(a: BigInteger, n: Int, ans: BigInteger = BigInteger.ONE): BigInteger{
    if(n == 0) return ans
    return pow(
        a * a, //a^2^xを作っておく
        n.ushr(1), //nを右ビットシフトして一番下の桁をずらしていく、符号は無視
        if(n.and(1) == 1) ans * a else ans //nの最終ビットが1なら掛け、それ以外は無視する
    )
}

おまけ

バイナリ法無しの計算をpow_nとしてループを使って実装し、以下の状態で動かしてみました。

import java.math.BigInteger
import kotlin.system.measureTimeMillis

//累乗（バイナリ法）
tailrec fun pow(a: BigInteger, n: Int, ans: BigInteger = BigInteger.ONE): BigInteger{
    if(n == 0) return ans
    return pow(a * a,  n.ushr(1),  if(n.and(1) == 1) ans * a else ans)
}

//通常ループ
fun pow_n(a: BigInteger, n: Int): BigInteger{
    var ans = BigInteger.ONE
    for(i in 1..n){ ans *= a }
    return ans
}

fun main(args: Array<String>) {
    for(i in 0..100000 step 10000){
        val time1 = measureTimeMillis{
            pow(BigInteger("17"), i)
        }
        val time2 =  measureTimeMillis{
            pow_n(BigInteger("17"), i)
        }
        println("$i,$time1,$time2")
    }
}
実行結果

17^{100000}とかまでいくとすごい差が付きますね。
f:id:wrongwrongwrongwrong163377:20181210064747p:plain

続き

wrongwrong163377.hatenablog.com

*1:100bは2進数表記