[F#] 約log2n回の再帰呼び出しでべき乗(累乗)を計算する

29の場合は、次のように表すことができる



これを下から上へ辿ると



内側から計算すると
n が偶数のときには以下が成り立つ (res : 計算結果)



n が奇数のときには以下が成り立つ 



n=9 を２進数で表すと

1001

２進数の場合は、最下位ビットが1だと奇数なので、それを調べて処理分けしています。

let pow7 (x:bignum) n =
  let rec poww d = 
    if d = 1 then
      x
    else
      let res = poww (d >>> 1) in
      if (d &&& 1) = 0 then
        (res * res)
      else
        (res * res * x)
  in
  poww n
実行結果：
> pow7 2N 9;;
val it : bignum = 512N