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

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

recurrence discrete-mathematics floating-accuracy algorithm

v78 · 技术社区 · 9 年前

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 回复 | 直到 9 年前

Yves Daoust 9 年前

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

推荐文章

Beth · 双向查找子集c

7 年前

Lamda · 如何在数学上将窗口函数应用于matlab中的信号?

7 年前

ReeSSult · (P<->Q)和(Q<->R)的DNF

8 年前

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

9 年前

Ankit Kumar · 代码增长的算法顺序

10 年前

Hassnain · n的计算值

10 年前

ToBeGeek · 二部图论-从二部邻接矩阵中找到成对重叠(共享边)

10 年前

LandonSchropp · 老师的算法

11 年前

jnm2 · 计算NxN行列式的符号

11 年前