7

空き時間にプロジェクト Euler をプレイしていて、リファクタリングが必要なところまで来ました。Miller-Rabin といくつかのふるいを実装しました。ふるいは、数百万未満のように小さい数の方が実際には高速であると以前に聞いたことがあります。誰もこれに関する情報を持っていますか？Google はあまり役に立ちませんでした。

4

4 に答える 4

10

はい、ほとんどのアルゴリズムで、スペースを時間と交換できることがわかります。つまり、より多くのメモリを使用できるようにすることで、速度が大幅に向上します *a。

私は Miller-Rabin アルゴリズムを実際には知りませんが、単一の左シフト/追加およびメモリ抽出よりも単純でない限り、事前に計算されたふるいによって水から吹き飛ばされます。

ここで重要なことは、事前に計算されています。最初の 100 万個の素数が近い将来に変更される可能性は低いため、パフォーマンスの観点から、このようなことを事前に計算することをお勧めします :-)

つまり、次のようなふるいを作成します。

unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1};
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))

a++マクロなどに渡さないという通常の注意事項があります。これにより、両方の長所が得られます。「小さい」素数の場合は目がくらむほど高速なテーブル ルックアップが行われ、範囲外の場合は計算方法に戻ります。

他の方法の 1 つを使用してルックアップ テーブルを生成するプログラムを作成することは明らかです。すべてを手動で入力する必要はありません。

しかし、すべての最適化の質問と同様に、推測ではなく測定してください。

*aこれの典型的なケースは、かつて組込みシステム用に書かなければならなかったいくつかの三角関数でした。これは競争力のある契約入札であり、システムには CPU のうなり声よりも少し多くのストレージがありました。

機能のベンチマーク数値が競合を圧倒したため、実際に契約を獲得しました。

なんで？別のマシンで最初に計算されたルックアップ テーブルに値を事前に計算したためです。リダクション (入力値を 90 度より下に下げる) と三角関数 (コサインはサインの位相シフトに過ぎず、他の 3 つの象限は最初の象限に関連しているという事実) を慎重に使用することで、ルックアップ テーブルを180 エントリ (0.5 度ごとに 1 つ)。

最善の解決策は、エレガントでよこしまなものです:-)

価値のあることとして、次の C コードは、400 万未満のすべての素数 (そのうちの 283,000) を含むテーブルを生成します。

#include <stdio.h>

static unsigned char primeTbl[4000000];

int main (void) {
    int i, j;

    for (i = 0; i < sizeof(primeTbl); i++)
        primeTbl[i] = 1;

    primeTbl[0] = 0;
    primeTbl[1] = 0;
    for (i = 2; i < sizeof(primeTbl); i++)
        if (primeTbl[i])
            for (j = i + i; j < sizeof(primeTbl); j += i)
                primeTbl[j] = 0;

    printf ("static unsigned char primeTbl[] = {");
    for (i = 0; i < sizeof(primeTbl); i++) {
        if ((i % 50) == 0) {
            printf ("\n   ");
        }
        printf ("%d,", primeTbl[i]);
    }
    printf ("\n};\n");
    printf ("#define isPrime(x) "
        "((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n");

    return 0;
}

テーブルを 1600 万エントリ (16M) に増やすことができれprimeTblば、素数の数を 100 万以上 (最初の 1,031,130 個の素数) に保つのに十分であることがわかります。

現在、奇数のみを格納し、マクロを調整してそれを処理するか、符号なし文字の代わりにビット マスクを使用するなど、記憶域を少なくする方法があります。メモリが利用可能であれば、アルゴリズムの単純さを好みます。

于 2010-09-20T21:59:02.697 に答える
6

段階的なアプローチをお勧めします。まず、小さな素因数がないことを確認します。最初の 20 個または 30 個の素数による試行分割は機能しますが、巧妙なアプローチを使用すると、gcd を使用して必要な分割数を減らすことができます。このステップにより、複合材の約 90% が除外されます。

次に、その数が 2 を基数とする強い可能性のある素数であるかどうかをテストします (Miller-Rabin テスト)。

証明の最終ステップは、どれだけ大きくしたいかによって異なります。狭い範囲で作業したい場合は、許容される最大の 2 擬素数のリストでバイナリ検索を実行します。それが 2^32 の場合、リストには 10,403 メンバーしかないため、ルックアップには 14 クエリしかかかりません。

2^64 まで上げたい場合は、( Jan Feitismaのおかげで) その数が BPSW 擬素数かどうかを確認するだけで十分です。(すべての例外の 3 GB のリストをダウンロードし、試行分割で削除されるものを削除し、ディスクベースのバイナリ検索を作成することもできます。) TR Nicelyには、これを合理的に効率的に実装する方法を説明する素晴らしいページがあります。

もっと上に行く必要がある場合は、上記の方法を実装し、ポックリントン スタイルのテストのサブルーチンとして使用します。これは「小さい」の定義を拡張します。これらの方法について詳しく知りたい場合は、質問してください。

于 2010-09-21T18:32:47.577 に答える
2

事前計算の概念の変形として、最初に候補数pが 2、3、5、7、または 11 で割り切れるかどうかを安価にチェックできます。そうでない場合は、p素数 if 2 p-1 = 1 (mod p ）。これはある時点で失敗しますが、テスト済み (事前計算) であるため、1 億までは機能します。

言い換えれば、2 を底とする小さなフェルマー擬素数はすべて、3、5、7、または 11 のいずれかで割り切れます。

編集：

@starblue が正しく指摘しているように、上記は単純に間違っています。プログラムにバグがありました。私ができる最善のことは、上記を次のように修正することです。

候補pが 2、3、5、7、または 11 で割り切れる場合、それを合成と宣言します。
それ以外の場合pは、{4181921、4469471、5256091、9006401、9863461} のいずれかである場合は、複合体であると宣言します。それ以外の場合、基数 2 と基数 5 の Miller-Rabin テストに合格した
場合は、素数であると宣言します。 それ以外の場合は、コンポジットを宣言します。p

これは、10,000,000 未満の整数についてテストしました。おそらく、別のベースのペアがさらにうまくいくでしょう.

私の過ちをお詫び申し上げます。

編集2：

まあ、私が求めていた情報は、すでにウィキペディアのMiller-Rabin アルゴリズムのページ、 「テストの決定論的バリアント」というタイトルのセクションにあるようです。

于 2010-09-21T00:20:15.053 に答える
1

唯一の方法は、自分自身をベンチマークすることです。そのときは、それを書き留めて、オンラインのどこかに投稿してください。

于 2010-09-20T21:54:52.843 に答える