Последние 40 цифр числа Фибоначчи, (Олимпиадная задача) Опции

[Гость]

Вот недавно встертил интересную задачку:
Нужно вывести последние 40 цифр n-ого числа фибонначи,
где n<10^18, вот и все

[klem4]

Гость , я думаю вам поможет FAQ : Длинная арифметика, числа > LongInt

Сообщение отредактировано: klem4 - 15.03.2006 13:44

[Lapp]

я думаю вам поможет Длинная арифметика

klem4, тут дело не в этом. Или не совсем в этом. Я уже второй день думаю над этой задачей..
Первое поползновение - прикинуть количество операций для расчета 10^18-го числа Фибоначи. Собственно, тут и прикидывать не надо. Положим, что на сложение двух предыдущих уходит один цикл (что явно неверно для длинной арифметики, но это есть оценка снизу). Далее, берем машину, работающую на 3 ГГц. В час она выполнит 10^9*3*3600 сложений, что приблизительно есть 10^13. Получается, что нужно 10^5 часов. Будем считать, что в году 10000 часов (приблизительно). И получится, что на расчеты нам потребуется 10 лет.. А на длинную арифметику нужно как минимум десятку накинуть! Сто лет..
Но самое интересное не в этом. На хранение одного только последнего числа уйдет количесво памяти, сравнимое с произведенным на данный момент на всей Земле..

Конечно, можно считать только последние 40 знаков, тогда вопрос с памятью отпадает, но вопрос с временем остается.. Я долго думал, и придумал, что должна быть периодичность в младших разрядах. Стал вычислять - и действительно ее обнаружил. Но только это не решает проблемы, поскольку период растет медленно.. Будем думать дальше!

Разделено в отдельную тему, т.к. в ПЕРВОМ ЖЕ ПОСТЕ прикрепленной темы русским языком написано:

Внимание!
В этой теме публикуем только сами задачи и их решения... Обсуждения - в отдельных темах!!!

Сообщение отредактировано: volvo - 16.03.2006 13:40

[Altair]

ну так есть же формула для вычисления n-ого числа Фиббоначи.
Используем ее +длинную арифметику и вычисляем....

[Lapp]

Altair, ты гений!
Про формулу Бине я однозначно забыл [жжет лист бумаги, собирает пепел и посыпает голову]... А она ведь дает точное значение до последнего знака!

Но с нахрапа все равно не получается взять. Там фигурирует n-ая степень выражения, содержащего Sqrt(5). Если бы был просто корень из пяти, без слагаемых - то просто поделил n на два, потом дихотомией вычислить 5^(n/2). При этом n должно быть четным, но это ерунда - нечетное ЧФ вычислим по двум боковым четным. Вычислять в лоб (брать корень, прибавлять 1, делить пополам и возводить в степень дихотомическим умножением) нельзя, т.к. вычислять корень придется с точностью до 10^18 знаков..

Думаем.. [скрип мозгов за кадром]

[volvo]

Или возведением матрицы

     | 0   1 |
 A = |       |
     | 1   1 |,

в степень N (что можно сделать за O(log n) операций, также как и при вычислении по формуле Бине, но по-моему, с матрицей будет проще в смысле ошибок округления, т.к. можно будет работать именно с целочисленной длинной арифметикой)...