Excelと素因数分解とLAMBDA関数の２
〜2月9日 00:00
ExcelでVBAを使わずに素因数分解をしてみようチャレンジの２回目です。
まず、前回の失敗を振り返ってから、新しい手法を試みてみます。
Excelの再帰は使えない！？
前回のソースを見直してみましょう。
FuncName : Factor2
Discription : 素因数分解。LAMBDA再帰版。
Argments : num, [i], [tmp]
Function definition :
=LET(
_i, IF(ISOMITTED(i), 2, i),
_t, IF(ISOMITTED(tmp), 1, tmp),
_z, IF(
num < _i ^ 2,
HSTACK(_t, num),
IF(
MOD(num, _i) = 0,
Factor2(num / _i, _i, HSTACK(_t, _i)),
Factor2(num, IF(_i <= 2, 3, _i + 2), _t)
)
),
FILTER(_z, _z > 1)
)前回、Labsをキャプチャーして張り付けたところ、スマホで見たら小さくて読みづらかったので、今回はこんな感じにしてみます。どうかな？
この関数は、割る数「 _i 」を２→３→５→７→９→・・・と大きくしながら割り算を繰り返していき、商が「 _i^2 」より小さくなったときに計算を終了します。なので、素数を計算する際の繰り返し数が多くなります。
例えば、「 101 」を計算する場合を考えましょう。
最初は「 _i = 2 」から始まります。２→３→５→７→９と割れずに繰り返し、「 11 」になったところで「 101 < 11^2 = 121 」となるので計算を終了します。この場合繰り返し回数は、５回です。
これは、INT ( SQRT( 101 ) ) / 2 = 5 で求めることができます。
次に「 102 」の場合を見てみます。
「 _i = 2 」で早速割れて、商が「 51 」となります。
再び「 2 」で割ろうとしますが割れないので「 3 」に繰り上がります。
またうまく割れて、商が「 17 」となります。
再び「 3 」で割ろうとしますが割れないので「 5 」に繰り上がります。
しかし、「 17 < 5^2 = 25 」なので計算終了です。
結局、2→2→3→3と４回の繰り返しになりました。
何が言いたいかというと、大きな素数ほど繰り返し回数(Lambda Depth)が多くなって計算できなくなるということです。
前回は、「 2^31 - 1 」でエラーになりました。
しかし、「 2^40 - 1」は計算できています。
これは「 2^31 - 1 」が素数なのが原因だったのです。
では、実際何回転ぐらいできるのか調べてみました。
検証の結果、「 21,893,041 」で最初のエラーが出ました。
繰り返し回数は「 2340 」ですね。
高々2000強でお亡くなりになるなんて…ザコすぎませんか？Excelさん。残念です。
ついでに、もっと単純なコードならどのくらい回るのか調べてみました。
使用した関数はこちら。
FuncName : LoopTest
Discription : シンプルなコードでどこまで潜れるかテスト
Argments : num, [i]
Function definition :
=LET(
_i, IF(ISOMITTED(i), 1, i),
IF(
_i > num,
num,
LoopTest(num, _i + 1)
)
)引数「 num 」の値まで、１から足し算を繰り返すだけの関数です。
こちらで検証した結果がこれ。
「 4095 」でお亡くなりになったということは、4096回目でダメになったということですね。２の12乗とはなんとも意味ありげな数字ですが、そんなことよりなんとも残念な結果・・・。せっかく再帰が使えるのに遊んでる人が少ないわけだ。
REDUCE関数を使ってみる
さて、新しいExcelの関数では、再帰以外にもループ処理をする方法があります。そう、REDUCE関数です。LAMBDAヘルパー関数とか呼ばれてますね。
「はてなブログ」でREDUCE関数を使って素因数分解をされている方がいらっしゃいました。ここにリンクを貼っておきます。
この方のコードをまるまるコピーして、名前定義したのがこちらです。
FuncName : Factor1
Discription : 素因数分解。REDUCE関数でlog2(num)回繰り返す。
Argments : num
Function definition :
=LET(
_x, REDUCE(
HSTACK(1, num),
SEQUENCE(LOG(num, 2)),
LAMBDA(_a, _b,
LET(
_c, CHOOSECOLS(_a, -1),
_d, SEQUENCE(SQRT(num), , 2),
_e, MIN(FILTER(_d, MOD(_c, _d) = 0, _c)),
HSTACK(TAKE(_a, , _b), _e, _c / _e)
)
)
),
FILTER(_x, _x > 1)
)なにやら複雑なコードです。
これを一目見て何やっているか理解できる人はちょっと変態だと思います。いい意味で。
さて、お気づきになったでしょうか。
そうです、関数名が「 Factor1 」ですね。「 1 」なのです。
私が最初に作ってみた関数がこちらでした。
人様のコードなので、説明はしませんが、この関数はとても優秀です。
試しにメルセンヌ数を素因数分解してみましょう。
なんと、「 2^40 - 1 」まで余すことなく因数分解できてます。
「 2^41 - 1 」以降は#VALUE!エラーになっていますが、これはLambda Depthとは別の問題です。後ほど説明します。
ここまでできるならもうこれでいいじゃん！となりそうですが、そうは問屋が卸しません。
この関数、実はとても重いのです。
試しに次のような関数を使って処理時間を比べてみます。
FuncName : TCount1
Discription : 関数の処理時間を測る
Argments : x
Function definition :
=LET(
_t1, NOW(),
_x, Factor1(x),
_t2, NOW(),
_t3, TEXT(_t2 - _t1, "s.000") & "sec",
HSTACK(_t3, _x)
)簡単に説明しますと、
①NOW関数で現在時刻を取得
②Factor1関数で素因数分解の処理
③再度NOW関数で現在時刻取得
④ ①と③の差分を計算
⑤経過時間と素因数分解の結果をくっつけて返す
この関数をFactor2版も作って「 2^40 - 1 」で試した結果がこちら。
なんとFactor2関数が一瞬で処理しているのに対し、Factor1関数は５秒もかかっています。
Factor1関数は、SQRT(num)個の配列を除数として、FILTER関数にてnumが割れるかチェックしています。
そしてそれをLog(num,2)回繰り返しています。
例えば、「 102 」の場合、
①SEQUENCE( LOG( 102, 2 ) ) ⇒ { 1, 2, 3, 4, 5, 6 }
②SEQUENCE( SQRT( 102 ), , 2 ) ⇒ { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
となります。
①が６回、②が10回ですね。
②の配列で毎回MOD計算をしていますので、合計60回のMOD計算をしていることになります。
それに対し、Factor2関数では、上で数えたように４回しかMOD計算をしていません。
これが圧倒的な計算速度の差になっています。
再帰とFILTER関数の合わせ技
さて、なんとかFactor1関数を早くできないかと考えて、考えて、考えて・・・、FILTER関数と再帰を組み合わせる案を思いつきました。
FuncName : Factor3
Discription : 因数分解。FILTER関数で最大素因数を求め、分岐しながら再帰ループ。
Argments : num
Function definition :
=LET(
_n, num,
_s, SEQUENCE(SQRT(_n), , 2),
_d, ***********************,
_q, _n / _d,
_n1, IF(******, Factor3(_d), _d),
_n2, IF(******, Factor3(_q), _q),
_z1, HSTACK(_n1, _n2),
_z2, FILTER(_z1, _z1 > 1, 1),
_z3, SORT(_z2, , 1, TRUE),
_z3
)コードの一部を目隠しさせていただきました。
何が入るか想像してみてください。
（FILTERって言ってるのだからどこかには入るのでしょう）
このFactor3関数を動かした結果がこちら。
無事に「 2^40 - 1 」まで素因数分解できています。
では、速度はどうでしょうか？
「 2^30 -1 」「 2^34 -1 」「 2^40 -1 」の３つで比べたところ、Factor2関数が圧倒的に早いのは変わりませんが、Factor3関数でもFactor1関数の10～30倍ぐらい早いことがわかりました。
なんとか改良できたようです。
2＾41の壁
しかし、Factor3でも「 2^41 」の壁は超えられませんでした。
実際どこからエラーになるかを調べてみると、
「 1,099,513,724,929 」だということが分かります。
なぜここが限界値なのかというと、答えは左隣りの数値にあります。
「 1,048,577 」というと何の変哲もなさそうな数字ですが、その上の「 1,048,576 」は「 2＾20 」という切りのよい数字になっています。
そして、この数値はExcelのSheetの最大行数です。
つまり、
SEQUENCE( SQRT( _n ), , 2 ) ⇒ { 2, 3, 4, 5, 6,・・・, 1048577, 1048578 }
という配列は、Excelの最大行数を超過する為、作れない！というわけです。
こんなところまでSheetに依存してしまうのがExcelの残念なところです。
この壁を乗り越えるスマートなコードはまだ思いつかないため、今回はここまでですね。
もし、よい案を思いついた方がいらっしゃったら、ぜひコメントで教えてください。
答え合わせと解説
それでは、Factor3関数の答え合わせです。
と、言いたいところなのですが、せっかくの初投稿なので、ここからは有料にしてみたいと思います。
続きが気になるかたはぜひ最後までどうぞ！
ここから先は
1月10日 00:00 〜 2月9日 00:00
この記事が気に入ったらチップで応援してみませんか？