![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
fregimusИнтересный вопрос, на который я не смог ответить, обсуждая одну задачу (задание 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 потребует введения вспомогательной функции, которая будет «помнить» два числа в своих аргументах. Третий аргумент нужен только, чтобы завершить вычисления, не забыть, где нам остановиться, идя вдоль ряда Фибоначчи: он задает число оставшихся шагов:
\&space;n\rightarrow\begin{cases}a,&n=0\\\varphi\&space;(a+b,a)\&space;(n-1),&n>0\end{cases}\\\\F\&space;1\rightarrow&space;1\\F\&space;n\rightarrow\varphi\&space;(1,1)\&space;(n-1)\end{array})
А теперь приходит добрый волшебник Хэл Абельсон и говорит: я знаю, как значительно ускорить это вычисление! Можно модифицировать алгоритм, чтобы «перескакивать» в ряду шагами, кратными 2n.Тут он достает из широких В условии задачи приводится отображение
ψ (p, q) (a, b) → ψ (p, q) ((a + b)p + aq, ap + bq)
Хорошо видно, что
φ = ψ (1, 0)
Теперь аналитически применим функцию ψ дважды к данным a и b
\&space;(a,b)&\rightarrow&space;\psi\&space;(p,q)\&space;((a+b)p+aq,ap+bq)\\&\rightarrow\psi\&space;(p,q)\&space;((((a+b)p+aq)+(ap+bq))p+((a+b)p+aq)q,((a+b)p+aq)p+(ap+bq)q)\\&=\psi\&space;(p,q)\&space;((ap+bp+aq+ap+bq)p+(ap+bp+aq)q,(ap+bp+aq)p+(ap+bq)q)\\&=\psi\&space;(p,q)\&space;(ap^2+bp^2+apq+ap^2+bpq+apq+bpq+aq^2,ap^2+bp^2+apq+apq+bq^2)\\&=\psi\&space;(p,q)\&space;(ap^2+bp^2+2apq+2bpq+ap^2+aq^2,ap^2+2apq+bp^2+bq^2)\\&=\psi\&space;(p,q)\&space;((a+b)(p^2+2pq)+a(p^2+q^2),a(p^2+2pq)+b(p^2+q^2))\end{align*})
Обратите внимание, что форма этого выражения соответствует однократному применению ψ, но только с иными значениями p и q:
p → p² + 2pq
q → p² + q²
Таким образом, рекуррентная самотождественность ψ сохранилась, и мы можем удваивать наши шаги каждый раз, когда обнаружим, что до нашего F(n) их остается четное число: просто заменим p и q на новые, соответствующие двойному шагу, и при этом вдвое уменьшим число оставшихся шагов. Полное решение можно записать так:
\&space;(a,b)\&space;n\rightarrow\begin{cases}a,&n=0\\\psi\&space;(p,q)\&space;((a+b)p+aq,ap+bq)\&space;(n-1),&space;&n\&space;\text{mod}\&space;2=1\\\psi\&space;(p^2+2pq,p^2+q^2)\&space;(a,b)\&space;(n/2),&space;&n\&space;\text{mod}\&space;2=0\\\end{cases}\\\\F\&space;1\rightarrow&space;1\\F\&space;n\rightarrow\psi\&space;(1,0)\&space;(1,1)\&space;(n-1)\end{array})
Очевидно, что перед каждым удвоенным шагом мы будем делать не более одного неудвоенного, так что число шагов будет падать вдвое на каждые не более двух сделанных, так что новый алгоритм вычисляет F(n) за логарифмическое число шагов O(log n).
А вот и детский вопрос, поставивший меня в тупик: как именно добрый волшебник Хэл Абельсон пришел именно к такой форме функции ψ? Признаюсь, я с размаху сел в лужу. Давайте меня коллективно из нее доставать. Как определить, что для данного рекуррентного отношения существует самоподобное решение для перепрыгивания через 2 или несколько шагов? И, конструктивно, — как его отыскать?
___________________________
LaTeX to image conversion
Как вы помните, числа Фибоначчи определяются через суммирование предыдущих членов в ряду: каждое число равно сумме двух предыдущих, а первые два равны 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:
p → p² + 2pq
q → p² + q²
Таким образом, рекуррентная самотождественность ψ сохранилась, и мы можем удваивать наши шаги каждый раз, когда обнаружим, что до нашего F(n) их остается четное число: просто заменим p и q на новые, соответствующие двойному шагу, и при этом вдвое уменьшим число оставшихся шагов. Полное решение можно записать так:
Очевидно, что перед каждым удвоенным шагом мы будем делать не более одного неудвоенного, так что число шагов будет падать вдвое на каждые не более двух сделанных, так что новый алгоритм вычисляет F(n) за логарифмическое число шагов O(log n).
А вот и детский вопрос, поставивший меня в тупик: как именно добрый волшебник Хэл Абельсон пришел именно к такой форме функции ψ? Признаюсь, я с размаху сел в лужу. Давайте меня коллективно из нее доставать. Как определить, что для данного рекуррентного отношения существует самоподобное решение для перепрыгивания через 2 или несколько шагов? И, конструктивно, — как его отыскать?
___________________________
LaTeX to image conversion
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
2011-07-09 13:06 (UTC)(no subject)
2011-07-09 13:35 (UTC)Пусть матрица M равна
Тогда
и что бы вычислить F(n) достаточно возвести матрицу M в степень n, для чего используется известный алгоритм возведения в степень за LogN.
Матрицу можно хранить как два числа p,q, так как Mn выглядит как
Когда возвоздим матрицу p,q в квадрат, то
Получаем те самые волшебные формулы.
(no subject)
2011-07-09 14:14 (UTC)(no subject)
2011-07-09 14:23 (UTC)(no subject)
2011-07-09 14:24 (UTC)(no subject)
2011-07-09 14:44 (UTC)(no subject)
2011-07-09 14:58 (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
Если без матриц...
2011-07-09 17:06 (UTC)Все последовательности, удовлеворяющие сооношению "типа Фибоначчи", образуют двумерное пространство. Это значит, что если мы, скажем, у двух представителей знаем нулевой и первый, а также k-й члены, то мы умеем _быстро_ вычислять k-й член любого представителя по его нулевому и первому. Действительно, достаточно понять, как этот представитель выражается через двух изначальных.
Это немедленно приводит к формуле
a(n) = a(0)F(n-1) + a(1)F(n)
(здесь мы сводим всё к двум последовательностям, начинающимся с (F(-1), F(0)) = (1,0)
и (F(0), F(1)) = (0, 1) --- вот чем удобны именно Фибоначчи),
а значит,
F(2n) = F(n)F(n-1) + F(n+1)F(n) = F(n) (2F(n-1)+F(n)) = F(n) (2F(n+1)-F(n)),
F(2n-1) = F(n-1)^2 + F(n)^2.
Итак, зная пару (F(n-1), F(n)), мы можем узнать как пару (F(2n-2), F(2n-1)), так и пару (F(2n-1), F(2n)), что и даёт нам возможность вычислить любое число Фибоначчи за log n операций.
Для других соотношений 2-го порядка аналогично. Но с матрицами всё равно проще;)...
(no subject)
2011-07-09 17:34 (UTC)Так же знаю алгоритм возведения в степень.
Увидел этот пост, думаю, дай проверю, что если возводить матрицу в степень этим алгоритмом - то получатся те же чиселки, повезло.
(no subject)
2011-07-09 22:38 (UTC)(no subject)
2011-07-09 23:01 (UTC)(no subject)
2011-07-09 23:09 (UTC)(no subject)
2011-07-10 20:10 (UTC)(no subject)
2011-07-10 20:12 (UTC)(no subject)
2011-07-10 20:17 (UTC)Ассимптотика, конечно, в пользу логарифма.
(no subject)
2011-07-10 20:22 (UTC)Сишники кричали, что сейчас компилятор оптимизирует лучше человека... ассемблерщики - что человек лучше. А потом вылез человек чуть ли не с вижуал бейсиком и всех порвал.
(no subject)
2011-07-10 22:34 (UTC)(no subject)
2011-07-11 06:08 (UTC)Т.е. для ряда a[0], a[1], ... (для чисел фибоначчи член ряда - вектор из двух чисел) и функции f:
a[n+1] = f(a[n]) должна быть определена операция "умножения" <*> такая, что:
(f <*> g) a = f(g(a))
(f <*> g) <*> h = f <*> (g <*> h)
Ну и нужна "единица" I
f <*> I = I <*> f = f
Примеры:
a[0] = ""
a[n+1] = a[n] ++ "!"
(++ - операция слияния строк)
a[0] = 1
a[n+1] = a[n]+1 (случай, не описывающийся матрицей, хе-хе)
a[0] = 1
a[n+1] = a[n]*2
Хотя я не все требуемые условия выписал... Еще "произведение" функций должно эффективно вычисляться - так что мой первый пример, скорее всего, не проходит.
(no subject)
2011-07-11 11:55 (UTC)Для любой последовательности a_n = (f ^ (n - 1)) (a_1), вопрос в том, для каких f можно эффективно вычислять степени.
Ещё есть фокус через изоморфизм:
g = (h^-1) . f . h
(h^-1) . a_n . h = (g ^ (n - 1)) ((h^-1) . a_1 . h)
Так вычисление чисел Фибоначчи сводится к возведению в степень диагональной матрицы с собственными значениями (1 ± sqrt 5) / 2
> a[n+1] = a[n]+1 (случай, не описывающийся матрицей, хе-хе)
Ну матрицей и вектором, беда какая :)
> Еще "произведение" функций должно эффективно вычисляться
Собственно.
(no subject)
2011-07-12 01:23 (UTC)Ага, помню, что к чему-то похожему пришёл
2011-07-14 06:11 (UTC)Тогда я игрался-игрался с формулками, выписывая их на тетрадный листик.
И в какой-то момент получил формулу, переводящую пару {F(n), F(n+1)} в {F(2n), F(2n+1)} всего за пару-тройку умножений и сложений. Ну а дальше уже было просто - закодировать это всё на C (пришлось ещё длинную арифметику реализовать, конечно).
Кстати, оказалось, что никакого nlogn не получается, потому что длинная арифметика работает тем медленнее, чем больше наши числа (сейчас это не удивительно, а тогда слегка расстроило). Т.е. большие числа Фибоначчи считать было всё равно очень долго (пусть и на порядки быстрее, чем "в лоб"). Поэтому пришлось ещё добавить таблицу заранее насчитанных значений: хранил пару {F(10^6), F(10^6+1)}, {F(10^7), F(10^7+1)}, и так далее (дальше мельчить пришлось, а не идти по степеням десятки). Это позволило добиться хорошей производительности на компьютерах того времени (уже и не вспомню, было ли там хотя бы 100Mhz).
Re: Если без матриц...
2011-07-21 05:06 (UTC)Кажется, это то же самое.
Re: Если без матриц...
2011-07-21 05:07 (UTC)