アカウント名:
パスワード:
試しにプログラムを書かれる方がいるかと思いますので参考まで
以前エラトステネスのフルイのプログラムを色々書いてみた事ありますが、10^10とかのオーダーになると単純にプログラムすると、10Gバイトメモリが必要ですが、フルイを分割してプログラムした方がメモリ節約＆キャッシュの効きがよくて速いですよ。
フルイの分割というのは、フルイの対象とする範囲を、例えば
2～10^810^8～2*10^82*10^8～3*10^8 ....99*10^8～100*10^8
とか分割します。分割したそれぞれに対してフルイを実行します。
（分割の単位は例です。分割の単位はベンチ行って最適化してください。
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)に設定を変更する必要があります。
クラックを法規制強化で止められると思ってる奴は頭がおかしい -- あるアレゲ人
こ、これは (スコア: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
とか分割します。分割したそれぞれに対してフルイを実行します。
（分割の単位は例です。分割の単位はベンチ行って最適化してください。
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};