地獄のフィボナッチ数列@Python

誰か助けてください．

できごと

とあるプログラミング勉強用の問題を出すサイトにて（サイト名は言うと問題のネタバレになりかねないので秘密だよ）フィボナッチ数列の実装を求められたよ

序章

ぼく「これ簡単やな！＾＾」

fib1

def fib(seq):
    if seq == 0:
        return 0
    if seq == 1:
        return 1
    return fib(seq-1) + fib(seq-2) 

エラー発生
ぼく「どこがおかしいんだ？」

テスト内容
fib(1000) fib(-36)
ぼく「??????????????????????????????」

ちょっと調べた

ワイ「負数への拡張はこうやるのか，LRUキャッシュか，これ使えばいけそうやな」

fib2

from functools import lru_cache

@lru_cache(maxsize=10000000)
def fib(seq):
    if seq == 0:
        return 0
    if seq == 1:
        return 1
    tmp = (fib(abs(seq)-1) + fib(abs(seq)-2)) 
    
    if seq < -1:
        tmp *= (-1)**(abs(seq)+1)
    return tmp

エラー発生：RecursionError: maximum recursion depth exceeded
ぼく「ん，何これ？」
問題文を確認したら，
問題文「nが2000000まで扱えるようなアルゴリズムを書きなさい。」

ぼく「…馬鹿じゃねえの？」

迷走

import sys からのsys.setrecursionlimit()を調整したらsegmentation faultを起こしたのでこれではダメそう

korehadame

from functools import lru_cache
import sys

sys.setrecursionlimit(50000)


@lru_cache(maxsize=10000000)
def fib(seq):
    if seq == 0:
        return 0
    if seq == 1:
        return 1
    tmp = fib(abs(seq) - 1) + fib(abs(seq) - 2)

    if seq < -1:
        tmp *= (-1) ** (abs(seq) + 1)
    return tmp


fib(80000)

手元での出力結果

Segmentation fault 

光明

再帰的処理には無理があろうと思われますと感じたので，ループ処理の実装例に切り替える

Kwangmyong

from functools import lru_cache


@lru_cache(maxsize=10000000)
def fib(seq):
    a, b = 0, 1
    if seq == 0:
        return a
    elif abs(seq) == 1:
        result = b
    else:
        for j in range(abs(seq) - 1):
            a, b = b, a + b
        result = b

    if seq > 0:
        return result
    else:
        return result * (-1) ** (abs(seq) + 1)

手元では動作
ぼく「お，これいけるんとちゃうか？」
提出結果:Execution Timed Out (12000 ms)
ぼく「」

解決

O(n)のアルゴリズムでは無理そうなのでO(logn)のアルゴリズムを考えたがぼくの低レベルな脳みそでは考えつかなかったので調べる．

するとこのような法則があるらしい．（参考サイト）

Method 6 (O(Log n) Time)
もう一つ、フィボナッチ数nをO(Log n)時間で求めることができる面白い漸化式を紹介します。
nが偶数の場合，k = n/2として，Fib(n) = [2*Fib(k-1) + Fib(k)]*Fib(k)
nが奇数の場合，k = (n + 1)/2として，F(n) = F(k)*F(k) + F(k-1)*F(k-1)

これを実装してみる

Final

from functools import lru_cache


@lru_cache(maxsize=10000000)
def fib(seq):
    a, b = 0, 1
    if seq == 0:
        return a
    elif abs(seq) == 1:
        result = b
    else:
        if abs(seq) % 2 == 0:
            k = abs(seq) / 2
            result = ((2 * fib(k - 1)) + fib(k)) * fib(k)
        else:
            k = (abs(seq) + 1) / 2
            result = fib(k) * fib(k) + fib(k - 1) * fib(k - 1)

    if seq > 0:
        return result
    else:
        return result * (-1) ** (abs(seq) + 1)

無事にテスト突破！やったぜ！

〆

アルゴリズムのオーダーって大事，ほんとに痛感した…