斐波那契数列

复制import sys
sys.set_int_max_str_digits(100000)  # 允许打印大数字符串

def fib(n: int) -> int:
    """返回第 n 个斐波那契数（n>=0），使用快速倍增法，O(log n)"""
    if n < 0:
        raise ValueError("n must be >= 0")
    if n == 0:
        return 0
    # 快速倍增：F(2k) = F(k)*(2*F(k+1)-F(k))
    #          F(2k+1) = F(k+1)^2 + F(k)^2
    def fib_pair(k: int):
        if k == 0:
            return (0, 1)
        a, b = fib_pair(k >> 1)
        c = a * (2 * b - a)
        d = a * a + b * b
        if k & 1:
            return (d, c + d)
        else:
            return (c, d)
    return fib_pair(n)[0]

# 示例：第 100 项（大数）
print(fib(100))  # 354224848179261915075

# 示例：黄金比近似（F(n+1)/F(n)）
print(fib(101) / fib(100))  # 1.618033988749895

复制package main

import (
	"fmt"
	"math/big"
)

// Fib 返回第 n 个斐波那契数（n>=0），使用快速倍增法，O(log n)
func Fib(n int) *big.Int {
	if n < 0 {
		panic("n must be >= 0")
	}
	if n == 0 {
		return big.NewInt(0)
	}
	var fibPair func(k int) (*big.Int, *big.Int)
	fibPair = func(k int) (*big.Int, *big.Int) {
		if k == 0 {
			return big.NewInt(0), big.NewInt(1)
		}
		a, b := fibPair(k >> 1)
		// c = a * (2*b - a)
		twoB := new(big.Int).Mul(big.NewInt(2), b)
		twoB.Sub(twoB, a)
		c := new(big.Int).Mul(a, twoB)
		// d = a^2 + b^2
		a2 := new(big.Int).Mul(a, a)
		b2 := new(big.Int).Mul(b, b)
		d := new(big.Int).Add(a2, b2)
		if k&1 == 1 {
			return d, new(big.Int).Add(c, d)
		}
		return c, d
	}
	res, _ := fibPair(n)
	return res
}

func main() {
	// 示例：第 100 项
	fmt.Println(Fib(100)) // 354224848179261915075

	// 示例：黄金比近似（F(101)/F(100)）
	f100 := Fib(100)
	f101 := Fib(101)
	phi := new(big.Rat).SetFrac(f101, f100)
	phiFloat, _ := phi.Float64()
	fmt.Printf("%.15f\n", phiFloat) // 1.618033988749895
}

复制// 快速倍增法计算第 n 个斐波那契数（n>=0），O(log n)
function fib(n) {
  if (n < 0) throw new Error('n must be >= 0');
  if (n === 0) return 0n;

  function fibPair(k) {
    if (k === 0) return [0n, 1n];
    const [a, b] = fibPair(k >> 1);
    const c = a * (2n * b - a);
    const d = a * a + b * b;
    if (k & 1) return [d, c + d];
    return [c, d];
  }

  return fibPair(n)[0];
}

// 示例：第 100 项（BigInt 支持任意大数）
console.log(fib(100).toString()); // 354224848179261915075

// 示例：黄金比近似（F(101)/F(100)）
const f100 = fib(100);
const f101 = fib(101);
const phi = Number(f101) / Number(f100);
console.log(phi); // 1.618033988749895