750k+
| SCENE RESEARCH STATION | |
| with my everyday thinking-and-doctrine |
| /(top) | /about | /antenna | /map | /modp | /dispe | /bbs |
桁集合が{-1,0,1}となる2進表現． 通常の2進表現の桁集合は{0,1}である．
冗長2進表現から通常の2進表現への逐次変換の事．
例えば冗長2進表現{1,0,-1,0}を2進表現に変換すると{0,1,1,0}となる(いずれも10進数で6を表す)．
これを素直な加算と減算で実現すると，-1が入力されたときにキャリーが伝播するため， n桁の変換コストはO(n)となる(桁上げ先見等を使ってもO(log_2 n)である)．
キャリーの伝播をなくし定数時間で処理するためには，-1が入力された場合の答え(言い換えるなら1小さい表現)を内部に持てばよい．
通常の表現をP，1小さい表現をNとすれば，変換規則は次のようになる．
| 入力 | 1 | 0 | -1 |
|---|---|---|---|
| P(i+1) | P(i),1 | P(i),0 | N(i),1 |
| N(i+1) | P(i),0 | N(i),1 | N(i),0 |
これだけでは分かりにくいので，具体的に冗長2進表現{1,0,-1,0}の変換例を示す．
| 入力 | 1 | 0 | -1 | 0 |
|---|---|---|---|---|
| P(i) | {1} | {1,0} | {0,1,1} | {0,1,1,0} |
| N(i) | {0} | {0,1} | {0,1,0} | {0,1,0,1} |
以上，桁集合が{-1,0,1}の場合について説明した．より高基数の場合も同様である．Pと基数分小さいNを持てばon-the-fly変換ができる．
冗長4進表現(桁集合{-3,-2,-1,0,1,2,3})の場合の変換規則を以下に示す．
| 入力 | 3 | 2 | 1 | 0 | -1 | -2 | -3 |
|---|---|---|---|---|---|---|---|
| P(i+1) | P(i),11 | P(i),10 | P(i),01 | P(i),00 | N(i),11 | N(i),10 | N(i),01 |
| N(i+1) | P(i),10 | P(i),01 | P(i),00 | N(i),11 | N(i),10 | N(i),01 | N(i),00 |
冗長4進表現{2,-2,-3,1,-1}を2進表現に変換すると{0,1, 0,1, 0,1, 0,0, 1,1}となる(いずれも10進数では2*4^4-2*4^3-3*4^2+1*2^2-1=339を表す)．上記の変換規則でこのon-the-fly変換ができることを確認しよう．
小学校で習う筆算と全く同じアルゴリズムである．
最上位ビットの桁ぞろえを行い，除数の方が大きければ1を立て，そうでなければ0を立てていく．1を立てた場合は被除数からシフト済みの除数を引く．
除数と被除数の比較と除数を引く減算が必要．比較中に減算を並列に処理すれば，減算のレイテンシは隠蔽できる(比較終了時に減算済みかそうでないものを使うかを選択する)．
常に被除数(正確には計算途中の剰余)が負にならないように振舞うため，「回復型」減算シフトとも呼ぶ．
減算シフトでは除数を商{0,1}を立てる基準としたが，これは0を基準として商{-1,1}を立てる．0との比較なので1ビットを比較するだけでよい．
商が冗長2進表現になるので，変換処理が必要になる(一般的にはon-the-flyで変換を行うためそのレイテンシは隠蔽できる)．
(書きかけ)
Clear[F, FT, x, X];
m = 13;
F[x_] := 2^x;
FT[x_] := Normal[Series[F[x], {x, 1/2, m}]];
FE[X_] := Abs[((FT[x] /. {x -> X})/F[X] - 1];
Log[2, N[Max[FE[0], FE[1]], 100]]
750k+