長大語計算

TAOCPにbroadword computingという話題がある. 長大なビット列に対する演算法である.

例えば x=1110111101100111 の中で 0111 というパターンを探す問題である.
その答は q=0001000000001000 である. つまりqの1に対応するxの場所が0111の0であり, その右に111があるのだ.

方法は q=¬x & x<<1 & x<<2 & x<<3 とすればよい. 途中の状況を示すと下のようだ.

x    =(1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1)
¬ x =(0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0)
x<<1 =(1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 0)
x<<2 =(1 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0)
x<<3 =(0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0)
q    =(0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0)

つまり探すパターンの各ビットが0なら¬x, 1ならxのままを, 左シフトで, 答の位置に集め, 全体の&をとれば得られるわけである.

応用問題として, 5月8日のブログの最初にあるQ₀とQ₁から11011, つまり双子の素数が並んでいる場所を探してみる.

(define x #x2196820D864A4C32816D129A64B4CB6E)

として, x & x<<1 & (¬x)<<2 & x<<3 & x<<4 で良い筈である.

から

が得られる. つまり, 5と7と11と13, 11と13と17と19で, この辺はすぐ思いつく. その次は101と103と107と109であり, さらに191と193と197と199が続く. これだけ素数が連続するから, 他の小さい素数はどこに隠れるか見てみると

101 = 101
102 = 17 3 2
103 = 103
104 = 13 2 2 2
105 = 7 5 3
106 = 53 2
107 = 107
108 = 3 3 3 2 2
109 = 109

のように, 7, 13, 17がうまく2や5と一緒になる.

191 = 191
192 = 3 2 2 2 2 2 2
193 = 193
194 = 97 2
195 = 13 5 3
196 = 7 7 2 2
197 = 197
198 = 11 3 3 2
199 = 199

も同様.

ついでにQ₀からQ₇までを使い

として, もう少し先まで探すと qが得られ, 最左の1の位置を求める.
(ここでi2bは整数を0と1のビット列にする関数. iandなどは, 2つの整数のビット毎ANDなど, ilshは整数のビット左シフトである.)

(length (member 1 q)) => 940

従って並ぶ双子の最大の素数は

(- (* 940 2) 1) => 1879

であり, この辺りは

1871 = 1871
1872 = 13 3 3 2 2 2 2
1873 = 1873
1874 = 937 2
1875 = 5 5 5 5 3
1876 = 67 7 2 2
1877 = 1877
1878 = 313 3 2
1879 = 1879

次は

(length (member 1 (list-tail q (- 1024 940 -1)))) => 745
(- (* 745 2) 1)) => 1489

1481 = 1481
1482 = 19 13 3 2
1483 = 1483
1484 = 53 7 2 2
1485 = 11 5 3 3 3
1486 = 743 2
1487 = 1487
1488 = 31 3 2 2 2 2
1489 = 1489

(length (member 1 (list-tail q (- 1024 745 -1)))) => 415
(- (* 415 2) 1) => 829

821 = 821
822 = 137 3 2
823 = 823
824 = 103 2 2 2
825 = 11 5 5 3
826 = 59 7 2
827 = 827
828 = 23 3 3 2 2
829 = 829

(length (member 1 (list-tail q (- 1024 415 -1)))) => 100

となり, 先ほどの199, 197, 193, 191が得られる.