?

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

( 22 comments — Leave a comment )
_winnie
Jul. 9th, 2011 01:35 pm (UTC)
Про волшебные штаны не соображу, возможно он замаскировал знание, что штаны - это матрица.

Пусть матрица M равна
[0 1]
[1 1]

Тогда
[F(n-1)] = M  [F(n-2)]
[F(n)  ]      [F(n-1)]       
и
[F(n-1)]  =  Mn[0]
[F(n)  ]       [1]

и что бы вычислить F(n) достаточно возвести матрицу M в степень n, для чего используется известный алгоритм возведения в степень за LogN.
Матрицу можно хранить как два числа p,q, так как Mn выглядит как
[p q  ]
[q p+q]

Когда возвоздим матрицу p,q в квадрат, то
[p q  ]2   это [ p2 + q2   2pq + p2 ]
[q p+q]        [ 2pq + p2 ...       ]

Получаем те самые волшебные формулы.
fregimus
Jul. 9th, 2011 02:14 pm (UTC)
Bingo! А расскажите, как Вы догадались? Какую-то часть Вашего вывода Вы уже знали?
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)
Это примерно так же честно, как если бы он «Крэй» из кармана вынул и заткнул их за пояс программой на бейсике. Только если понятие оптимизации трактовать уж настолько широко…
_winnie
Jul. 9th, 2011 05:34 pm (UTC)
Я знаю (не помню откуда, может и сам придумал) про то что следующая пара чисел фиббоначи записывается как умножение матрице на предыдущую пару, и что можно их вычислять как Mn.

Так же знаю алгоритм возведения в степень.

Увидел этот пост, думаю, дай проверю, что если возводить матрицу в степень этим алгоритмом - то получатся те же чиселки, повезло.
fregimus
Jul. 9th, 2011 10:38 pm (UTC)
Ага, спасибо. Меня здесь занимает вопрос — я не до конца его сформулировал, все очень сыро — о том, какие рекуррентные отображения можно механически оптимизировать. Ну, и как.
irishoak
Jul. 9th, 2011 11:01 pm (UTC)
Любые. Тем же способом. Размер марицы только меняется...
Anatoly Borodin
Jul. 9th, 2011 11:09 pm (UTC)
Не любые, а линейные.
aamonster
Jul. 10th, 2011 08:10 pm (UTC)
Ну, как минимум подобные этому - когда у нас следующий член ряда зависит от N предыдущих и операции перехода вперёд по ряду ассоциативны (связанное ругательство - моноид...).
Anatoly Borodin
Jul. 10th, 2011 10:34 pm (UTC)
Не совсем так. Следующий член ряда должен линейно, с постоянными коэффициентами зависеть от предыдущих членов. Тогда можно построить соответствующую матрицу A, и ассоциативность будет уже в A^(n-1).
aamonster
Jul. 11th, 2011 06:08 am (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

Хотя я не все требуемые условия выписал... Еще "произведение" функций должно эффективно вычисляться - так что мой первый пример, скорее всего, не проходит.
Anatoly Borodin
Jul. 11th, 2011 11:55 am (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 (случай, не описывающийся матрицей, хе-хе)

Ну матрицей и вектором, беда какая :)

> Еще "произведение" функций должно эффективно вычисляться

Собственно.
my_tribune
Jul. 14th, 2011 06:11 am (UTC)
Ага, помню, что к чему-то похожему пришёл
Т.е. я тогда ещё не знал про матрицы, но надо было научиться быстро вычислять F(n) для больших n.
Тогда я игрался-игрался с формулками, выписывая их на тетрадный листик.
И в какой-то момент получил формулу, переводящую пару {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).
irishoak
Jul. 9th, 2011 05:06 pm (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-го порядка аналогично. Но с матрицами всё равно проще;)...

shabunc
Jul. 21st, 2011 05:06 am (UTC)
Re: Если без матриц...
зачем же так сложно, через пошагово разворачивающийся массив, можно вот так вот

Кажется, это то же самое.
shabunc
Jul. 21st, 2011 05:07 am (UTC)
Re: Если без матриц...
в восьмой строке последнее возвращаемое значение лишнее, но оно ничему не мешает.
( 22 comments — Leave a comment )