1 public static BigInteger fib(int n)
 2 {
 3     Console.WriteLine(n);  // 打印輸入的參數(shù)n，用于調(diào)試
 4 
 5     BigInteger semn = 1;  // 定義一個(gè)BigInteger類型的變量semn，用于存儲(chǔ)符號
 6     BigInteger t = 0;  // 定義BigInteger類型的變量t，用于臨時(shí)存儲(chǔ)中間計(jì)算結(jié)果
 7     BigInteger i = 1;  // 定義BigInteger類型的變量i，初始化為1
 8     BigInteger j = 0;  // 定義BigInteger類型的變量j，初始化為0
 9     BigInteger k = 0;  // 定義BigInteger類型的變量k，初始化為0
10     BigInteger h = 1;  // 定義BigInteger類型的變量h，初始化為1
11 
12     if (n < 0)  // 如果n小于0，表示需要計(jì)算負(fù)數(shù)的斐波那契數(shù)
13     {
14         n *= -1;  // 將n取絕對值
15         semn = n % 2 == 0 ? -1 : 1;  // 判斷n的絕對值是否為偶數(shù)，如果是偶數(shù)，semn為-1，否則為1
16     }
17 
18     while (n > 0)  // 當(dāng)n大于0時(shí)，進(jìn)行循環(huán)計(jì)算斐波那契數(shù)
19     {
20         if (n % 2 != 0)  // 如果n是奇數(shù)
21         {
22             t = j * h;  // 計(jì)算j乘以h的結(jié)果，并賦值給t
23             j = i * h + j * k + t;  // 更新j的值，根據(jù)斐波那契數(shù)列的遞推公式計(jì)算
24             i = i * k + t;  // 更新i的值，根據(jù)斐波那契數(shù)列的遞推公式計(jì)算
25         }
26         t = h * h;  // 計(jì)算h的平方，并賦值給t
27         h = 2 * k * h + t;  // 更新h的值，根據(jù)斐波那契數(shù)列的遞推公式計(jì)算
28         k = k * k + t;  // 更新k的值，根據(jù)斐波那契數(shù)列的遞推公式計(jì)算
29         n = n / 2;  // 將n除以2，用于控制循環(huán)次數(shù)
30     }
31 
32     return j * semn;  // 返回計(jì)算得到的斐波那契數(shù)乘以符號semn，得到最終結(jié)果
33 }

 1 using NUnit.Framework;
 2 using System;
 3 using System.Collections.Generic;
 4 using System.Numerics;
 5 
 6 public class FibonacciTest
 7 {
 8 
 9     [Test]
10     public void testFib()
11     {
12         List<int> tests = new List<int> { 0, 1, 2, 3, 4, 5, -6, -96, 1000, 1001 };
13 
14         Random rnd = new Random();
15         for (int i = 0; i < 10; ++i)
16         {
17             tests.Add(rnd.Next(-100, 0));
18         }
19         tests.Add(rnd.Next(10000, 100000));
20         tests.Add(rnd.Next(1000000, 1500000));
21 
22         foreach (int n in tests)
23         {
24             BigInteger found = Fibonacci.fib(n);
25             Assert.AreEqual(FibonacciRef.fib(n), found);
26         }
27     }
28     
29     private static class FibonacciRef
30     {
31         private static IDictionary<int, BigInteger> fibs = new Dictionary<int, BigInteger>();
32 
33         static FibonacciRef()
34         {
35             fibs[0] = BigInteger.Zero;
36             fibs[1] = BigInteger.One;
37             fibs[2] = BigInteger.One;
38             fibs[3] = fibs[2] + fibs[1];
39             fibs[4] = fibs[3] + fibs[2];
40             fibs[5] = fibs[4] + fibs[3];
41         }
42 
43         private static BigInteger calcFib(int n)
44         {
45             BigInteger result;
46             if (fibs.TryGetValue(n, out result))
47                 return result;
48 
49             if ((n & 1) == 1)
50             {
51 
52                 int k = (n + 1) / 2;
53                 BigInteger fk = BigInteger.Pow(calcFib(k), 2);
54                 BigInteger fkm1 = BigInteger.Pow(calcFib(k - 1), 2);
55                 result = fk + fkm1;
56             }
57             else
58             {
59                 int k = n / 2;
60                 BigInteger fk = calcFib(k);
61                 BigInteger fkm1 = calcFib(k - 1);
62                 result = (fkm1 * fibs[3] + fk) * fk;
63             }
64 
65             fibs[n] = result;
66             return result;
67         }
68 
69         public static BigInteger fib(int n)
70         {
71             bool neg = n < 0;
72 
73             if (neg)
74                 n = -n;
75 
76             BigInteger result = calcFib(n);
77 
78             if (neg && (n & 1) == 0)
79                 result = -result;
80 
81             return result;
82         }
83     }
84 }