sideways addition

アルゴリズムを読んでいると, 簡単なものでも, あれ? と思うのがたまにある.

ビット列のsideways additionというのは, 1のビットの数である.
(1 0 1 0 1 0 1 0 1) なら5である. (Henry WarrenのHacker's Delightではpopulation countという.) あるいは∑x_i (x_iは0または1) といってもよい.



またまたTAOCPの話題で恐縮だが, x₁, x₂, ..., x₉の9ビットのsideways additionが次のように書いてあった.

x₁₀=x₁⊕x₂⊕x₃,  x₁₁=x₄⊕x₅⊕x₆,  x₁₂=x₇⊕x₈⊕x₉,  x₁₃=x₁₀⊕x₁₁⊕x₁₂,
y₁=⟨x₁x₂x₃⟩,  y₂=⟨x₄x₅x₆⟩,  y₃=⟨x₇x₈x₉⟩,  y₄=⟨x₁₀x₁₁x₁₂⟩

とすると

x₁+…+x₉=x₁₃+2(y₁+y₂+y₃+y₄)

で得られる. x⊕y はxとyの排他的論理和; ⟨xyz⟩はx,y,zの多数決(TAOCPではmedianという)を表わす. x⊕y⊕zと⟨xyz⟩で全加算器になる.

非常に美しい式だが, 本当かとも思い, 早速やってみる.

(define base 10)
(define (sidewayadd xs)
 (define (xor a b c) (modulo (+ a b c) 2))
 (define (med a b c) (quotient (+ a b c) 2))
 (let* ((x1 (modulo (quotient xs (expt base 0)) base))
        (x2 (modulo (quotient xs (expt base 1)) base))
        (x3 (modulo (quotient xs (expt base 2)) base))
        (x4 (modulo (quotient xs (expt base 3)) base))
        (x5 (modulo (quotient xs (expt base 4)) base))
        (x6 (modulo (quotient xs (expt base 5)) base))
        (x7 (modulo (quotient xs (expt base 6)) base))
        (x8 (modulo (quotient xs (expt base 7)) base))
        (x9 (modulo (quotient xs (expt base 8)) base))
        (x10 (xor x1 x2 x3)) (x11 (xor x4 x5 x6))
        (x12 (xor x7 x8 x9)) (x13 (xor x10 x11 x12))
        (y1 (med x1 x2 x3)) (y2 (med x4 x5 x6))
        (y3 (med x7 x8 x9)) (y4 (med x10 x11 x12)))
  (+ x13 (* 2 (+ y1 y2 y3 y4)))))
(sidewayadd 000000111) => 3                                                     
(sidewayadd 111000111) => 6

なるほど. letの中の, 割ったり剰余をとったりしてx1, x2,...を作っているのは, (sidewayadd '(1 1 1 0 0 0 1 1 1))と書くのは面倒なので, (sidewayadd 111000111)としたいからである.

しかし落ち着いて考えてみると, アルゴリズムが正しいことは簡単に分かる.



この図のように9ビットを右からx₁,...,x₉とする. 3ビットずつに区切り, その区間の和を求めると0から3までになるから, 2ビットで表現出来, それが下のx₁₀,y₁などである. x₁,x₂,x₃の3ビットの二進法の和は, その1の桁(x₁₀)はx₁,x₂,x₃の排他的論理和だし, 10の桁(y₁)はそれらの多数決だから, アルゴリズムにはそう書いてある. 次に3つの区間の3ビットの和が得られたとして, この和を取るわけだが, 和の1の桁はx₁₀,x₁₁,x₁₂の排他的論理和である. 10の桁y₁,y₂,y₃を足せばよく, それにx₁₀,x₁₁,x₁₂からの繰上がり, すなわちそれらの多数決を足す. 10の桁だから2倍する.

と書いてしまえば, 当然なアルゴリズムであった.

この話題では, 思い出すことが2つある. 1つは英国ケンブリッジ大学のEDSACのライブラリのsideways additionで, 第2版に登場した.

EDSACの語長は35ビットだが, 36ビットと考えて6ビットの区間６つとする. ビットシフトやビット毎ANDや加算して, ６つの区間で並列にその区間の1の数を和を作る. 6までだから3ビットの範囲に収まる. つぎに10⁵10⁵...0⁵1（つまり5個の0と1が交互の列)を掛けると中央の6ビットの区間に総和が現れる仕掛けである.

この話はTAOCPのbitwise tricks and techniquesにも書いてある.

もう1つはパラメトロン計算機PC-1の語長が36ビットだったことに関係する. この36なる数は, 9ビット掛ける4なのだ. 9ビット毎にパリティをとり, エラー検出ビットを設ける計画であった. 3個のパラメトロンの信号のパリティは, 3重平衡変調器という回路で簡単に取れるはずで, それを2段用いれば9個のパリティが取れるというもくろみであった. そしてメモリーは1語当り情報36ビット, 検査用4ビット, 計40ビットで構成するはずであった. しかし3重平衡変調器が思ったほどにはうまく働かず, 結局パリティビットなしになった.

ところで, 最初の美しい式はy₄まではBoole式だが, 最後に算術演算で足している. これは反則のようにも見えるが, y₁+y₂+y₃+y₄が実は(y_iは0または1なので)再びsideways additionになり, 再帰的に回路を構成すればよい. Knuthの計算機MMIXには, 64ビットまでのオペランドのsideways addition SADDがあるが, かなりの回路になるであろう.