sergeyShpagin May 6 at 14:31

Быстрое нахождение чисел Фибоначчи

Easy

17 min

10K

Java*Algorithms*

From sandbox

+32

Comments 23

malkovsky May 6 at 14:58

Тут нужно сделать важную оговорку, что все указанные оценки справедливы только если вы, например, делаете вычисления по модулю. Проблема в том, что длина Fn растет линейно от n из-за чего итеративный алгоритм работает на самом деле за O(n^2), а быстрый за O(nlogn) (из мастер-теоремы). Ну и соответственно если вы работаете по модулю часла длины k, то получаются оценки O(nk)/O(klogn).

Есть еще формула Бине

$f_n=\frac{\varphi^n-(-\varphi)^{-n}}{\sqrt{5}}~~\varphi=\frac{1+\sqrt{5}}{2}$

которая сводит вычисления чисел Фибоначчи к возведению в степень, которое можно делать за log, но из-за работы с float она не такая полезная даже для спортивного интереса, в отличии от

$\left(\begin{array}{cc}f_{n+1} & f_n \\ f_n & f_{n-1}\end{array}\right)^n=\left(\begin{array}{cc}1 & 1 \\ 1 & 0\end{array}\right)^n$

+15

wataru May 6 at 15:05

А еще можно вычислять по формуле Бине, но в алгебраическом расширении целых чисел корнем из 5. Тогда числа хранятся в виде a+b*sqrt(5). И умножение таких чисел будет тем же самым возведением матрицы в степень.

sci_nov May 6 at 15:36

N log N - быстрое преобразование Фибоначчи)), БПФ

GospodinKolhoznik May 7 at 21:34

А если есть процессор с бесконечно большим числом ядер)) то за O(log(n)) парралельных шагов можно вычислять не только числа Фибоначчи, но и любую рекуррентную последовательность вида

$x_n=a_n x_{n-1} + b_n x_{n-2}$

mentin May 7 at 07:21

Сведение Фибоначчи к умножению имхо проще всего понять, записав его как матричное умножение,
Вместо f(n) будем смотреть что происходит с вектором, точнее столбцом f(n+1), f(n):

f(n+1) = 1*f(n) + 1*f(n-1)
f(n)   = 1*f(n) + 0*f(n-1)

$\begin{pmatrix} f(n + 1) \\ f(n) \end{pmatrix}=\begin{pmatrix} 1 1 \\ 1 0 \end{pmatrix}\times\begin{pmatrix} f(n) \\ f(n - 1) \end{pmatrix}$

Получаем буквально возведение в степень (мартиц)

$\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix}=\begin{pmatrix} 1 1 \\ 1 0 \end{pmatrix}^{n}\times\begin{pmatrix} f(1) \\ f(0) \end{pmatrix}$

aamonster May 12 at 15:32

Только к возведению в степень, не к умножению.

domix32 May 7 at 13:00

100-километровым плотным слоем кроличьих тушек.

Напомнило нефтяную планету из кротов.

public static void main (final String... args )

А зачем final аргументам?

sergeyShpagin May 7 at 22:01

А зачем final аргументам?

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

domix32 May 7 at 22:12

А какой профит? У джавы какое-то особенное отношение к наследованию и внезапно можно частично отнаследовать методы или что-то в этом роде? То есть это явно не константность.

wataru May 7 at 22:28

final в джава тут - это как const в C++ - константрые, неизменяемые переменные.

GospodinKolhoznik May 7 at 21:22

Как сложно вы расписали! Это классическая задача, она разбирается в легендарной книге SICP и во многих учебниках по линейной алгебре. И в матричном виде разбор её решения занимает меньше страницы текста.

sergeyShpagin May 7 at 22:12

К сожалению, с математикой у меня не очень. Эта статья появилась, как раз по той причине, что во время разбора упражнения 1,19 в SICP, я не смог понять, как выводится формула a ← bq + aq + ap, b ← bp + aq, а про матричный способ вычисления чисел Фибоначчи не знал. Попробовал разобраться самостоятельно...

GospodinKolhoznik May 7 at 22:38

Ясно. Ну смотрите. Линейная алгебра очень большая наука. И даже то, что дается в университетских курсах это ее малая часть. Но есть и хорошая новость. Почти все знания из линейки, которые как то можно применить на практике изучаются за недельку (или две). Это операции сложения и умножения матриц и векторов, а ещё вычисление детерминанта ну и матрицы поворота и перехода к другому базису. Это покрывает почти все практические нужды, которые только бывают. Так что если вдруг захотите разобраться, вам надо внимательно изучить первые 20-30 страниц любого учебника. Остальные 400 страниц почти нигде не пригодятся. Такой вот принцип Парето на максималках.

Yermack May 8 at 23:09

Хорошая традиция - каждый раз, прежде чем начинать читать статью про быстрое нахождение чисел Фибоначчи, брать и воспроизводить по памяти решение:

julia> fib(n) = ( BigInt.( [1 1;1 0] )^n )[1];

julia> fib.(1:10)
10-element Vector{BigInt}:
  1
  2
  3
  5
  8
 13
 21
 34
 55
 89
julia> @time fib(1_000_000);
  0.029857 seconds (1.45 k allocations: 10.012 MiB)

julia> @time fib(100_000_000);
  6.999292 seconds (105.82 k allocations: 1.612 GiB, 0.14% gc time)

julia> 100_000_000 |> fib |> string |> length
20 898 764

vpert May 13 at 08:43

А возведение в степень здесь происходит за логарифм или линейное? Просто в этом и заключается вся задача

Кажется по выводу, что в 100 раз увеличили число, в ~100 раз увеличилось и время. Хотя возможно это вина длинной арифметики

wataru May 13 at 11:11

Хотя возможно это вина длинной арифметики

Именно. Длина чисел растет линейно от n. Более того, оно так быстро работает только потому, что там еще и умножение длинных чисел сделано быстро, через FFT какое-нибудь. A то мы бы только умножение двух чисел длиной с миллионы знаков ждали бы несколько минут. В итоге там что-то около O(n (log n)^2) получается.

aamonster May 12 at 15:40

TL;DR

Слишком большая статья для описания такой простой вещи. Лучше б рассказали старинную байку, как фанаты ассемблера и си зарубились из-за скорости, договорились помериться, вычисляя n-е число Фибоначчи, и всех уделал какой-то чувак, написавший чуть ли не на бейсике.

Как только узнаёшь в задаче возведение матрицы в степень – остальное должен написать, не задумываясь.

Кстати, если копнуть глубже – это решение не за логарифмическое время. Ведь числа с ростом N становятся всё длиннее, и умножение, соответственно, медленнее. Исходя из объёма вашей статьи и упоминания в ней быстрого алгоритма умножения – я ожидал увидеть как минимум алгоритм Карацубы.

kt0x May 13 at 08:42

Почему бы просто не воспользоваться формулой Бине?

ImidgX May 13 at 08:43

Как так получилось, что итеративный способ с n сложениями оказался дольше/хуже, чем матричное возведение в степень, где как я понимаю 4 операции сложения и 8 операций умножения на каждую итерацию⁉️ ?

ImidgX May 13 at 17:01

Я "думал-думал и всё понял" ?
В матричном умножении для быстрого вычисления используется быстрое возведение в степень: https://habr.com/ru/companies/otus/articles/779396/
Что логарифмически уменьшает количество операций.

VeryLysyj Jun 18 at 17:10

Без каких-либо претензий, предлагаю такой вариант.

        // быстрое вычисление чисел Фибоначчи для х => 0 по формуле Бине
        public static Int64 FastFibonacci(int x)
        {
            const float cp = 1.6180339887498948482046f; // (1+sqrt(5))/2
            const float sqrt5 = 0.4472135954999579392818f; // 1/sqrt(5)
            const float delta = 0.4999999999f; // для округления вправо

            float s = sqrt5;
            float v = cp;
            int c = x;
            
            while (c != 0)
            {
                if (c % 2 == 1)
                {
                    s = s * v;
                }
                c = c >> 1;
                v = v * v;
            }
            return (Int64)(s + delta);
        }

Прошу не судить строго, может чего не понял.

wataru Jun 18 at 20:09

Тут проблема с точностью. float всего-то 32 бита. Но даже в даблах у вас быстро точностьи мантиссы перестанет хватать. раньше, чем int64 ответ переполнится. А уж если в ответ длинные числа нужны, то вы длинную вещественную арифметику писать замучаетесь.

VeryLysyj Jun 19 at 14:45

Согласен по всем статьям. Во-первых, действительно, если и использовать стандартные типы, то лучше будет double - там 16 значащих цифр. Во-вторых, округление результата при помощи delta и приведения типа к Int64 имеет смысл до 1Е17 максимум (для использования типа double), а дальше можно вообще не париться с округлением, и просто s возвращать.

Для повышения точности можно использовать тип BigInteger, тогда вроде всё будет работать бог знает до куда, главная проблема будет вычислить соответствующее количество значащих цифр для констант (1+sqrt(5))/2 и 1/sqrt(5).

Показанный выше алгоритм я изначально планировал как быстрый, но с ограниченной точностью. Главный вопрос, какова от него от такого польза? Вечный вопрос, нужно ли вообще писать алгоритм, если заранее не знаешь, понадобится ли он вообще кому-нибудь?

Show the best of all time