別搗蛋

#!/usr/bin/perl

# 使用遞迴方法 (recursive) - 速度慢
# 輸入 : 整數 n
# 輸出 : 費波那契數
sub fibonacci {
    my $n = shift;
    return 0 if ($n==0);
    return 1 if ($n==1);
    return fibonacci($n+2) - fibonacci($n+1) if ($n<0);
    return fibonacci($n-1) + fibonacci($n-2);
}

# 使用疊代方法 (iterative) - 速度快
# 輸入 : 整數 n
# 輸出 : 費波那契數
sub fibonacci_i {
    my $n = shift;
    my (@fib, $i, $neg);

    $neg = 0;
    if ($n<0) {
        $n = abs($n);
        $neg = 1;
    }

    $fib[0] = 0;
    $fib[1] = 1;
    for ($i=2;$i<=$n;$i++) {
        $fib[$i] = $fib[$i-1] + $fib[$i-2];
    }
    return (-1)**($n+1)*$fib[$n] if ($neg);
    return $fib[$n];
}

# 上面程式以自家電腦執行發現
# F₇₄ 之後以科學記號顯示
# F₁₄₇₇ 之後溢位無法計算

---

# 使用大數模組 (package)
# 輸入 : 整數 n
# 輸出 : 費波那契數
use Math::BigInt;
sub fibonacci_p {
    my $n = shift;
    my (@fib, $i, $neg, $temp);

    $neg = 0;
    if ($n<0) {
        $n = abs($n);
        $neg = 1;
    }

    $fib[0] = 0;
    $fib[1] = 1;
    for ($i=2;$i<=$n;$i++) {
        $temp = Math::BigInt->new($fib[$i-1]);
        $temp = $temp->badd($fib[$i-2]);
        $fib[$i] = $temp;
    }
    if ($neg) {
        $temp = Math::BigInt->new(-1);
        $temp = $temp->bpow($n+1);
        return $temp*$fib[$n];
    }
    return $fib[$n];
}