Эффективное приближение n-го члена без потери точности

Задача Учитывая рекуррентное соотношение для gn в виде

g0 = c, где — постоянная двойная.
gn = f( gn-1 ) , где f – линейная функция.

затем найдите значение другого повторения, заданное выражением

hn = gn/exp(n)

ограничения: 1 ‹= n ‹= 10^9

Математически значение g(n) можно вычислить за время log(n), а затем h(n) можно вычислить очень легко, но проблема заключается в переполнении типов данных типа double. Таким образом, описанная выше стратегия работает только для n около 1000, но не для больших n. Обратите внимание, что значение h(n) может находиться в диапазоне двойных значений.

Настоящая проблема заключается в том, что мы пытаемся вычислить h(n) из g(n). Мой вопрос в том, что есть ли хороший способ вычислить h (n) напрямую без переполнения двойников.


recurrence algorithm floating-accuracy discrete-mathematics
person v78    schedule 05.09.2015    source источник
comment
Заменить f(x) на k(x) = f(x)/exp(1)?   -  person David Eisenstat    schedule 05.09.2015

Ответы (1)


arrow_upward
1
arrow_downward 

G0=c
G1=ac+b
G2=a²c+ab+b
G3=a³c+a²b+ab+b
...
Gn=a^nc+b(a^n-1)/(a-1)

потом

Hn = (a/e)^nc+b((a/e)^n-1/e^n)/(a-1) ~ (a/e)^n (c + b/(a-1))
person Yves Daoust    schedule 05.09.2015