まず、あなたのプログラムを共有し、正確さに取り組んでくれてありがとう。私はテストを行うことが重要だと考えており、サイズの境界近くでのふるい分けは、コードの作業に時間を費やしたものでした。
「どこでも同じ結果: nada、zilch、niente.」あなたは十分に一生懸命見ていません。これを行うツールはたくさんあります。プライムシーブが 2^64-1 まで行かないのは残念ですが、それは他に何もないという意味ではありません。
「では、2^64 に近いふるいが適切に動作することをどのように確認できるでしょうか?」私が行ったことの 1 つは、2^64-1 付近の開始点/終了点のすべての組み合わせを実行するエッジケース テストを作成し、多くのメソッドがすべて同じ結果を生成することを確認することです。これは、これらの素数のリストを開始することに依存していますが、これらを取得する方法はたくさんあります。これは、この範囲でふるいをテストするだけでなく、開始/終了条件をテストして、そこに問題がないことを確認します.
2^64 以下の 100 万個の素数を生成するいくつかの方法:
time perl -Mntheory=:all -E 'forprimes { say } ~0-44347170,~0' | md5sum
1M の素数を生成するのに ~2 秒かかります。別のコード (Perl または GMP) の使用を強制したり、素数性テストを使用したりすることができます。これを行う方法はたくさんありますis_provable_prime($n)。たとえば、単にループして . Math::Primality を含む他の Perl モジュールもありますが、それらははるかに低速です。
echo 'forprime(i=2^64-44347170,2^64-1,print(i))' | time gp -f -q | md5sum
1M の素数を生成するのに ~13 秒かかります。Perl モジュールと同様に、決定論的ルーチンである isprime の呼び出しをループするなど、多くの代替方法があります (Pari/GP の古いバージョンではないことを前提としています)。
#include <stdio.h>
#include <gmp.h>
int main(void) {
mpz_t n;
mpz_init_set_str(n,"18446744073665204445",10);
mpz_nextprime(n, n);
while (mpz_sizeinbase(n,2) < 65) {
/* If you don't trust mpz_nextprime, one could add this:
* if (!mpz_probab_prime_p(n, 100))
* { fprintf(stderr, "Bad nextprime!\n"); return -1; }
*/
gmp_printf("%Zd\n",n);
mpz_nextprime(n, n);
}
mpz_clear(n);
return 0;
}
約 30 秒かかり、同じ結果が得られます。これは、25 のプリセット ランダム ベース MR テストを BPSW や証明方法の 1 つほど信頼していないため、より疑わしいですが、結果が一致しているため、この場合は問題ではありません。余分な 100 のテストを追加することは時間的に非常にコストがかかりますが、誤った結果が得られる可能性は非常に低くなります (塩基が重複していると思われるため、これも無駄です)。
from sympy import nextprime
n = 2**64-44347170;
n = nextprime(n)
while n < 2**64:
print n
n = nextprime(n)
Python の SymPy を使用します。残念ながら、primrange は 2^64-1 を指定するとクレイジーなメモリを使用するため、使用できません。単純な nextprime メソッドを実行するのは理想的ではありません。約 5 分かかりますが、同じ結果が生成されます (現在の SymPy isprime は 46 の素数ベースを使用します。これは、2^64 未満の決定論的な結果に必要な数よりもはるかに多いです)。
他にも FLINT や GAP などのツールがあります。
Windows を使用しているため、世界は不安定で、多くのことが正しく機能していないことに気付きました。Windows で Perl の ntheory をテストしましたが、コマンド プロンプトから Cygwin と Strawberry Perl の両方で同じ結果が得られました。GMP が正しく機能すると仮定すると、GMP コードは同じように機能するはずです。
編集追加: 結果が比較方法のいずれかと一致しない場合は、2 つのうちの 1 つ (または両方) が間違っています。間違っているのは比較コードかもしれません! エラーを見つけて報告すると、誰にとっても役立ちます。可能性は低いですが、両方とも同じように間違っている可能性があります。そのため、できるだけ多くの他の情報源と比較したいと考えています。私にとっては、比較する「ゴールデン」コードを 1 つ選ぶよりも堅牢です。特に、完全にテストされていない奇妙なプラットフォームを使用している場合.
BPSW の場合、いくつかの実装があります。
- パリ。AES Lucas は、Pari のソース コードに含まれているため、移植性が高いかどうかはわかりません。
- TRいいですね。強力なルーカス、スタンドアロン コード。
- デビッド・クリーバー。スタンダード、ストロング、エクストラストロングのルーカス。スタンドアロン ライブラリ、非常にわかりやすく、非常に使いやすい。
- x86_64 の asm Montgomery 数学を含む私の非 GMP コード。もちろん、bigint コードよりもかなり高速です。
- 私のGMPコード。標準、ストロング、AES、またはエクストラストロング ルーカス。他の bigint コードよりも高速です。また、他の Frobenius および他の複合性テストもあります。スタンドアロンにすることができます。
- 私は LibTomMath を使用するバージョンを持っており、これを Perl6 VM の 1 つに入れたいと考えています。LTM を使用したい場合にのみ興味深いものです。
Feitsma データに対して検証済みのすべて。私は周りにももっと多くの実装があると確信しています。FLINT には非常に高速なバリエーションがありますが、実際には BPSW ではありません (ただし、2^64 未満の数値については検証されています)。