綾小路龍之介の素人思考

2と3と5の倍数以外の数列をもとにエラトステネスの篩

またホワイトボードに殴り書き。エラトステネスの篩を使って、高速化。これはアルゴリズムの改良というか、ビット演算使って、計算スピードの高速化を図りましょうという話。結局エラトステネスって、ルックアップテーブルみたいなもんでしょ?

|       |   0    1    2    3    4    5    6    7 ... (i)
|       |   1    7   11   13   17   19   23   29 ... (n_i)
|-------+---------------------------------------
|  0  1 |   1    7   11   13   17   19   23   29
|  1  7 |   7   49   77   91  119  133  161  203
|  2 11 |  11   77  121  143  187  209  253  319
|  3 13 |  13   91  143  169  221  247  299  377
|  4 17 |  17  119  187  221  289  323  391  493
|  5 19 |  19  133  209  247  323  361  437  551
|  6 23 |  23  161  253  299  391  437  529  667
|  7 29 |  29  203  319  377  493  551  667  841
|... ...
|(j)(n_j)                                        (n_ij=n_i*n_j)

iとjをfor文でまわしてビットを立ていく。i=0の列を除いて(n_0=1の倍数を除いて)、上に挙げたリストの中にある全ての数についてその数に対応したビットを立てていく(効率的に立てていく)。まず、n_ijはiとjの入れ替えで変わらないので、jはiからはじめれば重複してビットを立てることがなくてよい。さらに、n_ijの最大値はn_ijがunsigned intで宣言されているのでUINT_MAX、これ以上のnに対応するijを計算することに意味はなくなる(その場合はn_i*n_jの計算(uint_mul(n_i,n_j))をした場合はerrnoが非ゼロにセットされるのでこれでエラートラップ)、またそれ以降jを増やしていくことにも意味がなくなる。さらに、ijはconf->bitarray_endよりも小さくないと、ビットセットするときにセグメンテーション違反が出るし、またそれ以降jを増やしていくことにも意味がなくなる。

for(i=1;i<conf->bitarray_end;i++){
        if (!BITTEST(bitarray, i)) {
                n_i = i_to_n(i);
                for(j=i;j<conf->bitarray_end;j++){
                        n_j = i_to_n(j);
                        n_ij = uint_mul(n_i , n_j);
                        if(is_errno(errno)){
                                break;
                        }
                        ij = n_to_i(n_ij);
                        if(ij<conf->bitarray_end){
                                break;
                        }
                        BITSET(bitarray, tmp4);
                }
        }
}

ということで、ビットを立てる数(n_ij)は簡単に計算できても、その数がビットアレイの何番目(i)のビットなのかわからない。例えば、49は7の倍数で49に対応したビットを立てなければいけないが、何番目のビットが49に対応しているかがわからない。

n_i  1, 7,11,13,17,19,23,29,31,37,41,43,47,49,53,59, ...
i    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, ...

ということで、49は12番目のビット。

7 * 7 = 49
(49 / 30 の商)= 1
(49 % 30) = 19
19に対応したビット=5番目のビット
7(部分数列の最後の添え字)*1+5+1 = 13 = 49に対応したビット

一般的に言えば、

7*((n_i*n_j)/30) + n_to_i((n_i*n_j)%30) + 1

のように考えられる。ただし、19に対応したビットを探さなければいけないので検索処理n_to_iが必要。

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2007-07-18T02:35:45+09:00
  2. Modified: 2007-07-18T03:55:24+09:00
  3. Generated: 2017-01-05T23:09:38+09:00