?

Log in

No account? Create an account

Previous Entry | Next Entry

Интересный вопрос, на который я не смог ответить, обсуждая одну задачу (задание 1. 19 из sicp) с учеником. Пресловутый «детский вопрос». Впрочем, начнем по порядку.

Как вы помните, числа Фибоначчи определяются через суммирование предыдущих членов в ряду: каждое число равно сумме двух предыдущих, а первые два равны 1. Таким образом, получается ряд натуральных чисел { 1; 1; 2; 3; 5; 8; 13; 21; … }. Обозначим n-ный член этого ряда через F(n). Мы можем определить рекуррентную формулу для F(n):

F(n) = F(n − 1) + F(n − 2)
F(1) = F(2) = 1

Попытка применить эту формулу для практического вычисления неэффективна до нелепости: например, чтобы вычислить F(5), мы сначала вычислим F(4) и F(3), a вычисляя F(4), мы должны вычислить F(3) и F(2). F(3) уже вычисляется дважды. Легко видеть, что при вычислении для больших n число повторов растет, будто лавина.

Естественно упростить вычисление, двигаясь от начала ряда. Если мы каждый раз будем помнить только 2 числа в их порядке, по ним мы можем вычислить третье, «забыть» первое — оно больше не нужно — и повторять эту операцию с оставшимися двумя, пока не сделаем нужного числа шагов. Этот метод гарантирует вычисление F(n) за число шагов n−2, то есть, как об этом говорится, порядка n, и общепринято записывается как O(n).

Новое рекуррентное соотношение для F потребует введения вспомогательной функции, которая будет «помнить» два числа в своих аргументах. Третий аргумент нужен только, чтобы завершить вычисления, не забыть, где нам остановиться, идя вдоль ряда Фибоначчи: он задает число оставшихся шагов:



А теперь приходит добрый волшебник Хэл Абельсон и говорит: я знаю, как значительно ускорить это вычисление! Можно модифицировать алгоритм, чтобы «перескакивать» в ряду шагами, кратными 2n. Тут он достает из широких В условии задачи приводится отображение

ψ (p, q) (a, b) → ψ (p, q) ((a + b)p + aq, ap + bq)

Хорошо видно, что

φ = ψ (1, 0)

Теперь аналитически применим функцию ψ дважды к данным a и b



Обратите внимание, что форма этого выражения соответствует однократному применению ψ, но только с иными значениями p и q:

pp² + 2pq
qp² + q²

Таким образом, рекуррентная самотождественность ψ сохранилась, и мы можем удваивать наши шаги каждый раз, когда обнаружим, что до нашего F(n) их остается четное число: просто заменим p и q на новые, соответствующие двойному шагу, и при этом вдвое уменьшим число оставшихся шагов. Полное решение можно записать так:



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

А вот и детский вопрос, поставивший меня в тупик: как именно добрый волшебник Хэл Абельсон пришел именно к такой форме функции ψ? Признаюсь, я с размаху сел в лужу. Давайте меня коллективно из нее доставать. Как определить, что для данного рекуррентного отношения существует самоподобное решение для перепрыгивания через 2 или несколько шагов? И, конструктивно, — как его отыскать?

___________________________
LaTeX to image conversion
CodeCogs - An Open Source Scientific Library

Tags:

Comments

fat_crocodile
Jul. 9th, 2011 02:23 pm (UTC)
Кажется в той же первой главе было про эту матрицу и возведение её в степень (раньше или позже -- не помню).
fregimus
Jul. 9th, 2011 02:24 pm (UTC)
Перечитаю. Я тоже не помню.
fregimus
Jul. 9th, 2011 02:44 pm (UTC)
Не, нет ничего. Только ссылка на Kaldewaij (1990). Найду ее, что ли. Вы не там это видели?
fat_crocodile
Jul. 9th, 2011 02:58 pm (UTC)
Странно, был уверен, что оттуда, но тоже просмотрел и тоже не нашёл.
Нет, Kaldewaij я точно не читал.

Но это в общем-то даже в вики есть (последний пункт в тождествах):
http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#.D0.A2.D0.BE.D0.B6.D0.B4.D0.B5.D1.81.D1.82.D0.B2.D0.B0
aamonster
Jul. 10th, 2011 08:12 pm (UTC)
Я где-то встречал байку, как C-шники с ассемблерщиками бились, кто лучше оптимизирует числа фиобначчи... И вылез какой-то перец с этим алгоритмом.
fat_crocodile
Jul. 10th, 2011 08:17 pm (UTC)
Ну, если в рамках машинного слова, то вполне вероятно, что линейный вариант на ассемблере зарулит логарифмический на С. Особенно если в слове 2-4 байта.
Ассимптотика, конечно, в пользу логарифма.
aamonster
Jul. 10th, 2011 08:22 pm (UTC)
В рамках машинного слова мериться нечем, мерились вычислением миллионного, что ли, числа (что предполагает реализацию длинной арифметики).
Сишники кричали, что сейчас компилятор оптимизирует лучше человека... ассемблерщики - что человек лучше. А потом вылез человек чуть ли не с вижуал бейсиком и всех порвал.
fregimus
Jul. 12th, 2011 01:23 am (UTC)
Это примерно так же честно, как если бы он «Крэй» из кармана вынул и заткнул их за пояс программой на бейсике. Только если понятие оптимизации трактовать уж настолько широко…