Расчет фибоначчи

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), если вы умны.

---

В итоге я реализовал их на Хаскеле. fib1 - матричное возведение в степень, а fib2 - точное целочисленное преобразование формулы в замкнутой форме, как описано выше. Их время выполнения выглядит следующим образом, как измерено Критерием при компиляции с помощью GHC 7.0.3 :

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;
    }
}

Answer 3

Тип данных Double имеет верхний предел значения 1,7 x 10 ^ 308

. Расчет для 1474 включает значение ~ 1,1 x 10 ^ 308 за один шаг.

Итак,к 1475 вы определенно превзойдете то, что может представлять Double.К сожалению, единственный более крупный примитив C #, Decimal (128-битное число), имеет очень высокую прецессию, но с относительно небольшим диапазоном (только до 10 ^ 28).

Без разработки пользовательского типа данных, которыйможет обрабатывать числа больше 10 ^ 308 с некоторой степенью десятичной точности, я не вижу способа сделать это.Тем не менее, кто-то там, возможно, уже создал такой класс, так как я могу представить себе сценарии, где он может пригодиться.

См. Double: http://msdn.microsoft.com/en-us/library/678hzkk9(v=VS.80).aspx

и десятичное число: http://msdn.microsoft.com/en-us/library/364x0z75(v=VS.80).aspx

Answer 4

Библиотека 'Solver Foundation' , по-видимому, включает некоторые типы «больших» чисел. Возможно, тип Rational обеспечит вам точность и дальность, которые вам нужны. Он представляет собой рациональное соотношение двух BigInteger значений. (Он приносит свой собственный BigInteger - я думаю, он был написан до поставки .NET 4.)

Теоретически, это позволяет ему представлять очень большие числа, но также и представлять большую точность. (Очевидно, что ваша формула не имеет отношения к рациональным, но с плавающей точкой здесь также приближение.)

Он предлагает метод возведения Rational в силу чего-то другого: http://msdn.microsoft.com/en-us/library/microsoft.solverfoundation.common.rational.power(v=VS.93).aspx

Answer 5

Самый быстрый (и самый грязный)? : D

private Double dirty_math_function(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);
 }

private Double FibSequence(Int32 input) {
  if(input < 1475)
       return dirty_math_function(input);
  else{
       return (FibSequence(input -1) + FibSequence(intput -2));
  }
}

Answer 6

Многие ответы здесь предполагают, что сложность может быть минимизирована до O (log (n)).Почему бы не попробовать целочисленную реализацию подхода log (n)?

Во-первых, учтите, что вам даны два термина из последовательности Фибоначчи: F(n) и F(n+1).Логично, что большие члены F(n+k) можно записать в виде линейной функции от F(n) и F(n+1) как

 F(n+k) = Ck1*F(n) + Ck2*F(n+1)

Вы можете просто вычислить эти коэффициенты (которые будут зависеть только от k), (что интересно, они тоже являются последовательностью Фибоначчи!) и используют их для ускорения продвижения, затем снова вычисляют их для больших значений k, чтобы иметь возможность продвигаться еще быстрее, и так далее.

Answer 7

Как вы правильно указали, для BigInteger не реализован метод Sqrt.Вы можете реализовать это самостоятельно, хотя:

Вычислить квадратный корень из BigInteger (System.Numerics.BigInteger)

Хотя точность все равно должна быть проблемой для вашего кода.

Answer 8

1. Это не точная формула, она даст вам только приблизительное значение.А поскольку арифметика с плавающей точкой ограничена 6-8 байтами на число, отклонение будет увеличиваться с увеличением числа.Гораздо лучше, чем с плавающей точкой.

Answer 9

проблема в том, что (5 ^ (1/2) ^ 1475) легко переполняется int.Что вам нужно сделать, так это написать «большую математическую» библиотеку для обработки математических операций из памяти (бит за битой), а не использования жестко типизированных типов данныхэто боль в но, я знаю.Посмотрите на квадрат и умножьте метод.