提问人：v78 提问时间：9/5/2015 更新时间：9/5/2015 访问量：65
在不损失精度的情况下有效逼近第n项
Efficient approximation of nth term without losing accuracy
问：
探针给定 gn 的递归关系为
g0 = c，其中是连续双精度。
g n = f（ gn-1 ） ，其中 f 是线性函数
然后找到另一个递归的值，由下式给出
h n = g n/exp（n）
约束：1 <= n <= 10^9
从数学上讲，g（n） 的值可以在 log（n） 时间内计算，然后 h（n） 可以很容易地计算，但问题是双精度数据类型的溢出。因此，上述策略仅适用于 1000 左右的 n，而不适用于更大的 n。请注意，h（n） 的值可以在双精度范围内
实际问题是我们试图从 g（n） 计算 h（n）。我的问题是，有没有好方法可以直接计算 h（n） 而不会溢出双精度。
答：
1赞
user1196549
9/5/2015
#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))
评论