Skew Binary Numbers - komamitsu.log

先日、osiireさんにSkew Binary Random-Access Listsというのを紹介して頂いたので、http://www.cs.cmu.edu/~rwh/theses/okasaki.pdfを眺めていた。
これはSkew Binary Numbersというのに基づいているらしいので、まずそっちを見てみることに。いずれも初耳。

以下、Skew Binary Numbersとは…について自分の整理もかねてメモ

まず、お馴染みの十進数では、k桁目が $10^k$ との掛け算で表現できる。
$1(10^3) + 2(10^2) + 3(10^1) + 4(10^0) = 1234$

二進数だと $2^k$ との掛け算。
$1(2^2) + 0(2^1) + 1(2^0) = 0b101 = 5$

そして、Skew Binary Numbersでは $2^{k+1} - 1$ との掛け算になる。
$1(2^{5+1} - 1) + 0(2^{4+1} - 1) + 1(2^{3+1} - 1) + 2(2^{2+1} - 1) + 0(2^{1+1} - 1) + 0(2^{0+1} - 1) = 1(63) + 1(15) + 2(7) = 92$

上記例の場合、前述のpdfだと002101(least-significant digit first)という表記法になっていたけれど、http://online-judge.uva.es/p/v5/575.htmlとかだと101200的になっていて、個人的には後者がわかりやすいので以降そんな感じで。

で、Skew表記の101200というのは、7, 7, 15, 63の合計値なのでOCamlのListっぽく書くと[7;7;15;13]とも表現できる。

十進数の11(Skewで111)だと $1(2^{2+1} - 1) + 1(2^{1+1} - 1) + 1(2^{0+1} - 1) = 1(7) + 1(3) + 1(1) = 11$ で、[1;3;7]。

十進数の13(Skewで120)だと $1(2^{2+1} - 1) + 2(2^{1+1} - 1) + 0(2^{0+1} - 1) = 1(7) + 2(3) = 13$ で、[3;3;7]。

このようにしておくと、Listの先頭二値を比較するだけで、Skew表記における最小のnon-0値が2であるか判断できてうれしいらしい。
上記例の十進数の11では、1と3で一致しないのでSkew表記における最小のnon-0値は2以外。
十進数の13では、共に3で一致するのでSkew表記における最小のnon-0値は2。

てなことを利用したIncrement, Decrimentの処理がStandard MLのコードで書いてあったので、OCamlに書き直してみた。

open Printf

let inc = function
  | ws as w1::w2::rest when w1 = w2 -> (1 + w1 + w2)::rest
  | ws -> 1::ws

let dec = function
  | 1::rest -> rest
  | w::rest -> (w / 2)::(w / 2)::rest
  | _ -> failwith "It can't decrease any more."

let print_list l =
  let sum = List.fold_left (fun a b -> a + b) 0 l in
  printf "%04d: " sum;
  List.iter (fun x -> printf "%d " x) l;
  print_newline ();
  l

let _ =
  let rec loop n f l =
    if n <= 0 then (print_list l)
    else (
      print_list l;
      loop (n - 1) f (f l)
    )
  in
  let len = 20 in
  print_endline "=== Inc ===";
  let l = loop len inc [] in
  print_endline "=== Dec ===";
  loop len dec l

incでは、
Listの最小の二値を比較して同値であれば、Skew表記における最小のnon-0は2と判断し「二値 <=> 二値の合計値+1」を交換して繰り上がり（[3;3;7] => [7;7], Skew表記: 120 => 200）。
それ以外の場合、繰り上がりがないので1を足すだけ（[1;3;7] => [1;1;3;7], Skew表記: 111 => 112）。

decでは、
Listに1が含まれている場合は繰り下がりが無いので当該の1を外すのみ（[1;3;7] => [3;7], Skew表記: 111 => 110）。
それ以外の場合、「Skew表記における最小のnon-0値 <=>その値を2で割った値二つ」を交換し繰り下がり（[3;3;7] => [1;1;3;7], Skew表記: 120 => 112）。
こちらは、List中の全ての値が奇数なので2で割って足し合わせると1減っていることを利用している。

繰り上がり、繰り下がりにも負けず、inc, decともに計算量がO(1)というところがキモみたい。