Точное вычисление 1000-го числа Фибоначчи

Дональд Кнут в своей книге "Искусство программирования" (т. 1, "Основные алгоритмы") предлагает решить следующую задачу.

Напишите программу, которая вычисляет и выдаёт на печать числа Фибоначчи от F1 до F1000 в десятичном виде.

В данной статье мы решим эту задачу с той лишь оговоркой, что выводить на печать тысячу чисел мы не будем, а ограничимся лишь выводом F1000. Читатель, при желании, сможет сам модернизировать приводимые нами программы таким образом, чтобы на печать выводились все найденные числа, а не только последнее.

Сама по себе задача нахождения чисел Фибоначчи настолько тривиальна, что, пожалуй, не заслуживает отдельной статьи. Однако, если язык программирования, на котором будет писаться программа, не поддерживает переменные целого типа произвольного размера (а именно таковым является язык C99, который мы собираемся использовать), то задача существенно усложняется.

В самом деле, для хранения числа F1000, как будет показано далее, размера поддерживаемых языком C99 стандартных типов целочисленных данных не хватит. Таким образом, задача, по сути, сводится к созданию целочисленного типа данных неограниченного размера и функций для работы с ним.

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

Предварительные замечания

Вспомним, какие числа называются "числами Фибоначчи". Дональд Кнут в упомянутой выше книге определяет числа Фибоначчи как члены последовательности, определяемой следующим образом:

F 0 = 0 ; F 1 = 1 ; F n + 2 = F n + 1 + F n , n ≥ 0 .

По сути, приведённую рекуррентную формулу можно рассматривать как готовый алгоритм для последовательного вычисления чисел Фибоначчи.

Давайте найдём теперь приближённое значение числа F1000. Для этого нам понадобится ещё одна формула из книги Кнута:

F n ≈ ϕ n 5 , ϕ = 1 + 5 2 .

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

lg ϕ 1000 5 = 1000 lg 1 + 5 - lg 2 - 1 2 lg 5 ≈ 208 , 6381552 .

F 1000 ≈ 10 208 , 6381552 = 10 0 , 6381552 · 10 208 ≈ 4 , 346656 × 10 208 .

Итак, как мы видим, число F1000 является 209-значным. Разумеется, никакие встроенные целочисленные типы языка C99 не позволяют хранить числа таких размеров.

Далее будем действовать следующим образом. Для "разминки" напишем две программы, вычисляющие числа Фибоначчи приближённо и сохраняющие их в переменных типа double . Затем перепишем эти программы, используя для хранения этих чисел переменные типа big_int . Новые версии программ будут находить уже точные значения чисел Фибоначчи.

Во всех программах индекс последнего вычисляемого числа Фибоначчи (т. е. число 1000) будет задаваться с помощью макроса N , определяемого следующим образом:

Приближённые вычисления

Создадим массив типа double , состоящий из 1001 элемента и последовательно заполним его числами Фибоначчи, используя приведённую выше рекуррентную формулу, после чего выведем последний элемент массива на печать. Ниже приведён код программы.

Полагаю, что код настолько прост, что комментарии излишни. Выполнение программы приведёт к следующему выводу на консоль:

Как мы видим, вычисленное программой приближённое значение F1000 полностью совпало с приближённым значением, найденным по формуле.

Совсем не обязательно хранить все вычисленные значения чисел Фибоначчи. Достаточно в любой момент времени знать только два последних значения. Если они содержатся в двух переменных, то процесс получения очередного числа Фибоначчи будет выглядеть так: сумма этих значений присваивается той переменной, в которой хранилось до этого наименьшее из двух значений.

Ясно, что на каждой итерации цикла, в ходе которого последовательно вычисляются числа Фибоначчи, эти две переменные будут "меняться ролями". Обеспечить такое чередование ролей можно, выполняя те или иные действия, в зависимости от чётности или нечётности переменной цикла.

Ниже приведена новая версия программы, в которой для хранения чисел Фибоначчи вместо массива используются переменные a и b .

Заметим, что в ходе выполнения программы числа Фибоначчи с чётными индексами всегда будут помещаться в переменную b , а с нечётными — в переменную a . Результат работы этой программы полностью совпадает с результатом работы предыдущей.

Точные вычисления

Приступим к точному вычислению числа F1000. С этой целью перепишем предыдущие 2 программы с использованием типа big_int . Ссылки на две статьи с описанием этого типа и функций для работы с ним приведены в начале данной статьи. Весь программный код, разработанный в этих двух статьях, мы соберём в библиотеку, которую будем подключать к нашим программам с помощью заголовочного файла big_int.h.

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

• dcreate() — принимает адрес строки, содержащей текстовое представление большого числа в десятичной форме. На основе этой строки формирует переменную типа big_int и возвращает её адрес. В случае ошибки возвращает ноль;
• sum() — принимает адреса двух переменных типа big_int , складывает их и создаёт переменную того же типа, содержащую сумму. Функция возвращает адрес созданной переменной;
• dprint() — принимает адрес переменной типа big_int , формирует строку, содержащую текстовое представление переменной в десятичном виде. Функция возвращает адрес созданной строки;
• delete() — принимает адрес переменной типа big_int , освобождает память, занятую этой переменной.

Итак, модернизируем первую программу из предыдущего радела. Вот код новой версии:

Библиотека для работы с большими числами ориентирована на работу с переменными типа big_int через указатели. Поэтому мы создаём массив не самих переменных типа big_int , а указателей на них (см. строку 6). Далее в ходе выполнения программы этот массив заполняется адресами переменных, созданных динамически (строки 7-10).

Заметим, что в строках 14, 15 происходит утилизация динамической памяти, выделенной для хранения всех чисел Фибоначчи. Можно задаться вопросом: а стоило ли освобождать память непосредственно перед выходом из функции main() ? Ведь выход из main() означает завершение всей программы, после которого вся выделенная для неё память автоматически утилизируется операционной системой.

В данном случае, действительно, без этих строк можно было обойтись. Но я сделал своей привычкой всегда освобождать память, динамически выделенную ранее, после того, как необходимость в её использовании отпадает. Эта привычка обусловлена, если угодно, некоторыми внутренними эстетическими ощущениями. Только программа, не допускающая утечку памяти, может быть, в моём понимании, гармоничной и законченной.

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

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

Но вернёмся к нашей программе. Её выполнение приводит к следующему выводу на консоль:

Итак, точное значение тысячного числа Фибоначчи получено! Как мы видим, первые его 7 цифр и количество знаков полностью согласуются с полученным нами ранее приблизительным значением.

Теперь переделаем вторую программу из предыдущего раздела:

Нам пришлось, помимо указателей a и b , ввести третий указатель — t , роль которого заключается во временном хранении содержимого той переменной, в которую записывается результат функции sum() , "затирающий" старое значение. После вызова данной функции уже не нужная нам переменная, чей адрес хранится в t , уничтожается. Таким образом, использование указателя t позволяет избежать утечки памяти.

Консольный вывод данной программы в точности совпадает с выводом предыдущей.

На этом всё. Исходный код программ, рассмотренных в этом разделе, можно скачать по приведённой ниже ссылке.