Расскажу вам об одной интересной формуле. Нередко на разных форумах обсуждается вопрос: как быстрее всего находить числа Фибоначчи? И почти везде для этого используют либо формулы, задействующие золотое сечение с точностью до определённого знака, либо простое сложение. Однако, существует куда более изящное решение, причём только в целых числах.

Напомню, что:
F(0)=0
F(1)=1
F(n) = F(n–1) + F(n–2)

Для вычисления F(n) можно воспользоваться следующими формулами:
F(2k–1) = F(k–1)2 + F(k)2
F(2k) = (2 F(k–1) + F(k))F(k)

Так, для вычисления F(1000) нужно найти всего 21 штуку предыдущих значений F(n).

GD Star Rating
loading...

11 Responses to Как быстрее всего находить числа Фибоначчи?

  1. ReMonkey:

    Откуда взялась сумма квадратов? Я чё–т не просёк. И как из этих формул следует, что тысячный член ряда Фиббоначи находится через 21 предыдущий?

  2. Zvin:

    Вот статья, в которой эта формулы была впервые описана, по крайней мере так считается, что до этого она нигде не публиковалась.
    Давайте рассмотрим конкретный пример, найдём F(49)
    Известно, что F(49)=7778742049
    по представленным выше формулам получается, что F(49)=F(2*25 –1) = F(24)2+F(25)2
    Снова обратимся к известным источникам: F(24)=46368, тогда 46368^2=2149991424, F(25)=75025, значит 75025^2=5628750625
    И действительно, 2149991424+5628750625=7778742049
    Точно таким же образом можно найти F(24) и F(25) и все предыдущие F(n), нужные для их вычисления, вплоть до F(0) и F(1), которые определены изначально.

  3. Zvin:

    Я не поленился, расписал все шаги: для вычисления F(1000) нужны F(500) и F(499)
    Для вычисления F(500) и F(499) нужны F(250) и F(249)
    F(250) и F(249) нуждаются в F(124) и F(125)
    Для F(124) нужны F(61) и F(62)
    Для F(125) нужны F(62) и F(63)
    Для F(63) нужны F(32) и F(31)
    Для F(62) и F(61) нужны F(31) и F(30)
    F(32) и F(31) нуждаются в F(16) и F(15)
    Для F(30) нужны F(15) и F(14)
    Для F(16) и F(15) нужны F(8) и F(7)
    Для F(14) нужны F(7) и F(6)
    F(8) и F(7) нуждаются в F(4) и F(3)
    Для F(6) нужны F(3) и F(2)
    F(4) и F(3) нуждаются в F(2) и F(1)
    F(2) требует F(1) и F(0)
    F(1) и F(0) заданы изначально, по определению.

  4. Zvin:

    Давайте что ли ещё немного таких формул. Известно, что числа Лукаса (обозначим их L(n)) задаются по той же формуле, что и числа Фибоначчи, только первые члены другие: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, …
    С их помощью нам открываются следующие формулы:

    F(4k+1) ? 1 = F(k)L(k)L(2k+1)
    F(4k+3) ? 1 = F(k+1)L(k+1)L(2k+1)
    F(4k+1) + 1 = F(2k+1)L(2k)
    F(4k+3) + 1 = F(2k+1)L(2k+2)
    L(4k+1) ? 1 = 5 F(k)L(k)F(2k+1)
    L(4k+3) ? 1 = L(2k+1)L(2k+2)
    L(4k+1) + 1 = L(2k)L(2k+1)
    L(4k+3) + 1 = 5 L(k+1)F(k+1)F(2k+1)

  5. ReMonkey:

    Оу, как интересно, спасибо.

  6. Lu007:

    А по–моему это легче запомнить в матричной форме.

    Ну а возведение в степень — операция логарифмической сложности от показателя степени.

  7. Zvin:

    а не дольше ли получится матрицы перемножать, даже алгоритмом Копперсмита–Винограда, чем целые числа алгоритмами Шёнхаге–Штрассена и Фюрера для больших n?

  8. Zvin:

    Как при помощи чисел Фибоначчи проверить, является ли число простым?

    Для этого нужно посмотреть, насколько близко значение F(n)/n к ближайшему целому числу. Если близко, значит n простое. Объяснение этому следующее: для всех простых n, за некоторыми известными исключениями, F(n+1) или F(n–1) содержит n в качестве одного из множителей.

    К сожалению, этот алгоритм неэффективен и на практике малопригоден к использованию.

  9. Lu007:

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

    У меня есть подозрения, что эту матричную запись можно привести к форме, указанной в посте, но как то лень проверять.

  10. TcMoon:

    для перемножения матриц размером 2 на 2 никакой виноград не нужен

  11. Re:

    Для больших n матрицы умножать будет быстрее, для вычисления F_n нужно O(log n) операций, в то время как для вычисления по формулам похоже будет степенная от n функция, хоть и с показателем < 1. Кстати, эти формулы на сколько я помню выводятся именно из матричной)

    Кстати, метод с матрицами применим к любой линейной рекурентности, в отличии от формул

Добавить комментарий