在不损失精度的情况下有效地逼近第n项

Question

问题给定g_n为

的递归关系

g₀ = c，其中为内容双精度体。
G _n = f(G _n-1)，其中f是线性函数

然后求另一个递归式

的值

h_n = g_n/exp(n)

约束条件包括:

1 & lt; = n & lt; = 10 ^ 9

在数学上，g(n)的值可以在log(n)时间内计算出来，然后h(n)可以很容易地计算出来，但问题是双精度数据类型的溢出。因此，上述策略只适用于n在1000左右的情况，而不适用于更大的n。请注意，h(n)的值可以在double

范围内。

实际的问题是我们试图从g(n)计算h(n)。我的问题是，有没有什么好方法可以直接计算h(n)，而不需要溢出双精度。

Answer 1

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))