问题标签 [continued-fractions]

我编写了这段代码来使用欧几里得算法计算有理数 N 的连分数展开式：

如果说 N 是 3.245，则函数永远不会结束，因为显然 f 永远不会等于 0。展开的前 10 项是：

[3.0、4.0、12.0、3.0、1.0、247777268231.0、4.0、1.0、2.0、1.0]

这显然是一个错误，因为实际的扩展只是：

[3;4,12,3,1] 或 [3;4,12,4]

是什么导致了这里的问题？是某种舍入误差吗？

在 SICP 练习 1.37 中

SICP 中的第 1.3.3 节向下滚动到节的末尾（就在 1.3.4 之前）以找到练习[该节中的第三个练习]。

根据问题，我将 cont-frac 定义为

链接到练习的解决方案

根据解决方案链接，上面的代码似乎是一致的。当 n 和 d 被替换为 时，问题出现在解决方案的第二部分，在解决方案的(lamda (i) 1.0)(a) 部分，这是一个过程。

我无法理解在cont-frac. 当我尝试时，出现错误类型的参数

编辑 1

我已经添加了我的整个解决方案。它解决了问题，但没有抓住该部分的本质。这是练习 1.37、1.38 和 1.39 的解法。该程序不使用以下链接的解决方案作为通用方法的程序 解决方案 1.37，解决方案 1.38和解决方案 1.39

在下面
的程序phi和程序中e-2-val，k是程序中连分数
的步数tan，k是以弧度为单位的角度（准确值的步数为1000）

我想使用连分数进行数字水印。我需要使用连分数的概念来评估一个数字。谁能提供连分数的matlab代码？

这里我将使用符号

可以通过计算它然后应用定义来找到一个数字的连分数，但这需要至少 O(n) 位的内存才能找到一个₀，一个₁ ...一个_n，实际上它是一个多更差。使用双浮点精度只能找到₀、₁ ... a ₁₉。

另一种方法是使用这样一个事实：如果 a,b,c 是有理数，则存在唯一有理数 p,q,r 使得 1/(a+b*2 ^1/3 +c*2 ^2/3 ) = x +y*2 ^1/3 +z*2 ^2/3，即

因此，如果我使用 boost 有理库将 x、y 和 z 表示为绝对精度，我只能使用 2 1/3 的双精度准确地获得 floor(x + y*2 ^1/3 + ^z *2 ^2/3 )和2 ^2/3因为我只需要它在真实值的 1/2 以内。不幸的是，x、y 和 z 的分子和分母增长得相当快，如果你使用常规浮点数，错误会很快堆积起来。

通过这种方式，我能够在一小时内计算出₀、₁ ... ₁₀₀₀₀，但不知何故，mathematica 可以在 2 秒内完成。这是我的代码供参考

我们知道 Pell 方程表示为

在 D 不是完全平方的情况下，可以通过 D 的连分数展开来近似，例如让我们考虑这种方程

61的平方根可以通过以下matlab代码来近似

但我有一个问题：如何将结果分配给两个单独的变量？即

从这个网站 https://www.quora.com/What-is-the-fast-way-to-solve-the-fundamental-solution-of-Pell-equation

我知道解决方案是基于分子和分母的，如何在 matlab 的代码中将分数部分分配给 x 和 y？提前致谢

这有点被问到了，但不是这样。我有一个小 Python 程序，它可以找到 n (1 <= n <= 10000) 平方根的连分数。

我一直在尝试在 Julia 中做到这一点，但我不知道该怎么做。主要是因为它处理无理数（如果 x 不是完全平方，则 sqrt(x) 是无理数，例如 sqrt(2) = 1.414213...）。所以我认为我不能使用理性类。

它在这里说https://docs.julialang.org/en/latest/manual/integers-and-floating-point-numbers/#Arbitrary-Precision-Arithmetic-1 Julia 可以使用 BigFloats 进行任意精度算术。但它们似乎不够准确。

我也尝试在 Python 中使用 PyCall 和 Decimals 包（来自 Julia），但出现奇怪的错误（如果它们有帮助，我可以发布它们）。

这是我的 Python 程序。我的问题是如何在 Julia 中做到这一点？

如您所见，我需要一种计算精确平方根的方法，以及一种获取数字整数部分的方法。这就是真的，除了很多很多的精度！

伙计们，我没有发布我的 Julia 代码，因为我不想有一个小手稿来回答！但在这里，它有效。正如我在下面的评论中所说，我使用 setprecision 函数将精度设置为一个高值并且它可以工作。我凭经验得到了 711 的值。

所以无论如何，user2357112解决了它，非常感谢。

我正在尝试在 Bill Gosper 的连续对数上实现基本算术，这是连续分数的“突变”，允许术语协同例程即使在非常大或非常小的数字上也能发出和消耗非常小的消息。

可逆算术，例如 {+,-,*,/} 至少在一元表示中由 Gosper 相当直接地描述，但我很难实现有效地从除法运算中截断信息的模运算符。

我已经意识到模运算符主要可以用我已经拥有的操作来定义：

a mod b == a - b * floor(a / b)

留下我唯一的问题是地板。

我还读到连续对数的行程编码格式有效地描述了

'...待描述的剩余数字的以 2 为底的对数的整数部分。

因此，立即产生第一项（通过）到目前为止会产生正确的输出，但仍有很大一部分有待确定，我认为这需要某种进位机制。

我编写了以下代码来测试输入项和预期的输出项，但我主要是在寻找实现 floor 背后的高级算法思想。

输出对的示例输入 (1234 / 5) 是

输入：[7, 0, 3, 0, 0, 0, 0, 1, 3, 3, 1]

输出：[7, 0, 3, 1, 4, 2, 1, 1]

我如何才能本着连分数算术的精神实现地板运算符，仅在必要时使用项并立即发出项，尤其是仅使用游程编码格式（二进制）而不是 Gosper 倾向于描述的一元展开。

如何在 Python 中将分数转换为连分数？我试着环顾四周，发现有人使用 Fraction 模块来做与我的问题类似的事情，但我没有设法修改它们。我发现的图像示例：

所以如果输入是181 101，那么输出应该是1 1 3 1 4 4。提前谢谢！

编辑：已解决，但由于解决方案在评论中，我不能接受我自己的解决方案，直到明天它仍然开放。再次非常感谢这个伟大的社区及其人民

可选上下文：我正在计算 Pell 方程的解

http://mathworld.wolfram.com/PellEquation.html

页面底部是一个表格，其中包含 D -> x, y 的值。我的代码对除 D = 61 之外的每个值都非常有效。我相信它可能与 x 和 y 的值非常大有关，也许分数模块无法处理如此大的数字并且存在溢出？我观察到，无论我将输入/起始值作为分数还是小数给出都会改变我的解决方案（但仅适用于 D = 61）。为什么我的代码以 D = 61 的值失败？我需要更改/使用什么才能使其正常工作？非常感谢您的时间和帮助。

代码：

我正在尝试实现一个递归函数，它接受一个浮点数并返回一个整数列表，表示浮点数的连分数表示（https://en.wikipedia.org/wiki/Continued_fraction）一般我想我理解算法是如何应该工作。它相当简单。我到目前为止是这样的：

问题显然与基本情况有关。似乎 r 的值永远不会减少到 0.0，而是算法继续返回类似于 0.0 .....[number] 的值。我只是不确定如何进行比较。我到底应该怎么做。该函数所基于的算法说基本情况是 0，所以我自然将其解释为 0.0。我没有看到任何其他方式。另外，请注意这是一个任务，明确要求我递归地实现算法。有人对我有一些指导吗？将不胜感激