代码之家 › 专栏 › 技术社区 › v78

不损失精度的第n项的有效逼近

recurrence discrete-mathematics floating-accuracy algorithm

1

v78 · 技术社区 · 11 年前

Probelem公司 给定g的递推关系 _n 像

克 ₀ =c,其中是连续双精度。
克 _n =f(g) _n-1个 ),其中f是线性函数

然后找到下式给出的另一个递推的值

小时 _n =克 _n /表达式(n)

约束条件: 1<=n<=10^9

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

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

1 回复 | 直到 11 年前

1

Yves Daoust 11 年前

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