Оптимальный алгоритм для вычисления результата непрерывной дроби

Question

Непрерывная дробь - это серия делений такого типа:

depth   1    1+1/s

depth   2    1+1/(1+1/s)

depth   3    1+1/(1+1/(1+1/s))
  .     .      .           
  .     .      .      
  .     .      . 

Глубина - целое число, но s - число с плавающей запятой.

Какой будет оптимальный (с точки зрения производительности) алгоритм для вычисления результата для такой дроби с большой глубиной?

Answer 1

Подсказка: разверните каждую из этих формул, используя базовую алгебру. Вы увидите, как появляется шаблон.

Я покажу вам первые шаги, чтобы это стало очевидным:

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: если вы не видите очевидного паттерна, появляющегося из вышеприведенного, наиболее оптимальный алгоритм будет включать в себя вычисление чисел Фибоначчи (так что вам нужно будет Google для оптимального # генератора Фибоначчи).

Answer 2

Я хотел бы остановиться на превосходном ответе ДВК . Я буду придерживаться его обозначения f(d,s), чтобы обозначить искомое значение для глубины d.

Если вы вычислите значение f(d,s) для большого d, вы заметите, что значения сходятся по мере увеличения d.

Пусть & phi; = f (& infin;, s). То есть & phi; является пределом, когда d приближается к бесконечности, и является продолженной дробью, полностью расширенной. Обратите внимание, что & phi; содержит копию самого себя, так что мы можем написать & phi; = 1 + 1 / & phi ;. Умножение обеих сторон на & phi; и переставив, получаем квадратное уравнение

& phi; ² - & phi; - 1 = 0

, который можно решить, чтобы получить

& Phi; = (1 + & radic; 5) /2.

Это знаменитое золотое сечение .

Вы обнаружите, что f(d,s) очень близко к & phi; как d становится большим.

Но подождите. Там больше!

Как указывал ДВК, формула для f(d,s) включает в себя члены из последовательности Фибоначчи. В частности, он включает в себя отношения последовательных членов последовательности Фибоначчи. Для n-го члена последовательности существует выражение , а именно

(& Phi; * 1 037 * N - (1- & Phi;) * * п тысячу тридцать-девять ) / & Радич; 5.

С 1-го; меньше единицы, (1- & phi;) ⁿ становится меньше, когда n становится большим, поэтому хорошее приближение для n-го члена Фибоначчи равно & phi; ⁿ / & radic; , Возвращаясь к формуле ДВК, соотношение последовательных членов в последовательности Фибоначчи будет стремиться к & phi; ^{n + 1} / & phi; ⁿ = & phi;.

Итак, это второй способ добраться до того факта, что непрерывная дробь в этом вопросе оценивается как & phi;.

Answer 3

Я бы начал с вычисления 1/s, которое мы назовем a.

Затем используйте цикл for, поскольку, если вы используете рекурсию, в C вы можете столкнуться с переполнением стека.

Поскольку это домашнее задание, я не буду давать много кода, но, если вы начнете с простого цикла, равного 1, продолжайте увеличивать его, пока не доберетесь до 4, тогда вы можете просто перейти к n раз.

Поскольку вы всегда будете делить 1/s, а деление стоит дорого, простое выполнение одного раза поможет с производительностью.

Я ожидаю, что если вы решите это, вы действительно сможете найти шаблон, который поможет вам в дальнейшей оптимизации.

Может оказаться полезной статья, подобная этой: http://www.b -list.org / weblog / 2006 / nov / 05 / marketing-tips-learn-оптимизм-стратегии / , которая будет вам полезна.

Я предполагаю, что с точки зрения производительности вы хотите, чтобы она была быстрой, независимо от используемой памяти, между прочим.

Вы можете обнаружить, что если вы кэшируете значения, которые вы рассчитывали, на каждом шаге, вы можете использовать их повторно, вместо того, чтобы повторять дорогостоящие вычисления.

Я лично делал бы 4-5 шагов вручную, выписывая уравнения и результаты каждого шага, и смотрел бы, появляется ли какой-либо паттерн.

Обновление:

GCC добавил хвостовую рекурсию, и я никогда не замечал этого, так как я стараюсь сильно ограничить рекурсию в C по привычке. Но у этого ответа есть хорошее быстрое объяснение различных оптимизаций, которые gcc сделал на основе уровня оптимизации.

http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s

Answer 4

Пахнет как хвостовая рекурсия (рекурсия (рекурсия (...))).

(Другими словами - зацикливание!)