剰余(3)

おさらい:
最初の方法をmethod1、もう一つの方法をmethod2と呼ぶことにする。
除数が大きいときmethod2のほうが効率がよい。
除数が小さいときmethod1のほうが効率がよい。


だから、どちらの方法を使ったほうがいいか、
除数の大きさで決まりそうである。
これ以上だったらmethod2を使ったらいいという境界がありそう。
それを求める。


変数は0〜e2-1まで取れて、
a : a2e2 + a1e + a0
b : b1e + b0
と書けるとする。

method1は、
e2 % b 〜 b/2程度(最大b)
だから、1回の操作でb/(2e2)倍程度になる。


method2は、
(a2e + a1)(e - b / (b1 + 1))
〜 a/(4b)程度(最大a/b)
だから、1回の操作でe/(4b)倍程度になる。


b/(2e2) = e/(4b)
を解いて、
b = 2-1/2e3/2


まあ、b = e3/2 が境界と考えてよいだろう。
これだと、ちゃんと検証していないけれど、2回で済みそうだ。
すなわち、ループを使わなくて済み、インライン化できる。
インライン化でどの程度スピードアップするかわからないが。


本当はもっといいアルゴリズムがあるのだろうけど、
見たことがない。