アカウント名:
パスワード:
試しにプログラムを書かれる方がいるかと思いますので参考まで
以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、10^10とかのオーダーになると単純にプログラムすると、10Gバイトメモリが必要ですが、フルイを分割してプログラムした方がメモリ節約＆キャッシュの効きがよくて速いですよ。
フルイの分割というのは、フルイの対象とする範囲を、例えば
2～10^810^8～2*10^82*10^8～3*10^8 ....99*10^8～100*10^8
とか分割します。分割したそれぞれに対してフルイを実行します。
（分割の単位は例です。分割の単位はベンチ行って最適化してください。）
途中の数からフルイを計算をはじめるためには、素数の表を持っておく必要があります。10^10までフルイを実行するには10^5までの素数表を持っておけばいいです。これはあらかじめ作る必要はなく、最初の2～10^8のフルイ実行時の結果を記憶しておけばいいです。
というような工夫をすれば、AMD Opteron 1216で10^10までのフルイは3分7秒、10^11までは34分7秒で実行出来ました。
なおメモリ節約のため上記のような分割ではなく、bit単位でのアクセス、2/3/5の倍数を例外扱いなどをしてメモリ節約される方もいるかもしれませんが、かなりペナルティが高いです。10^10までのフルイで24分57秒、10^11までのフルイで230分16秒という結果になりました。
言語は何で書きましたか？
3や5でペナルティが大きいのはなんとなく分かる気がします。しかし2は単純な論理積演算で検証が可能ですが、それでもペナルティは大きいんですか？
2/3/5でそれぞれ比較は行っていませんが、10^9までの計算で次のような結果になっています。(10^10までは行ってません)
bit単位のアクセスでメモリ節約: 2分20秒bit単位のアクセスに加えて2/3/5の例外扱いでメモリ節約: 2分59秒
したがって2/3/5の例外扱いでペナルティが高いは大げさでした。bit単位でのアクセスはペナルティが高いに修正します。
なお、2/3/5の例外扱いのために次のような読み替えテーブルを使ってます。説明は省きますが2/3/5の最小公倍数は30ですので、大体意味わかると思います。
static const int_fast32_t yomikae_table[30]={-1, 0,-1,-1,-1,-1,-1, 1,-1,-1, -1, 2,-1, 3,-1,-1,-1, 4,-1, 5, -1,-1,-1, 6,-1,-1,-1,-1,-1, 7};
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー
こ、これは (スコア:0)
みんな、すぐに手元のコンピュータで確認してみるんだ
エラトステネスの篩をアレンジしたプログラムなんかは簡単に作れるよね
エラトステネスの篩で参考 (スコア:5, 参考になる)
試しにプログラムを書かれる方がいるかと思いますので参考まで
以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、10^10とかのオーダーになると単純にプログラムすると、10Gバイトメモリが必要ですが、フルイを分割してプログラムした方がメモリ節約＆キャッシュの効きがよくて速いですよ。
フルイの分割というのは、フルイの対象とする範囲を、例えば
2～10^8
10^8～2*10^8
2*10^8～3*10^8
....
99*10^8～100*10^8
とか分割します。分割したそれぞれに対してフルイを実行します。
（分割の単位は例です。分割の単位はベンチ行って最適化してください。）
途中の数からフルイを計算をはじめるためには、素数の表を持っておく必要があります。10^10までフルイを実行するには10^5までの素数表を持っておけばいいです。これはあらかじめ作る必要はなく、最初の2～10^8のフルイ実行時の結果を記憶しておけばいいです。
というような工夫をすれば、AMD Opteron 1216で10^10までのフルイは3分7秒、10^11までは34分7秒で実行出来ました。
なおメモリ節約のため上記のような分割ではなく、bit単位でのアクセス、2/3/5の倍数を例外扱いなどをしてメモリ節約される方もいるかもしれませんが、かなりペナルティが高いです。10^10までのフルイで24分57秒、10^11までのフルイで230分16秒という結果になりました。
Re:エラトステネスの篩で参考 (スコア:2, おもしろおかしい)
Re:エラトステネスの篩で参考 (スコア:1)
言語は何で書きましたか？
Re:エラトステネスの篩で参考 (スコア:2)
Re: (スコア:0)
3や5でペナルティが大きいのはなんとなく分かる気がします。
しかし2は単純な論理積演算で検証が可能ですが、それでも
ペナルティは大きいんですか？
Re:エラトステネスの篩で参考 (スコア:2)
2/3/5でそれぞれ比較は行っていませんが、10^9までの計算で
次のような結果になっています。(10^10までは行ってません)
bit単位のアクセスでメモリ節約: 2分20秒
bit単位のアクセスに加えて2/3/5の例外扱いでメモリ節約: 2分59秒
したがって2/3/5の例外扱いでペナルティが高いは大げさでした。
bit単位でのアクセスはペナルティが高いに修正します。
なお、2/3/5の例外扱いのために次のような読み替えテーブル
を使ってます。説明は省きますが2/3/5の最小公倍数は30です
ので、大体意味わかると思います。
static const int_fast32_t yomikae_table[30]=
{-1, 0,-1,-1,-1,-1,-1, 1,-1,-1,
-1, 2,-1, 3,-1,-1,-1, 4,-1, 5,
-1,-1,-1, 6,-1,-1,-1,-1,-1, 7};