Оптимальный алгоритм для вычисления результата непрерывной дроби
Непрерывная дробь является серией подразделений этого вида:
depth 1 1+1/s
depth 2 1+1/(1+1/s)
depth 3 1+1/(1+1/(1+1/s))
. . .
. . .
. . .
Глубина является целым числом, но s число с плавающей точкой.
Каков был бы оптимальный алгоритм (мудрый производительностью) для вычисления результата для такой части с большой глубиной?
4 ответа
Подсказка: разверните каждую из этих формул, используя базовую алгебру. Вы увидите закономерность.
Я покажу вам первые шаги, чтобы все стало очевидно:
f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1) / (s + 1)
/* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2) / (2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3) / (3*s + 2)
...
Подсказка2: если вы не видите очевидной закономерности, вытекающей из вышеизложенного, то наиболее оптимальным алгоритмом будет вычисление чисел Фибоначчи (поэтому вам нужно будет погуглить на предмет оптимального генератора чисел Фибоначчи).
Я бы начал с вычисления 1 / с , которое мы назовем a .
Затем используйте цикл for, поскольку, если вы используете рекурсию в C, вы можете столкнуться с переполнением стека.
Поскольку это домашнее задание, я не буду приводить много кода, но, если вы начнете с простого цикла, равного 1, а затем продолжайте увеличивать его, пока не дойдете до 4, тогда вы можете просто перейти к n раз.
Поскольку вы всегда будете делить 1 / с , а деление обходится дорого, простое выполнение этого единовременного деления поможет повысить производительность.
Я ожидаю, что если вы проработаете это, вы действительно сможете найти шаблон, который поможет вам в дальнейшей оптимизации.
Вы можете найти такую статью: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/ , чтобы быть полезным.
Я полагаю, говоря о производительности, вы имеете в виду, что хотите, чтобы он был быстрым, независимо от используемой памяти, кстати.
Вы можете обнаружить, что если вы кэшируете вычисленные вами значения на каждом шаге, вы можете использовать их повторно, а не повторять дорогостоящие вычисления.
Я лично делал 4-5 шагов вручную, записывая уравнения и результаты каждого шага, и смотрел, появляется ли какая-то закономерность.
Обновление:
GCC добавил хвостовую рекурсию, и я никогда этого не замечал, так как по привычке стараюсь сильно ограничить рекурсию в C. Но в этом ответе есть хорошее быстрое объяснение различных оптимизаций, которые gcc сделал на основе уровня оптимизации.
http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s
Попахивает хвостовой рекурсией(рекурсией(рекурсией(...))))
(Другими словами - loop it!)
Я бы хотел подробнее остановиться на отличном ответе ДВК . Я буду придерживаться его обозначения f (d, s) для обозначения искомого значения глубины d .
Если вы вычислите значение f (d, s) для большого d , вы заметите, что значения сходятся по мере увеличения d .
Пусть φ = f (∞, s). То есть φ - это предел, поскольку d приближается к бесконечности, и является полностью раскрытой непрерывной дробью. Обратите внимание, что φ содержит копию самого себя, поэтому мы можем записать φ = 1 + 1 / φ. Умножая обе части на φ и переставляя, мы получаем квадратное уравнение
φ 2 - φ - 1 = 0
, которое можно решить, чтобы получить
φ = (1 + √5) / 2.
Это известное золотое сечение .
Вы обнаружите, что f (d, s) очень близко к φ, когда d становится больше.
Но подождите. Есть больше!
Как указал ДВК, формула для f (d, s) включает члены из последовательности Фибоначчи.В частности, он включает отношения последовательных членов последовательности Фибоначчи. Существует выражение в закрытой форме для n-го члена последовательности , а именно
(φ n - (1-φ) n ) / √5 .
Поскольку 1-φ меньше единицы, (1-φ) n становится малым по мере того, как n становится большим, поэтому хорошее приближение для n-го члена Фибоначчи - φ n / √5. И возвращаясь к формуле ДВК, отношение последовательных членов в последовательности Фибоначчи будет стремиться к φ n + 1 / φ n = φ.
Итак, это второй способ понять, что непрерывная дробь в этом вопросе оценивается как φ.