まじめに計算してはいけません

これはprojecteulerにおける鉄則（だと思う）
例えば、Problem104なんだけど、調子に乗ってgmpのfib関数を使ったら、終わらないのなんのって。
いくら高速なルーチンとはいえ、（この場合）全桁必要ではないのだから、そこまで計算する必要はない。

許容可能な範囲で計算（努力？！）を省くというのは実世界でも有用なテクニックなんだろう。
ただ、問題はその範囲を見極めることがそう簡単ではないということと、
どういう風に影響なく省くかがよく分からんことにあるのだけど。

試しにgmpのfibを使って先頭、末尾を取り出してチェックしたのだけど、冒頭で書いたように、
そうそう終わらない。（例題のは一瞬で出せるのだけど）
仕方がないので速くなるかどうかは疑問だったけど、後半10ケタ「のみ」を実直に計算することにした
（最高でも10ケタしか演算しないので、猛烈に遅くなることはないと踏んだ）

まじめに計測してないけど、桁数が多くなればなるほどgmpより速くなるっぽい。
（というか、桁数が文字通り爆発するfibにおいては圧倒的に不利ではあるのだけど。
その不利な条件下で健闘するgmpはほんと、すばらしい）

ただ、頭10ケタ（のみを取り出す）のはいい手を思いつかなかったので、ここにはgmpを使った。
（後半10ケタが条件を満たす場合のみgmpでfibを計算して頭の桁をチェックすることにした）

これでもまだ速くなる余地はあるんだろうけど、まぁ、何とか実用時間内かと

指数・対数をごにょごにょすると頭10ケタも出せるような話もあったのだけど、これはよく分かってない。
（先頭1-2ケタならまだしも）
これなら圧倒的に速い

余談っぽいのだけど、末尾の桁が欲しいのであれば、文字列変換してスライスで切り出すよりも
mod使って計算する方が圧倒的に速いとか、ここから学べることはいくらでもある。
この辺りがコンピュータサイエンスの醍醐味なのかも。
って、これはコンピュータサイエンス系の正式な教育を受けてない人間のひがみなのかも？
もっとも、そんなまともな教育が当時、可能だったのかという話もある。（慶応SFC辺りだと違ったかな？）
とはいえ、21世紀になってしばらく経ってはいるけど、劇的に改善したとは思えないんだけどね。

ps
末尾10ケタを手に入れようと思ったら、定義どおりの実装をして適宜10**9のmodをとるのが一番速そう。
時と場合によっては原点回帰も必要、と。
（gmpのfib関数しか知らなかったらこの手法はおそらく使えない）