algorithm - 处理递归函数时如何提高(mathematica)性能？

Question

背景。我想打印 31^(1/2) 的收敛表。我对表进行了以下递归定义。 (将 31^(1/2) 与黄金比例交换，下表将包含斐波那契数列)。

 cf := ContinuedFraction
 tf := TableForm
 p[-1] = 0; p[0] = 1; q[-1] = 1; q[0] = 0;
 a[k_] := cf[Sqrt[31], k][[k]]
 p[k_] := a[k]*p[k - 1] + p[k - 2]
 q[k_] := a[k]*q[k - 1] + q[k - 2]
 s[n_] := Timing[Table[{k, a[k], p[k], q[k]}, {k, 8, 8 n, 8}]] // tf

时间呈指数增长。我不得不 alt+。 (中止)为 s[4]。

问题:在处理递归函数时如何提高(mathematica)性能？

Answer 1

从快速(不彻底，承认)看你的代码，看起来 p 和 q 都是根据 two 递归定义的 以前的值。这意味着要计算 p 的第 n 值，需要进行 ~2^n 评估(每一步都使数字加倍)。所以是的，无论使用 Mathematica 还是任何其他语言，复杂性都是指数级的。

如果您坚持使用问题的递归公式(例如为了简单起见)，那么减少性能损失的最简单方法是使用 memoization ，即做类似的事情

p[k_] := p[k] = a[k]*p[k - 1] + p[k - 2]

不要忘记在任何重新定义之前Clear[p]。

简而言之，memoization 意味着让函数记住每个输入的计算结果，以便后续评估更快。从两个先前的值(p_(n) 和 p_(n-1))计算 两个 值(p_(n+1) 和 p_(n))很可能更快，但更复杂，那么复杂度将是线性的而不是指数的。

_{希望对您有所帮助。我现在没有 Mathematica 可以测试。}