我不认为 C# 的数据类型具有足够的浮点精度和范围来天真地处理这个问题。
如果你真的想走这条路,你会注意到共轭
小于一,所以
与四舍五入到最接近的整数相同,因此你可以简化你的解决方案来找到
. 然后使用二项式展开,这样您只需
用适当的 a和b计算(它们是有理的,可以用 BigInteger 精确计算)。如果你仍然为此返回 Double,你仍然不会比 1475 更进一步,但你应该能够仅用精确的整数数学计算出如何完成这部分 ☺</p>

还有另一种计算斐波那契数的巧妙方法,使用矩阵求幂:

如果你很聪明,这可以在 O(log n) 中完成。
我最终在 Haskell 中实现了这些。 fib1
是矩阵求幂并且fib2
是闭合形式公式的精确整数转换,如上所述。它们各自的运行时如下所示,由GHC 7.0.3编译时由Criterion测量:
import Control.Arrow
import Data.List
import Data.Ratio
newtype Matrix2 a = Matrix2 (a, a, a, a) deriving (Show, Eq)
instance (Num a) => Num (Matrix2 a) where
Matrix2 (a, b, c, d) * Matrix2 (e, f, g, h) =
Matrix2 (a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h)
fromInteger x = let y = fromInteger x in Matrix2 (y, 0, 0, y)
fib1 n = let Matrix2 (_, x, _, _) = Matrix2 (1, 1, 1, 0) ^ n in x
binom n =
scanl (\a (b, c)-> a*b `div` c) 1 $
takeWhile ((/=) 0 . fst) $ iterate (pred *** succ) (n, 1)
evens (x:_:xs) = x : evens xs
evens xs = xs
odds (_:x:xs) = x : odds xs
odds _ = []
iterate' f x = x : (iterate' f $! f x)
powers b = iterate' (b *) 1
esqrt e n = x where
(_, x):_ = dropWhile ((<=) e . abs . uncurry (-)) $ zip trials (tail trials)
trials = iterate (\x -> (x + n / x) / 2) n
fib' n = (a, b) where
d = 2 ^ n
a = sum (zipWith (*) (odds $ binom n) (powers 5)) % d
b = sum (zipWith (*) (evens $ binom n) (powers 5)) % d
fib2 n = numerator r `div` denominator r where
(a, b) = fib' n
l = lcm (denominator a) (denominator a)
r = a + esqrt (1 % max 3 l) (b * b / 5) + 1 % 2