问题标签 [continued-fractions]

通读更多 SICP，我被困在练习 1.3.8上。我的代码适用于近似 1/phi，但不适用于近似 e - 2。

而不是为 e-2 获得 0.7 blah blah blah，我得到 0.5 blah blah 的东西。我不知道为什么。我很确定我在“eulers-e-2”函数中正确定义了“d”。

编辑：谢谢大家，我是倒过来计算的。这是固定代码。

（编辑：针对脾气暴躁的评论，不，这不是家庭作业。我正在研究音高检测，获取一系列潜在的谐波峰值，并尝试构建基频的候选对象。所以，这实际上是一个非常实际的问题。 )

考虑（例如）pi 的最佳分数近似值，按分母递增排序：3/1、22/7、355/113、...

挑战：创建一个整洁的C 算法，该算法将为给定的浮点数生成第 n 个商近似 a/b，同时返回差异。

calcBestFrac(float frac, int n, int * a, int * b, float * err) {...}

我认为最好的技术是连分数

去掉 pi 的小数部分，得到 3
现在，余数是 0.14159... = 1/7.06251..

所以下一个最好的有理数是 3 + 1/7 = 22/7
从 7.06251 中减去 7 得到 0.06251.. 大约是 1/15.99659..

称它为 16，那么下一个最佳近似值是
3 + 1/(7 + 1/16) = 355/113

但是，将其转换为干净的 C 代码绝非易事。如果我得到一些整洁的东西，我会发布。与此同时，有人可能会喜欢它作为脑筋急转弯。

前几天，Wolfram 博客发表了一篇关于 13 岁男孩 Neil Bickford 的文章，他计算了 pi 的简单连分数表示的前 4.58 亿项，以[3; 7, 15, 1, 292, ...]. Bickford在他的博客上描述了他的成就，甚至引用了Bill Gosper 的算法，但我一直无法计算出算法。

我知道的一件事是如何使用Wikipedia 关于连分数的文章中给出的方法将 pi 的十进制表示转换为连分数。但这需要 pi 的十进制表示到足够多的位数，而且 Bickford 肯定没有数百万位数的 pi 支持他的计算。

有人可以详细解释一下 Bickford 用来进行计算的算法吗？

我一直在研究 Project euler Problem 57（爱这个网站！）。对于这个问题，需要在有限连分数和正规分数之间进行转换。我设计了一种算法，它基本上取列表中最后一个数字的倒数，将其添加到倒数第二个并继续直到最后一个分数仍然存在。对于问题 67，它工作得非常好，但这次它在第二次迭代后停止工作（我必须对多个连分数执行算法）。

这是一段代码（我使用了一个外部模块，即 sympy）：

我基本上只是测试它是否得到了所有最后的分数，并且在返回之前从函数中打印出答案，但是在我将值分配给 sqrt_eval 之后的打印结果为 None。这是一个测试运行：

我一直在彻底寻找答案，但找不到答案。如果可以的话，请帮助我调试它，而无需过多更改代码。

我正在尝试编写一个 Matlab 函数来计算多少项 m，它需要黄金分数才能达到 n 位精度。这是我到目前为止所拥有的，但我一直得到 0 的输出。

我认为对于那些学习数论或刚开始学习 Matlab 的人来说，这是一个常见的问题。有什么建议吗？谢谢！

到目前为止，这是我想到的，适用于数组中的 2 个元素。数组中的元素是要插入连分数的变量。

顺便说一句，我没有使用递归，我需要能够获得连分数结果。

所以我正在实现一个连分数库来处理二次整数和有理数的子集。连分数项由无符号整数表示。在处理连分数时，我注意到以下一般模式：

1. 大多数术语都是小的个位数，其中 1 是最常见的。
2. 有些术语可能很大，对于我的应用程序来说最大的可能是 366 位，但这些非常罕见。
3. 较大的项表示一个特别好的数字近似，这意味着对于大部分而言，总体而言通常较少的项。
4. 最坏的连分数是黄金比例，366 位精度的有理近似值大约对应于连续 525 个 1。
5. 随机有理数通常不会有大量相同的数字，但可能有两到四个连续，其中 1 也是最常见的。

所以我对术语的数量和术语的大小都有限制，术语的数量与它们的大小大致成反比。所以将这些术语存储在机器字甚至字节中通常是非常浪费空间的，在最坏的情况下我仍然需要处理多字算术。鉴于术语大小和术语数量之间的大致反比关系（这两者都取决于分数的分子和分母的大小），我一直在尝试找到或提出一个好的压缩方案，这样我就不会浪费存储整数项的空间很大。

我考虑过Huffman encoding，因为编码和解码的速度很好，但我不确定如何得出代码值的概率。我有一种模糊的直觉，即Stern-Brocot 树可能会提供一个提示，因为它们是与连分数有直接关系的二叉树。

有谁知道一种很好的压缩方法来处理大量的小数字和偶尔的大数字，其中相同数字的运行通常很短（但在极少数情况下可能很长）？特别是我需要能够相当快地进行编码和解码（比如 O(n*lg(n)) 是我可以容忍的绝对最差的速度，O(n) 或更好），并且能够达到个别术语的位置，以便我知道我正在操作的术语编号（第四学期，第五学期等）。

另外，我对使用任何第三方实数或连分数库不感兴趣。我已经看过几个，它们要么不足以满足我的需求，要么过于矫枉过正，我想要自己编写代码以供我自己启迪的经验。

更新

我还了解了Gauss-Kuzmin 分布k，它给出了随机数在 0 和 1 之间均匀分布的特定连分数项的概率分布。它是

P(k) = -lg(1.0 - 1.0/((k + 1.0)**2)在 Python 伪代码中，其中 lg 是以 2 为底的对数。这是k接近无穷大的极限，所以我的情况受到更多限制（尽管2**366仍然很大）。Linas Vepstas 的“连分数的熵”给出了 Gauss-Kuzmin 分布的（信息）熵大约为 3.43 位。我的最大分母足够大，以至于我的连分数的信息熵可能接近该限制，尽管链接文章中的图表显示该限制的接近速度非常缓慢，因此对于相对较小的分母来说是不同的。

我的自然对数连分数算法有问题。我需要在 6 次迭代中以 1e-6 的精度计算自然对数，例如 ln(0.31)，我的算法将在 8 次中完成。

这是我的实现：

你们中有人知道如何改进我的代码吗？

我是 Python 新手，被要求创建一个程序，该程序将输入作为非负整数 n，然后使用连分数的前 n + 1 项计算 e 值的近似值：

我试图破译这个问题，但不能完全理解它所要求的一切。我不是在寻找一个确切的答案，而是希望有一个例子来帮助我。

这是确切的问题
下面是我之前用连分数完成的代码。

我目前在 Project Euler 的 Probelm 57 中工作：

https://projecteuler.net/problem=57

我的问题是，虽然我相信给出了正确的答案，但数字的计数似乎不正确。我不确定错误可能是什么。我已经包含了注释，希望能让我的代码更清晰。

我的代码正确识别 1393/985 分数，但在大约 i=30 之后，它似乎变得混乱（可能在某处溢出？）。

提前致谢！

PS显然答案是153，而我得到253