5 способов вычисления чисел Фибоначчи: реализация и сравнение

[SLY_G]

Пусть меня поправят математики через личные сообщения, поскольку в последнем абзаце начался такой математический угар, что русскоязычных аналогов некоторых терминов я просто не нашёл.

[kahi4]

Использование комплексных чисел для вычисления Fn красиво с математической точки зрения, но уродливо — с компьютерной.

Где вы там комплексные числа то нашли? В том плане, что функция может применяться к комплексным числам (как и к не целым, в этом её большое преимущество, которое, почему-то опущено), но для вычисления i-того номера комплексные числа не нужны.

P.S. Мне кажется, что это 4-ая статья с одними и теми же методами на хабре. Я уж молчу, что они все есть на вики.

[namespace]

О чем статья?

[Tuxman]

О том, как отвечать на один из вопросов на интервью. К сожалению, есть места где такое спрашивают. Встречаются вариации, например, вывести список простых чисел.

[nickolaym]

Поскольку тип результата — int, то достаточно сделать табличную реализацию первых 48 или 94 чисел. Ибо вотще.

[tenzink]

Вариант 6 (небольшое развитие матричного)
F_{2n+1} = F_n^2 + F_{n+1}^2
F_{2n} = F_n (2F_{n+1} — F_n)

вместо матрицы 2x2, используется пара

[VenomBlood]

Хорошее:
Фиксированный объём памяти, логарифмическое время

Ну сколько же можно. Где там логарифмическое время? Ну невозможно умножать за логарифмическое время. Длина байтового представления n-го числа Фиббоначи растет линейно. В uint64 влезет 93е (если не ошибаюсь) число фиббоначи, кешируется все это в 0.7Кб, т.е. на практике сложность или константная (если нам надо числа до определенного) или уж никак ни логарифмическая, коли даже битовое представление числа уже линейно растет, не говоря уже про умножение.

Тем, что возведение в степень можно произвести за логарифмическое время.

То что работает в рамках 64 битных регистров нельзя переносить на большие числа. Правильнее было бы сказать что в целую степень можно возвести за логарифмическое количество умножений.

[VladX]

Всё верно. Можно выкрутиться, и сказать, что мы вычисляем N-ное число по модулю M (где модуль M фиксирован и не зависит от N). Тогда действительно будет O(log N). Обычно этот способ и применяется для вычисления по модулю. Для предложенной автором реализации сложность будет примерно такая: сложение двух полиномов за O(N), возведение в квадрат за O(N log N); итераций алгоритма O(log N); тогда итоговая сложность будет O(N log N) для матриц и O(N^2) для тупого алгоритма. У обоих O(N) памяти.
Для оценки первого я пользовался этим:

[sci_nov]

Кстати, код в параграфе «Динамическое программирование» прямо реализуется рекурсивным цифровым фильтром с двумя ячейками памяти: просто и естественно.

[sashagil]

Капитан Очевидность (TL;DR): матричный вариант всех ест с хрустом на завтрак. Господа, матрицы не причём, вопрос в том, используется возможность человеческого мозга абстрагировть, или нет.

[dyadyaSerezha]

1. Не увидел, что там динамического в «динамическом программировании» по сравнению с другими вариантами.

2. В начале статьи все же хотелось бы примеров, где, когда и каких порядков числа Фибоначи нужны в реальных задачах. Иначе все в n-ый выглядит как «динамически» высосанное из пальца.

[VladX]

То же на Haskell по модулю 2^32, но с упрощенными формулами

fib 0 = 0
fib 1 = 1
fib nn = if even nn
	then let n = div nn 2 in
		(2 * fib (n - 1) + fib n) * fib n
	else let n = div (nn+1) 2 in
		fib n ^ 2 + fib (n-1) ^ 2

К сожалению, в Haskell нет встроенной длинной арифметики. Сложность вычисления сильно зависит от реализации длинной арифметики. Можно и быстрее, чем за O(N).

[nickolaym]

Как это в хаскеле нет встроенной длинной арифметики? Тип Integer разве не оно?

[VladX]

Значит с Integer будет то же самое, а с Int по модулю. Не суть.

[vba]

Не могли бы вы перевести предпоследний вариант в java подобный язык а то я с питоном не в ладах. Заранее спасибо.

[PsyHaSTe]

Мой старый вариант, есть куда улучшать, но идею демонстрирует:

using System;
using System.Diagnostics;
using System.Numerics;
 
namespace ConsoleApplication1
{
    class Program
    {
        public static BigInteger Fib(BigInteger n)
        {
            if (n < 0)
                throw new ArgumentException("The fibo value cannot be negative");
            if (n <= 1) 
                return n;
 
            BigInteger[,] result = { { 1, 0 }, { 0, 1 } };
            BigInteger[,] fiboM = { { 1, 1 }, { 1, 0 } };
 
            while (n > 0)
            {
                if (n%2 == 1)
                    Mult2x2Matrix(result, fiboM);
                n /= 2;
                Mult2x2Matrix(fiboM, fiboM);
            }
 
            return result[1,0];
        }
 
        private static void Mult2x2Matrix(BigInteger[,] m, BigInteger[,] n)
        {
            BigInteger a = m[0,0] * n[0,0] + m[0,1] * n[1,0];
            BigInteger b = m[0,0] * n[0,1] + m[0,1] * n[1,1];
            BigInteger c = m[1,0] * n[0,0] + m[1,1] * n[0,1];
            BigInteger d = m[1,0] * n[0,1] + m[1,1] * n[1,1];
 
            m[0,0] = a;
            m[0,1] = b;
            m[1,0] = c;
            m[1,1] = d;
        }
 
        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();
            var bigInteger = Fib(65536);
            sw.Stop();
            Console.WriteLine("Elapsed milliseconds = {0}, number length = {1} digits", sw.ElapsedMilliseconds, bigInteger.ToString().Length);
        }
    } 
}