在不损失精度的情况下有效地逼近第 n 项
Efficient approximation of nth term without losing accuracy
Probelem 给定 gn 的递归关系
g0 = c 其中是常量双精度数。
gn = f( gn-1 ) ，其中 f 是线性函数
然后求
给出的另一个递归的值
hn = gn/exp(n)
约束条件： 1 <= n <= 10^9
在数学上，g(n)的值可以在log(n)时间内计算出来，然后h(n)可以很容易地计算出来，但问题是double数据类型的溢出。所以上面的策略只适用于 1000 左右的 n，而不适用于更大的 n。请注意，h(n) 的值可以在 doubles
的范围内
实际问题是我们试图从 g(n) 计算 h(n)。我的问题是有什么好的方法可以直接计算h(n)而不会溢出双精度数。
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))
Probelem 给定 gn 的递归关系
g0 = c 其中是常量双精度数。
gn = f( gn-1 ) ，其中 f 是线性函数
然后求
给出的另一个递归的值hn = gn/exp(n)
约束条件： 1 <= n <= 10^9
在数学上，g(n)的值可以在log(n)时间内计算出来，然后h(n)可以很容易地计算出来，但问题是double数据类型的溢出。所以上面的策略只适用于 1000 左右的 n，而不适用于更大的 n。请注意，h(n) 的值可以在 doubles
的范围内实际问题是我们试图从 g(n) 计算 h(n)。我的问题是有什么好的方法可以直接计算h(n)而不会溢出双精度数。
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))