多倍長整数演算

レポートの２つ目の課題。
多倍長演算は結局ただの筆算なので実装は楽だろう。
でも、それじゃ自分の勉強にならないのでネタを探していた。*1
多倍長演算の実装には

ビット列を符号なし整数として保持。符号情報を別に扱う。
ビット列に符号情報まで埋め込む。

の２通りがある。RubyのBignumとかは前者。
後者の方法はつまりビット列を２の補数表現の整数などと解釈するということ。

作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久
出版社/メーカー: エスアイビーアクセス
発売日: 2004/09
メディア: 単行本
購入: 35人クリック: 732回
この商品を含むブログ (129件) を見る

には後者の方法で乗算を行う実装が紹介してあった。
この方法では

1.まず符号なし乗算。

ビット列全体を一つの整数としてみて、負数は２の補数が使われているとすると
(Xがmビット整数xを符号なしとして解釈した値だとすると)
$X=\left\{ \begin{array}{cc} x & (x\geq 0) \\ x + 2^m & (x < 0) \\ \end{array}\right.$
になる。
なので、xの符号ビットを $s_x$ (xが0以上なら0、それ以外なら1)と表すことにすると
mビット整数xとnビット整数yを符号なし乗算した値は
$XY = (x + s_x2^m)(y+s_y2^n) = xy + xs_y2^n+ys_x2^m+s_xs_y2^{m+n}$
となる。