计算斐波那契

Question

我发送了这个非常好的非递归函数来计算斐波纳契数列.

所以我编写了一些c#并且能够验证所有高达1474的数字是否正确.

尝试计算1475及以上时会出现问题.我的c#数学技能不能达到找出不同方法的任务.那么,有人有更好的方法在c#中表达这个特定的数学函数吗？除了传统的递归函数方式？

顺便说一句,我开始使用BigInteger作为返回类型.但是当试图将(1 + Math.Sqrt(5)/ 2)提升到1475次幂时,问题确实存在.我只是没有看到我需要什么样的数据类型(也没有这个问题的机制)来让它回归到Infinity以外的东西.

这是一个起点.

private Double FibSequence(Int32 input) {
    Double part1 = (1 / Math.Sqrt(5));
    Double part2 = Math.Pow(((1 + Math.Sqrt(5)) / 2), input);
    Double part3 = Math.Pow(((1 - Math.Sqrt(5)) / 2), input);

    return (part1 * part2) - (part1 * part3);
}

而且,不,这不是功课.对于缓慢的一天来说只是一个"简单"的问题.

Answer 1

我不认为C#有一个具有足够浮动精度和范围的数据类型来处理这个天真的问题.

如果你真的想沿着这条路走下去,你可以注意到这个共轭 不到一个,所以 与舍入到最接近的整数相同,因此您可以简化您的查找解决方案 .然后使用二项式扩展,这样你只需要计算,使用适当的a和b(这是合理的,可以使用BigInteger精确计算).如果你仍然回到Double这个,你仍然不会比1475更远,但你应该能够弄清楚如何做这个部分只有精确的整数数学☺

还有另一种利用矩阵求幂来计算斐波那契数的简洁方法:

如果你聪明的话,这可以在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

Answer 2

using System;
using Nat = System.Numerics.BigInteger; // needs a reference to System.Numerics

class Program
{
    static void Main()
    {
        Console.WriteLine(Fibonacci(1000));
    }

    static Nat Fibonacci(Nat n)
    {
        if (n == 0) return 0;
        Nat _, fibonacci = MatrixPower(1, 1, 1, 0, Nat.Abs(n) - 1, out _, out _, out _);
        return n < 0 && n.IsEven ? -fibonacci : fibonacci;
    }

    /// <summary>Calculates matrix power B = A^n of a 2x2 matrix.</summary>
    /// <returns>b11</returns>
    static Nat MatrixPower(
        Nat a11, Nat a12, Nat a21, Nat a22, Nat n,
        out Nat b12, out Nat b21, out Nat b22)
    {
        if (n == 0)
        {
            b12 = b21 = 0; return b22 = 1;
        }

        Nat c12, c21, c22, c11 = MatrixPower(
            a11, a12, a21, a22,
            n.IsEven ? n / 2 : n - 1,
            out c12, out c21, out c22);

        if (n.IsEven)
        {
            a11 = c11; a12 = c12; a21 = c21; a22 = c22;
        }

        b12 = c11 * a12 + c12 * a22;
        b21 = c21 * a11 + c22 * a21;
        b22 = c21 * a12 + c22 * a22;
        return c11 * a11 + c12 * a21;
    }
}