前回の、プログラミングの記事の続きです。
問題
ab(a＋b)(a－b)＝13c2
を満たす自然数(a,b,c)の組を見つけてください。
というものでした。
更に、問題を一般化して、
問題
ab(a＋b)(a－b)＝mc2
を満たす、mを合同数する自然数(m,a,b,c)の組を見つけてください。
でしたね。
これを手計算で見つけてもいいんだけれども、プログラミングして見つけることにします。
当初はm=13だけを求めればよかっただけなので、
左辺のmc2は正より、a－bは正でなければならないことから、
a＞b＞0という条件は自ずと見えてきますので、aを超えない1以上のbで、aとbの二重ネストでマシンパワーで検索するというものでした。
まぁ、13くらいならばそれで問題はないのだが、mを100未満の合同数という枷を自ら課したわけです。
数学をやっていると、こういう一般化して考えるってのはよくやることの一つなんです。
そうなると、今までのプログラムではいろいろと問題が出てくる。
mが大きくなると、答えが出るのに時間が掛かる。
特にmが素数だとその傾向は如実に強く出てくる。
シンプルなプログラムという意味では、最初の物で良かったのだが、余計な計算を沢山させているということでもある。
こうなってくると、数学的考証ってのが必要になってくるのだ。
まず、私自身がどんな解が欲しいのかということ。
mを合同数としたが、手こずっているのはmが合同数でありながら、素数の場合である。
mが素数に限定されると、少し物事が見えてくるのだ。
というわけで、mは合同数でありながら素数の場合だけに特化したプログラムを考えることにする。
a、b、a＋b、a－bという4つの自然数の積は、mとc2の積と等しい。
つまり、
a≡0 (mod m)
b≡0 (mod m)
a＋b≡0 (mod m)
a－b≡0 (mod m)
のうちの、いずれか1つでも該当するものがなければならないと、等式は成立しないうことである。
つまり、必要条件なのである。
mが素数ではなくて合成数の場合は、約数が分散してどこかで割り切れればよかったとも言えるが、aやbが小さい値で見つかりやすかったのも、これが理由であろう。
続いて、
ab(a＋b)(a－b)＝mc2
この式において、
例
m=5,a=8405,b=3600,c=18683700
このような解は、特に欲していないのだ。
ならば、どうすればいいのかというと、aとbは互いに素な関係のものだけを調べれば良いとなる。
互いに素ということで、ユークリッドの互除法をプログラムに組み込む必要が出てくる。
さて、aとbが互いに素になると、何か高速化に役に立つことが出てくるのだろうか。
gcd(a,b)＝1のとき、
gcd(a,a＋b)＝1
gcd(a,a－b)＝1
gcd(b,a＋b)＝1
gcd(b,a－b)＝1
なことは、ユークリッドの互除法から自明である。
これは余計な計算を減らせる要素となる。
x[0]＝a
x[1]＝b
x[2]＝a＋b
x[3]＝a－b
として、
x[0]からx[3]までのいずれか一つがmで割り切れる。
x[0]・x[1]・x[2]・x[3]÷m＝c2
ここからのx[n]は、どれか1つをmで割ったものとして、次に進む。
どれで割りきれたかは、ここでは重要ではない。
割り切れる必要があることが重要なのだ。
x[0]・x[1]・x[2]・x[3]＝c2
gcd(x[0],x[1])＞1ならば、解を求める必要がないことは、先に示した通りである。
また、
gcd(x[0],x[1])＝1のとき、
gcd(x[0],x[2])＝1
gcd(x[0],x[3])＝1
gcd(x[1],x[2])＝1
gcd(x[1],x[3])＝1
であることも、先に示した通りである。
ということは、
gcd(x[2],x[3])=g
とおくと、
gcd(x[0],g)＝1
gcd(x[1],g)＝1
であるからして、
x[0]とx[1]は右辺がc2という平方数から、
x[0]とx[1]は共に平方数でなけらばならない。
続いて、
g＝gcd(x[2],x[3])
から、
x[0]・x[1]・x[2]・x[3]・g＝c
左辺のこれら5つは、もともと64ビット正整数の範疇であり、小さくなることはあっても大きくなることはないので、64ビット正整数の範疇を超えることはないのである。
ただし、右辺のcは64ビットを超える可能性を秘めているのだが、左辺の5つの積の形で表されているので、それは別途計算すれば良いだけであるとも言える。
これにより、mが素数で大きいものでも、かなり高速なプログラムを作ることに成功したと言える。
ただ、この記事が上がっている時点で、m＝53、m＝79が求まっているのかは解らない。
プログラミングに数学の知識は必要か？
という問いに関して言えば、数学の知識がなくても出来る。
まぁ、計算をすると言っても四則演算とかくらいだろうか。
まぁ、四則演算、条件分岐、反復、こういったことだけでプログラムが作れるのだ。
なので、難しい数学の知識はなくて、プログラミングは出来る。
と言える。
だけどね、そのプログラムの出来・不出来という観点から見ると、余計な計算をしているとか、余計な条件分岐をしているとか、余計な反復をしているとか、そういった余計なことをやっていることが多いのだ。
マシン性能やコンパイラに最適化に任せるということでもいいんだろうけど、それでも納得が行くか行かないかというのはあるだろう。
例えば、一番気になるのが結果を出すまでの時間だろうか。
自分が生きている間に結果が出るのか怪しいなんてことを、自分が初心者だったころはやっていたし、今でもそういう難問にチャレンジすることもある。
まぁ、結果を知ることが叶わないならば、なんか手はないのか？と考えるわけで、どうやったらプログラムが高速に結果を出力するのかを模索する必要が出てくる。
そのアイディアは大抵の場合、数学がヒントになるのである。
つまり、数学を知らなくてもプログラミングは出来るけれども、出来上がったプログラムの、速い・遅い、出来・不出来、良し悪しに、少なからず数学が絡んでくるよという話しです。
それは、コンピュータにしろ、プログラミング言語にしろ、数学を基盤としているからであって、そこは論理に支配された世界なのです。
特に、私のような数学の問題をプログラミングで解くとか、図形問題の図をプログラミングで座標計算して描くとか、数学とプログラミングが相互に直結しているので、数学とプログラミングはどちらか一方が欠けてしまうと成り立たないのです。
たとえ、数学関連のありとあらゆる計算アルゴリズムが最適化されて、誰でも高速に動くプログラミングが出来る時代ってのは来るのかもしれないけれども、それを自分が体験出来るのかということになるわけで、私が初めてコンピュータと言われるもの、ポケコン、もうすこし後になるがパソコンを買ってから、かなりの月日が経ち、日進月歩で性能が上がっていくのを目の当たりにしてきた。
でも、パソコンの性能やコンパイラの性能に頼り切っているだけでは、私のプログラミング技術は伸び悩むし、数学の知識も釣られてしまう。
まぁ、今使っているパソコンは2011年製なので、Windows10にはアップグレード出来たが、Windows11にはアップグレード出来ないというボロパソコンである。
ボロパソコンであれ、逆に性能が低い時代のパソコンの方が、プログラミング技術は向上するというのがあるのだ。
まぁ、ネットが繋がって、ネットから情報を得られるというのも重要なのかもしれないけれども、そのきっかけは必要なんですよね。
ではでは