H.Nakao's Elliptic Curves Topics
since 2001.06.02
楕円曲線に関する話題
超楕円曲線に関する話題
円錐曲線に関する話題
数論アルゴリズム
What's new!
プログラム作成には生成AIは役に立つ[2026.09.16]
これまで、力任せの全域検索(Brute-force-saerch)で、対角4次ディオファントス方程式
A^4+h*B^4 = C^4+h*D^4
の自明でない小さい整数解(0 < A < C, 0 < D < B, gcd(A,B,C,D)=1)を探すために、Pari/gp(gp2c-run)で記述したプログラムを使っていたが、例えば、max(A,B,C,D)<=100000の範囲で検索すると、数日掛かっていた。
掲示板「出会いの泉」で、らすかる氏が超高速な力任せの全域検索(Brute-force-saerch)のアルゴリズムを公開してくれた。自分で0から作成することも不可能ではないが、作成とデバッグで1週間ほどの時間が掛かることが予想された。その間は研究が全く進まなくなるので、AIにプログラム作成を支援してもらうことにした。
らすかる(T.Suzuki)氏のアルゴリズムを記述したテキストをGoogle AIモードに読み込ませて、いくつかの指示を与えて、C言語のプログラムのひな型を作成させた。その後、自分でひな型に修正を加えて、デバッグと動作確認を行って、1日で完成させた。
らすかる氏に、彼のアルゴリズムを実装したものであることをプログラム中に明記して、GPLv3ライセンスで公開して良いか聞いたところ、承諾されたので、掲示板「出会いの泉」(スレッドNo.3267, 2026.09.14 10:25の返信)で、C言語のソースコード"dqde4.c"の形で投稿・公開した。
掲示板「出会いの泉」では、各行の先頭の空白が消えて、インデントが無くなっているので、読みづらい。
そこで、オリジナルのCプログラム"dqde4.c"をここでも公開する。
int128(128bit整数)が利用できるCコンパイラ(gccなど)があれば、コンパイルは簡単だ。
gcc -O2 dqde4.c -o dqde4
例えば、h=20054, max(A,B,C,D)<=100000の範囲で全域検索すると、1秒掛からずに、0個と出力する、
さらに、max(A,B,C,D) <=1000000の範囲に広げて全域検索をすると、約1時間で5個の整数解を出力する。
-bash-3.1$ time ./dqde4 20054 -m 100000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 20054, N = 100000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / h...
Total nodes collected after filter: 718754
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
Found 0 solutions.
Search finished successfully.
real 0m8.868s
user 0m8.715s
sys 0m0.150s
-bash-3.1$ time ./dqde4 20054 -m 1000000
--- Diophantine Equation A^4 + h*B^4 = C^4 + h*D^4 Search Started ---
Settings: h = 20054, N = 1000000, FILTER_MOD = 1360, HASH_MOD = 9999991, Verbose = OFF
[2/4] Computing and filtering (z^4 - x^4) / h...
Total nodes collected after filter: 75441836
[3/4] Creating hash index table...
[4/4] Generating y^4 - w^4 and performing main search...
66519^4+20054*18276^4=206897^4+20054*12062^4
20130^4+20054*18305^4=211998^4+20054*10369^4
190463^4+20054*27643^4=254519^4+20054*25759^4
5339^4+20054*67687^4=805331^4+20054*11189^4
7325^4+20054*73476^4=870715^4+20054*26382^4
Found 5 solutions.
Search finished successfully.
real 57m47.625s
user 57m39.678s
sys 0m7.875s
この"dqde4.c"によって、小さい自明でない整数解を求める時間が著しく短縮できた。
この素晴らしいアルゴリズム(超高速化ノウハウを含む)を惜しみなく公開してくれたらすかる氏に感謝する。
カワセミ♂[2025.02.04]
|
カワセミ♀[2025.02.04]
|
K200D写真集
写真共有サイト「フォト蔵」
関連サイト
| Last Update: 2026.09.17 |
| H.Nakao |