幕間 素因数分解について考えた 前
ゲームブック進めず、すみません。
時折、無性に素因数分解に挑戦したくなります。
（あるいは双子素数とか)
ついやってしまったので、以下、記録を投稿です。
正の奇数AとBを掛け合わせた数をNとする。
以下が成立する。
((A+B)/2)^2 = N + ((A-B)/2)^2
※もう少し書くと
N = A*B
4*N = 4*A*B
4*N = (A^2-A^2) + 4*A*B + (B^2-B^2) = (A+B)^2 - (A-B)^2
N = ((A+B)/2)^2 - ((A-B)/2)^2
※※
言い方を変えれば、奇数同士の掛け合わせは２つの平方数(ある数の二乗)の差になり、そこから掛け合わせた数が判る。
A=Bではない場合について考える(便宜上、A>Bとする)
N は ((A-B)/2)^2 より小さい事はあるが、(A-B)/2 よりは大きい
なぜならば
Nと(A+B)/2を比較すれば
AとBは正の奇数なおかつA>Bなので、A>3 かつ B>1 成立
なので
A*B ＞ A+B
も成立するので、ゆえに
N/2＞(A+B)/2
も成立
当然
N＞(A-B)/2
も成立
N/2を切り上げて整数化した数をXとする。
ここで1からXまでの平方数を数列として用意する(1^2からX^2まで)
この数列を配列ではなくsetと言うオブジェクトにして扱う事で、極めて高速な(環境にもよるがjavascriptで1000億程度ならば100分の1秒単位で終了)素因数分解が可能になる(と、この時点では思っていました。ただしsetの存在チェックは本当に早いです)。
【JavaScriptの応用】MapとSet
https://tcd-theme.com/2021/10/javascript-map-set.html
注意点としては、forEachメソッドで繰り返すとbreak;が出来ないので
for (let num of set) {
let a = num + N;
if(set.has(a)){
alert("見つけた");
console.log(num);
break;
}
と言う書き方が望ましいかも。(途中で止まらないので)
ただし、当然ながら大きな数の平方数の数列を用意するのは難しいです。
（１から10000000000000(100万の二乗)までの数列でファイルサイズにして12Mb)
100ケタを余裕で超えるような数の素因数分解には向かない？
※上記は10進法。ふと思ったが、10進法ではなく1000進法とか使えばある程度ファイルサイズの問題はカバーできる?
さて、平方数をあらかじめ用意しなくても考え方は使えるでしょうから、特に考えずにmath.sqrt(X)の結果を見て判断すると・・・あれ？
こちらの方が早い。
71751044477311 の 素因数分解（7178627 * 9995093）が0.03秒程度
8635844967113809 の 素因数分解（89652331×96325939）が0.475秒程度
※結局、見つかるまで全件試すので、この例のままでは13*96325939とかだと秒単位になりますから参考程度にすべきですね。
最近のjavascriptはBigIntと言う大きい数を扱えるので、これは！と思ったのですがBigIntは、math.sqrt(X)と言う処理まではやってくれません。(math.メソッド全般)
ただしJavascriptはべき乗 (**)はBigIntを受け入れると記述があり、A**0.5なら行けるかもしれませんが、TypeScriptのコンパイルオプションのlibをes2020以降にしないとエラーになる模様。
tsconfig.jsonをいじると行けるようですが、ビルドエラーが出まくりなので今後の目標にしておきます。
べき乗 (**)
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Exponentiation
とりあえず、平方数の数列がなくても良い事に安堵しつつ、もう少し高速化を図ります。
(未来技術的には、setの方法もありかもしれませんが)
平方数かどうかのチェックは、”重い”処理らしいのですが、有る数で割った余りを見ることで多くの"平方数でない数字"をはねることが出来ます。
有名なのが256で割った余りで、もしある数値が平方数ならば256で割った余りは44種類の値しか出現しないので、それ以外の値が出れば確認するまでもなく平方数では無いとはじく事が出来ます。
（もちろん余りがそのいずれかであった場合、改めて平方数かどうかを確認する必要があります）
平方数かどうかを高速に判定する方法
https://hnw.hatenablog.com/entry/20140503
色々な数を調べると、かなり剰余ではねることのできる数値もありましたので、なかなか有望かもしれません。（今度こそsetの出番？)
javascriptのチューニングだと思いますが、予想外に高速でしたので、もうちょっとだけ寄り道させてください。
投稿
