Быстрое нахождение чисел Фибоначчи
Описание способа нахождения значения произвольного элемента последовательности Фибоначчи за логарифмическое время.
Спираль Фибоначчи
Многие из тех, кто только приступает к изучению программирования, с одной из первых, сталкиваются с задачей о кузнечике.
На координатном луче, в точке с координатой 1 находится кузнечик. Этот кузнечик может прыгать только вперёд на расстояние 1 либо 2. Сколькими способами он может добраться до точки с координатой n?
Формула для решения этой задачи выводится достаточно просто.
Понятно, что до точки с координатой 0 кузнечик допрыгнуть не может — двигаться назад он не умеет. Способов попасть в эту точку 0. Попасть в точку с координатой 1, в которой он изначально находится, кузнечик может ровно одним способом — оставаться на месте. В любую другую точку с координатой n, кузнечик может добраться либо из точки с координатой n-1, либо из точки с координатой n-2. Соответственно, количество способов которыми он может достичь точки с координатой n равно сумме количеств способов которыми он может достичь точек с координатами n-1, и n-2. Иными словами, если функция f (n) вычисляет количество способов имеющихся у кузнечика чтобы попасть в точку n, то f (n) = f (n-1) + f (n-2).
Другая задача. В начале первого месяца вы получаете пару новорождённых кроликов. Через месяц, эти кролики повзрослеют. Начиная с третьего месяца и далее они будут стабильно давать приплод — ещё одну пару новорождённых кроликов. Таким образом, каждая появившаяся пара кроликов, начиная с двух месяцев после своего появления, каждый месяц порождает ещё пару кроликов. Количество кроликов никогда не уменьшается — кролики не болеют и не умирают. Задача: рассчитать какое количество пар кроликов будет у вас, на n-й месяц.
Формула для решения этой задачи, совпадает с формулой, полученной нами в задаче о кузнечике — f (n) = f (n-1) + f (n-2). Вполне очевидно, что каждый месяц к тому количеству кроликов, что было у вас в прошлом месяце прибавляется приплод, от тех кроликов которые у вас были два месяца назад, так как все они к этому моменту уже достаточно повзрослели, чтобы начать активно размножаться.
К счастью, у реальных кроликов несколько иные характеристики, иначе всего лишь через 9 лет, после появления первой пары кроликов, вся поверхность планеты была бы покрыта более чем 100-километровым плотным слоем кроличьих тушек.
Для решения обеих задач используется одна и та же формула: f (n) = f (n-1) + f (n-2). Это формула чисел последовательности Фибоначчи. Эта последовательность начинается с элемента под номером 0 и значением 0. За ним следует элемент под номером 1 и значением 1. Значения всех остальных элементов вычисляются согласно приведённой формуле — значение каждого из элементов равно сумме значений двух предыдущих.
Для неотрицательных номеров элементов значения принимают следующий вид:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …
Однако, из формулы f (n) = f (n-1) + f (n-2) вытекает, что f (n-2) = f (n) — f (n-1). Зная это, мы можем определить значения элементов последовательности и с отрицательными номерами. Так, элемент под номером -1 имеет значение 1, элемент под номером -2 — значение -1. Мы можем представить общий вид вот так:
…, -377, 233, -144, 89, -55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …
Несложно заметить, что значения элементов с отрицательными номерами, являются практически зеркальным отражением значений элементов с положительными номерами, с тем исключением, что элементы под чётными номерами имеют противоположный знак. Мы можем выразить это следующей формулой f (-n) = (-1)^(n+1)f (n). Благодаря данной формуле мы легко можем получить значение элемента под тем же номером с противоположным знаком. Доказательство корректности этой формулы оставляю в качестве небольшого упражнения читателям.
Теперь перейдём к задаче вычисления числа Фибоначчи со сколько-нибудь большим положительным номером. Скажем, 10000000.
Прежде чем приступать к решению, напишем несколько вспомогательных методов.
package fibonacci;
import java.math.BigInteger;
/**
* Нахождение чисел Фибоначчи.
* Класс предоставляет статический метод, для нахождения чисел Фибоначчи.
*/
public class Fibonacci {
// static fields
/**
* Полная форма опции печати.
*/
private static final String PRINT_OPTION_FULL_FORM = "--print";
/**
* Короткая форма опции печати.
*/
private static final String PRINT_OPTION_SHORT_FORM = "-p";
// static methods
/**
* Точка входа в приложение.
* Метод, предполагая, что начальным аргументом запуска указан номер желаемого числа Фибоначчи, вычисляет это число и выводит в стандартный поток ошибок время его вычисления. Опционально, если вторым аргументом является строка {@value #PRINT_OPTION_FULL_FORM}, или {@value #PRINT_OPTION_SHORT_FORM} в стандартный поток выводится значение выбранного числа, а в поток ошибок дополнительно выводится время вывода числа. Значение числа выводится до вывода длительностей вычисления и вывода.
* @param args Набор аргументов запуска.
* @throws NullPointerException Если набор аргументов запуска не существует.
* @throws ArrayIndexOutOfBoundsException Если набор аргументов запуска пуст.
* @throws NumberFormatException Если начальный аргумент запуска не является строкой, содержащей запись целого числа.
* @throws IllegalArgumentException Если в качестве начального аргумента запуска указанно значение {@link Integer#MIN_VALUE}.
*/
public static void main (
final String... args
) { // method body
final int n = Integer.parseInt(args[0]);
final boolean doPrint = (args.length > 1) && (args[1].equals(PRINT_OPTION_FULL_FORM) || args[1].equals(PRINT_OPTION_SHORT_FORM));
Instant start;
Instant finish;
final Duration calculationDuration;
Duration outputDuration = null;
start = Instant.now();
final BigInteger fibValue = fib(n);
finish = Instant.now();
calculationDuration = Duration.between(start, finish);
if (doPrint) {
start = Instant.now();
System.out.println(fibValue);
finish = Instant.now();
outputDuration = Duration.between(start, finish);
} // if
System.err.println(calculationDuration);
if (doPrint) {
System.err.println(outputDuration);
} // if
} // main()
/**
* Число Фибоначчи под указанным номером.
* Метод вычисляет и возвращает число Фибоначчи под указанным номером. Номер может быть как положительным, так и отрицательным.
* @param n Номер числа в последовательности. Не должен являться {@link Integer#MIN_VALUE}.
* @return Выбранное число Фибоначчи.
* @throws IllegalArgumentException Если указанный номер равен {@link Integer#MIN_VALUE}.
*/
public static BigInteger fib (
final int n
) { // method body
if (n == Integer.MIN_VALUE) throw new IllegalArgumentException();
BigInteger answer = null; // Здесь вычисляем абсолютное значение ответа, обратившись к одному из методов.
if ((n < 0) && (n % 2 == 0)) {
answer = answer.negate();
} // if
return answer;
} // fib()
// constructors
/**
* Конструктор, предотвращающий создание экземпляров класса.
* Конструктор объявлен с единственной целью - предотвратить создание экземпляров класса.
* @throws NoSuchMethodError При любом обращении к данному конструктору.
*/
private Fibonacci (
) { // method body
throw new NoSuchMethodError();
} // Fibonacci()
} // Fibonacci
Рекурсия.
Мы можем напрямую воспользоваться формулой f (n) = f (n-1) + f (n-2), и выразить функцию вычисления рекурсивно.
На языке Scheme это будет выглядеть так:
(define (fib n)
((if (and (negative? n) (even? n))
-
+) (fib-naive (abs n))))
(define (fib-naive n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib-naive (- n 2)) (fib-naive (- n 1))))))
На Java можно выразиться следующим образом:
/**
* Рекурсивное нахождение чисел Фибоначчи.
* Метод реализует рекурсивный алгоритм нахождения чисел Фибоначчи.
* @param n Номер числа в последовательности. Если номер отрицателен, то поведение метода не определено.
* @return Значение выбранного числа Фибоначчи.
*/
private static BigInteger fibNaive (
final int n
) { // method body
return switch (n) {
case 0 -> BigInteger.ZERO;
case 1 -> BigInteger.ONE;
default -> fibNaive(n-1).add(fibNaive(n-2));
}; // switch
} // fibNaive()
Однако, так как рекурсия требует многократного повторного вычисления одних и тех же значений, такой подход является крайне неэффективным, хотя и позволяет получить правильный результат. Но, по причине неэффективности, о сколько-нибудь больших номерах чисел в последовательности речи не идёт. Уже запрос 45-го числа Фибоначчи, заставляет машину задуматься на заметное время, что делает нашу цель — 10000000-е число последовательности, практически недостижимой.
Итеративный подход
Мы могли бы значительно сократить количество вычислений, воспользовавшись динамическим программированием. Например, просто сохраняя значения уже вычисленных элементов последовательности в массиве, и используя их повторно, при рекурсивных запросах. Это так называемая «ленивая динамика». Можно заметить, что в процессе рекурсивные вызовы всегда доходят до нулевого элемента, и, таким образом, используются значения всех элементов вплоть до целевого. Это позволило бы заменить рекурсию на последовательное заполнение массива вычисленных элементов. Но в процессе написания такого кода, стала бы очевидной вещь, явным образом проистекающая из формулы чисел. Давайте вспомним эту формулу:
f (n) = f (n-2) + f (n-1);
Для получения значения любого из элементов нам нужны значения только двух элементов предшествующих целевому, окружающих его, либо следующих за ним, но не остальные. В сущности, зная значения только любых двух смежных элементов последовательности, мы можем, постепенно продвигаясь в одном из направлений, узнать значение любого другого из элементов последовательности.
Так, зная значения нулевого и первого элементов последовательности, мы можем получить значение второго. Зная значения первого и второго, получаем значение третьего, и так далее.
Давайте выразим всё это в коде, для упрощения реализации начиная с пары минус первого и нулевого элементов.
На Scheme можем выразиться так:
(define (fib n)
((if (and (negative? n) (even? n))
-
+) (fib-iter 1 0 (abs n))))
(define (fib-iter prev cur n)
(cond ((zero? n) cur)
(else (fib-iter cur (+ prev cur) (- n 1)))))
А на Java — так:
/**
* Последовательное нахождение чисел Фибоначчи.
* Метод реализует итеративный алгоритм нахождения чисел Фибоначчи.
* @param n Номер числа в последовательности. Если номер отрицателен, то поведение метода не определено.
* @return Значение выбранного числа Фибоначчи.
*/
private static BigInteger fibIter (
final int n
) { // method body
BigInteger prev = BigInteger.ONE;
BigInteger cur = BigInteger.ZERO;
for (int i = n; i > 0; i--) {
final BigInteger next = cur.add(prev);
prev = cur;
cur = next;
} // for
return cur;
} // fibIter()
Теперь вычисления происходят несравненно быстрее, так как количество операций линейное. Вычислительная сложность алгоритма O (n). Для вычисления числа Фибоначчи с номером 1000000 придётся немного подождать, но оно стало достижимо. Наша цель — число Фибоначчи с номером 10000000, тоже достижима для этого алгоритма, но из-за большого числа сложений действительно больших чисел, ждать придётся достаточно времени, для того чтобы не спеша выпить чашечку кофе. Хотелось бы уменьшить это время.
Задача о быстром умножении
Для того, чтобы понять как мы можем находить числа Фибоначчи быстрее, рассмотрим следующую задачу:
Предположим, у нас имеется некий числовой тип данных, для значений которого определена только операция сложения. А нам нужно умножить значение этого типа a на не отрицательный, целый скаляр n.
Для начала, мы можем вспомнить, что операция умножения — это многократное повторение операции сложения. Так mul (a, n) = a + a + a + … + a, где значение a повторяется n раз.
Операция сложения, может быть выражена через рекурсию mul (a, n) = a + mul (a, n-1), что на Scheme можно высказать так:
(define (mul a n)
(cond ((zero? n) 0)
(else (+ a (mul a (- n 1))))))
Мы можем отказаться от использования рекурсии, заменив её итерациями. Это вытекает из формулы mul (a, n) = mul (a, n-1) + a, если предположить, что к моменту совершения данного шага операции значение mul (a, n-1) уже вычислено. Выразим этот подход на Scheme:
(define (mul a n)
(mul-iter a 0 n))
(define (mul-iter val accum count)
(cond ((zero? count) accum)
(else (mul-iter val (+ accum val) (- count 1)))))
Вычислительная сложность обоих этих походов, в данной задаче O (n), однако итеративный подход потребляет константное количество памяти, тогда как рекурсивному требуется O (n) дополнительной памяти для хранения промежуточных результатов.
Мы можем улучшить вычислительную сложность до O (log (n)) если вспомним, как значение скалярного числа n вычисляется из его записи в двоичной системе счисления. К примеру число 140 в двоичной системе записывается как 10001100. Значение числа из этой записи получается суммированием произведений значения каждой из цифр, на значение единиц её разряда. В случае числа 140 это выглядит как 128×1 + 64×0 + 32×0 + 16×0 + 8×1 + 4×1 + 2×0 + 1×0 = 128 + 8 + 4 = 140. Таким образом, если значение a умножается на скаляр 140, мы можем выразить это, как a*140 = a*128 + a*8 + a*4. Теперь вспомним, что степени двойки, это число 2 умноженное само на себя несколько раз. Так 128 = 2×2*2×2*2×2*2, 8 = 2×2*2 и 4 = 2×2. Получается, что выражение a*128 + a*8 + a*4 эквивалентно выражению (((((((a*2)*2)*2)*2)*2)*2)*2) + (((a*2)*2)*2) + ((a*2)*2). Используя это, а так же то, что операцию удвоения можно представить как сложение числа с самим собой, мы можем получить алгоритм умножения, работающий за логарифмическое время. Запишем его на языке Scheme:
(define (mul a n)
(quickMul a 0 n))
(define (quickMul val accum count)
(cond ((zero? count) accum)
((even? count) (quickMul (double val) accum (/ count 2)))
(else (quickMul val (+ accum val) (- count 1)))))
(define (double a)
(+ a a))
Заметьте, что для значений того же типа, что и a, в этом алгоритме используется только операция сложения, а вычислительная сложность улучшена до логарифмической, при константном потреблении памяти.
Формулы
Рассмотрев задачу о быстром умножении мы снова можем вернуться к числам Фибоначчи.
Сначала давайте подробнее рассмотрим формулу числа с номером n:
f (n) = f (n-2) + f (n-1)
Каждое из чисел Фибоначчи образовано суммой двух предшествующих чисел Фибоначчи. Каждое из двух предшествующих тоже является суммой, уже предшествующих ему чисел последовательности. Давайте попробуем последовательно раскладывать на слагаемые самый старший элемент последовательности, из правой части уравнения: f(n) = 1f(n) = 0f(n-1) + 1f(n-0);f(n) = 0f(n-1) + 1(f(n-1) + f(n-2)) = 1f(n-2) + 1f(n-1);f(n) = 1f(n-2) + 1(f(n-2) + f(n-3)) = 1f(n-3) + 2f(n-2);f(n) = 1f(n-3) + 2(f(n-3) + f(n-4)) = 2f(n-4) + 3f(n-3);f(n) = 2f(n-4) + 3(f(n-4) + f(n-5)) = 3f(n-5) + 5f(n-4);f(n) = 3f(n-5) + 5(f(n-5) + f(n-6)) = 5f(n-6) + 8f(n-5);f(n) = 5f(n-6) + 8(f(n-6) + f(n-7)) = 8f(n-7) + 13f(n-6);
Обратим внимание на последовательности коэффициентов слагаемых в самой правой части уравнений. Это две последовательности чисел: 0, 1, 1, 2, 3, 5, 8, … и 1, 1, 2, 3, 5, 8, 13, … Не правда ли, эти последовательности схожи между собой, и по какой-то причине кажутся нам знакомыми… Неудивительно, ведь это первые числа последовательности Фибоначчи. Итак, взглянув на эти коэффициенты, мы можем предположить существование следующей формулы:
f (n) = f (x)f (n-(x+1)) + f (x+1)f (n-x); Где x — некоторое целое число. (1)
Покажем, с помощью математической индукции, справедливость этой формулы при любом значении x.
База индукции.
Покажем, что формула справедлива при x = 0:
f (n) = f (0)f (n-(0+1)) + f (0+1)f (n-0);
f (n) = f (0)f (n-1) + f (1)f (n);
f (n) = 0f (n-1) + 1f (n);
f (n) = f (n);
Индуктивный переход при увеличении значения x.
Покажем, что если формула справедлива при x=k, то формула справедлива и при x = k + 1.
Предположим, что равенство f (n) = f (k)f (n-(k+1)) + f (k+1)f (n-k) верно. Тогда, при x = k + 1:
f (n) = f (k+1)f (n-((k+1)+1)) + f ((k+1)+1)f (n-(k+1));
f (n) = f (k+1)f (n-(k+2)) + f (k+2)f (n-(k+1));
f (n) = f (k+1)f (n-k-2) + f (k+2)f (n-(k+1));
f (n) = f (k+1)(f (n-k) — f (n-k-1)) + (f (k) + f (k+1))f (n-(k+1));
f (n) = f (k+1)f (n-k) + f (k)f (n-(k+1)) + f (k+1)f (n-(k+1)) — f (k+1)f (n-k-1);
f (n) = f (k+1)f (n-k) + f (k)f (n-(k+1));
f (n) = f (n);
Индуктивный переход при уменьшении значения x.
Покажем, что если формула справедлива при x=k, то формула справедлива и при x = k — 1.
Предположим, что равенство f (n) = f (k)f (n-(k+1)) + f (k+1)f (n-k) верно. Тогда, при x = k — 1:
f (n) = f (k-1)f (n-(k-1+1)) + f (k-1+1)f (n-(k-1));
f (n) = f (k-1)f (n-k) + f (k)f (n-k+1);
f (n) = (f (k+1) — f (k))f (n-k) + f (k)(f (n-k) + f (n-k-1));
f (n) = f (k)f (n-k) — f (k)f (n-k) + f (k)f (n-k-1) + f (k+1)f (n-k);
f (n) = f (k)f (n-(k+1)) + f (k+1)f (n-k);
f (n) = f (n);
Теперь, благодаря формуле (1), мы можем вывести формулу числа Фибоначчи от суммы индексов. Для этого предположим, что n = a + b. Подставим это выражение в формулу (1):
f (a+b) = f (x)f ((a+b)-(x+1)) + f (x+1)f ((a+b)-x);
Теперь, установим x = a, и подставим в формулу, полученную на предыдущем шаге:
f (a+b) = f (a)f ((a+b)-(a+1)) + f (a+1)f ((a+b)-a);
f (a+b) = f (a)f (a+b-a-1) + f (a+1)f (a+b-a);
f (a+b) = f (a)f (b-1) + f (a+1)f (b);
Таким образом:
f (a+b) = f (a)f (b-1) + (f (a-1) + f (a))f (b); (2)
Кроме того, воспользовавшись формулой (2), мы можем вывести формулу числа Фибоначчи от удвоенного индекса.
Установим в формуле (2) оба слагаемых равными n:
f (n+n) = f (n)f (n-1) + (f (n-1) + f (n))f (n);
f (2n) = f (n)(2f (n-1) + f (n)); (3)
Теперь почти всё готово для быстрого вычисления произвольных элементов последовательности Фибоначчи, на основе принципов, раскрытых при решении задачи о быстром умножении. Только перед этим следует обратить внимание на то, что в формулах (2) и (3) для вычисления нам требуется не только знание значения f (k), но и знание предшествующего ему значения f (k-1). Опираясь на формулу (2), мы легко можем вывести формулы для получения значения f (a+b-1) и, затем, f (2n-1):
В формуле (2) подставим вместо a выражение a — 1:
f ((a-1)+b) = f (a-1)f (b-1) + (f ((a-1)-1) + f (a-1))f (b);
f (a+b-1) = f (a-1)f (b-1) + (f (a-2) + f (a-1))f (b);
f (a+b-1) = f (a)f (b) + f (a-1)f (b-1); (4)
Подставим в формулу (4) значение n вместо значений a и b:
f (n+n-1) = f (n)f (n) + f (n-1)f (n-1);
f (2n-1) = f (n)^2 + f (n-1)^2; (5)
Теперь у нас есть всё, что необходимо для реализации быстрого вычисления чисел Фибоначчи.
Реализация быстрого вычисления. Scheme
Поскольку в формулах, как было замечено выше, для произведения вычислений требуется не только значение f (k), но и предшествующее ему значение f (k-1), будет удобно представлять элемент последовательности сразу парой чисел — самим значением элемента, и предшествующим ему. Для представления пар элементов, в языке Scheme, имеется стандартная конструкция Pair, которая, в основном, используется для создания списков, но подойдёт и в нашем случае. Для создания пары предназначена функция cons, а для доступа к полям пары — функции car и cdr. Само значение элемента последовательности будем хранить в первом поле, получая доступ при помощи функции car, а предшествующее ему значение — во втором поле, для доступа используя функцию cdr.
Действуя описанным образом, функцию быстрого вычисления элементов последовательности Фибоначчи, мы можем определить на Scheme так:
(define (fib n)
(cond ((and (negative? n) (even? n)) (- (fib (abs n))))
(else (qfib (abs n) (cons 1 0) (cons 0 1)))))
(define (qfib n term accum)
(cond ((zero? n) (car accum))
((even? n) (qfib (halve n) (fib-double term) accum))
(else (qfib (- n 1) term (fib-sum accum term)))))
(define (halve x)
(quotient x 2))
(define (fib-double x)
(cons (* (car x) (+ (* 2 (cdr x)) (car x)))
(+ (sqr (car x)) (sqr (cdr x)))))
(define (fib-sum a b)
(cons (+ (* (car a) (cdr b)) (* (+ (car a) (cdr a)) (car b)))
(+ (* (car a) (car b)) (* (cdr a) (cdr b)))))
(define (sqr x)
(* x x))
Реализация быстрого вычисления. Java
На Java, для повышения наглядности, вытесним реализацию элементов последовательности, сочетающих пару из текущего и предшествующего значений, а так же функций преобразования номера и быстрого вычисления в отдельный класс. Кроме того, воспользовавшись тем, что у нас есть быстрый доступ ко всем двоичным разрядам номера требуемого элемента, мы, для уменьшения количества вычислений, будем не удваивать номер слагаемого, проходя по битам целевого номера от младших к старшим, а наоборот — проходя от старших битов к младшим, будем удваивать номер аккумулятора, при необходимости увеличивая его на единицу. Для пояснения, вспомним пример из рассмотренной задачи о быстром умножении, где мы умножали значение a на скаляр 140. Число 140 можно представить не только как сумму (128 + 8 + 4), но и в виде выражения (((1×16 + 1)*2 + 1)*4).
Вспомогательный класс реализующий быстрое вычисление элементов последовательности Фибоначчи:
package fibonacci;
import java.math.BigInteger;
/**
* Быстрое вычисление элементов последовательности Фибоначчи.
* Экземпляры класса являются immutable-объектами представляющими элементы последовательности Фибоначчи. Каждый из таких объектов предоставляет методы, необходимые для реализации быстрого вычисления других элементов последовательности.
* Кроме того, класс предоставляет статический фабричный метод, реализующий алгоритм быстрого вычисления элементов последовательности.
*/
public class QFib {
// static fields
/**
* Нулевой элемент последовательности.
*/
public static final QFib ZERO = new QFib(BigInteger.ZERO, BigInteger.ONE, BigInteger.ZERO);
// instance fields
/**
* Значение данного элемента последовательности.
*/
private final BigInteger cur;
/**
* Значение предшествующего элемента последовательности.
*/
private final BigInteger prev;
/**
* Номер данного элемента последовательности.
*/
private final BigInteger n;
// static methods
/**
* Получение элемента последовательности с заданным номером.
* Метод, реализуя алгоритм быстрого вычисления элементов последовательности Фибоначчи, находит и возвращает элемент с заданным номером.
* @param n Номер элемента в последовательности.
* @return Элемент последовательности с заданным номером.
* @throws NullPointerException Если указанный номер элемента не существует.
*/
public static QFib of (
final BigInteger n
) throws NullPointerException
{ // method body
QFib accum = ZERO;
final BigInteger absN = n.abs();
for (int i = absN.bitLength() - 1; i >= 0; i--) {
accum = accum.doubleN();
if (absN.testBit(i)) {
accum = accum.next();
} // if
} // for
if (n.signum() < 0) {
accum = accum.negateN();
} // if
return accum;
} // of()
// constructors
/**
* Конструктор элемента последовательности.
* @param cur Значение данного элемента последовательности.
* @param prev Значение предшествующего элемента последовательности.
* @param n Номер данного элемента последовательности.
* @throws AssertionError Если разрешены операторы контроля, и любой из аргументов не существует.
*/
private QFib (
final BigInteger cur,
final BigInteger prev,
final BigInteger n
) throws AssertionError
{ // method body
assert cur != null;
assert prev != null;
assert n != null;
this.cur = cur;
this.prev = prev;
this.n = n;
} // QFib()
// instance methods
/**
* Значение элемента.
* Метод возвращает значение данного элемента последовательности.
* @return Значение данного элемента.
*/
public BigInteger value (
) { // method body
return cur;
} // value()
/**
* Следующий элемент последовательности.
* @return Следующий элемент последовательности.
*/
public QFib next (
) { // method body
final BigInteger nextCur = cur.add(prev);
final BigInteger nextPrev = cur;
final BigInteger nextN = n.add(BigInteger.ONE);
return new QFib(nextCur, nextPrev, nextN);
} // next()
/**
* Удвоение номера элемента.
* Метод возвращает элемент последовательности номер которого равен удвоенному номеру данного.
* @return Элемент с номером равным удвоенному номеру данного.
*/
public QFib doubleN (
) { // method body
final BigInteger doubleCur = cur.parallelMultiply(prev.add(prev).add(cur));
final BigInteger doublePrev = cur.parallelMultiply(cur).add(prev.parallelMultiply(prev));
final BigInteger doubleN = n.add(n);
return new QFib(doubleCur, doublePrev, doubleN);
} // doubleN()
/**
* Смена знака номера.
* Метод возвращает элемент последовательности с номером равным по абсолютному значению, но противоположным по знаку номеру данного элемента.
* @return Элемент последовательности с номером противоположным по знаку.
*/
public QFib negateN (
) { // method body
BigInteger negCur = cur;
BigInteger negPrev = cur.add(prev);
if (n.testBit(0)) {
negPrev = negPrev.negate();
} else {
negCur = negCur.negate();
} // if
final BigInteger negN = n.negate();
return new QFib(negCur, negPrev, negN);
} // negateN()
} // QFib
Теперь, в основном классе Fibonacci, реализуем метод qfib(), использующий написанный нами вспомогательный класс для быстрого вычисления значений элементов последовательности Фибоначчи:
/**
* Быстрое нахождение значения произвольного элемента.
* Метод, обращаясь к вспомогательному классу, находит за логарифмическое время и возвращает значение произвольного элемента последовательности Фибоначчи.
* @param n Номер элемента в последовательности.
* @return Значение указанного элемента последовательности.
*/
private static BigInteger qfib (
final int n
) { // method body
return QFib.of(BigInteger.valueOf(n)).value();
} // qfib()
Теперь мы достигли своей цели: с быстрым подходом вычисления стали действительно быстрыми — поиск 10000000-го числа последовательности занимает менее секунды! Так происходит потому, что вычислительная сложность быстрого алгоритма является логарифмической — в самом деле, на каждом шаге в методе of() класса QFib рассматривается один бит номера выбранного элемента. Таким образом, число итераций, совершаемых алгоритмом для нахождения выбранного элемента последовательности, в точности соответствует числу разрядов в двоичном представлении номера выбранного элемента, что в терминах выражения количества вычислений означает, что вычислительная сложность быстрого алгоритма равна O (log (n)). Печать найденного 10000000-го числа Фибоначчи на экране занимает в четыре с половиной раза больше времени, чем его вычисление — вывод таких больших чисел требует немало времени, ведь количество десятичных цифр в выводимом значении лишь на 30% меньше, чем общее число символов в четырёхтомнике «Война и мир».
С этим алгоритмом, для нас становятся вполне достижимы элементы последовательности Фибоначчи с совсем уже «неприличными» номерами: например, вычисление 1000000000-го числа Фибоначчи, на моей машине, занимает чуть меньше шести минут, а вот формирование и вывод его десятичного представления — без нескольких секунд, 50 минут. Последнее не удивительно, так как десятичное представление этого числа состоит из 208987640 знаков.
Заключение
Использованный алгоритм по сути манипулирует номерами элементов, а не их значениями. Этот алгоритм с равным успехом может быть использован как для быстрого умножения и быстрого получения чисел Фибоначчи, так и для нахождения элементов любой подходящей последовательности за логарифмическое время. Единственным условием, для такой последовательности, является определение функции нахождения элемента от суммы номеров двух других элементов seq (n+m), либо двух функций: удвоения номера элемента seq (2n), и увеличения номера элемента на единицу seq (n+1).
В заключение хотелось бы сказать несколько слов о целесообразности применения рассмотренных нами алгоритмов к получению значений последовательности Фибоначчи. Если требуется вычислить произвольный элемент последовательности, то тут, вне всяких сомнений, пальму первенства удерживает быстрый алгоритм, так как он требует только O (log (n)) вычислений. Однако, если нам необходимо однократно вывести непрерывную подпоследовательность из m элементов, то применение быстрого алгоритма не оправдано, поскольку для этого потребуется O (m*log (n)) операций, в то время как простой итеративный алгоритм, если уже известны два начальных элемента подпоследовательности, потребует только O (m) операций. Впрочем, если начальные элементы выводимой подпоследовательности нам ещё не известны, то получить их поможет как раз быстрый алгоритм, а вот дальше за дело возьмётся итеративный. Наконец, вспомним про незаслуженно обделённый нашим вниманием алгоритм на основе методов динамического программирования, заполняющий линейный массив однажды вычисленных элементов, позволяющий заполнить этот массив за линейное время, как с помощью рекурсивной реализации использующей «ленивую динамику», так и с помощью итеративного подхода. Этот алгоритм имеет важное преимущество перед другими, получаемое в случае множественных последующих обращений к уже вычисленным элементам последовательности: поскольку результаты вычислений кешируются, то, при повторных обращениях, стоимость получения значений вычисленных элементов является константной. То есть, алгоритм на основе динамического программирования требует O (n) памяти для хранения вычисленных элементов, совершает O (n) операций при заполнении кеша, но в дальнейшем, стоимость обращения к вычисленным элементам будет составлять O (1).
