3

我正在尝试在 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]

from fractions import Fraction

def const(frac):
        """ CL bistream from a fraction >= 1 or 0. """
        while frac:
                if frac >= 2:
                        yield 1
                        frac = Fraction(frac, 2)
                else:
                        yield 0
                        frac -= 1
                        frac = Fraction(1, frac) if frac else 0

def rle(bit_seq):
        """ Run-length encoded CL bitstream. """
        s = 0
        for bit in bit_seq:
                s += bit
                if not bit:
                        yield s
                        s = 0

def floor(rle_seq):
        """ RLE CL terms of the greatest integer less than rle_seq. """
        #pass
        yield from output

""" Sample input/output pairs for floor(). """
num = Fraction(1234)
for den in range(1, int(num)+1):
        input  = list(rle(const(num  / den)))
        output = list(rle(const(num // den))) # Integer division!
        print(">  ", input)
        print(">> ", output) 
        print(">>*", list(floor(input))) 
        print()
        assert(list(floor(input)) == output)

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

4

1 回答 1

0

通过假设游程编码中的下一个系数是无限的，您可以获得一个下限。通过假设下一项为 1，您可以获得一个上限。

您可以简单地处理尽可能多的游程编码系数，直到您知道下限和上限都在半开区间 [N, N + 1) 中。在这种情况下，您知道连续对数的下限是 N。这类似于 Bill Gosper 在链接文档开头所做的事情。

但是请注意，此过程不一定会终止。例如，当您将 sqrt(2) 乘以 sqrt(2) 时，当然会得到数字 2。但是，sqrt(2) 的连续对数是无限的。要评估乘积 sqrt(2) * sqrt(2)，您将需要所有系数才能知道您最终会得到 2。对于任何有限数量的项，您无法确定乘积是否小于 2 或等于至少等于它。

请注意，此问题并非特定于连续对数，而是出现在任何系统中的基本问题，在该系统中，您可以有两个数字，其表示是无限的，但乘积可以用有限数量的系数表示。

为了说明这一点，假设这些协程输出的不是行程编码值，而是十进制数字，我们要计算 floor(sqrt(2) * sqrt(2))。经过多少步骤后，我们可以确定产品至少为 2？让我们取 11 位数字，看看会发生什么：1.41421356237 * 1.41421356237 = 1.9999999999912458800169

正如您可能猜到的那样，我们任意接近 2，但永远不会“达到”2。事实上，在不知道数字的来源是 sqrt(2) 的情况下，数字可能会在该点之后终止，并且产品最终低于 2。类似地，所有后续数字可能都是 9，这将导致产品略高于 2。

（一个更简单的例子是使用产生 0.9999 的例程......）

因此，在这些任意精度的数值系统中，您最终可能会遇到只能计算某个区间 (N - epsilon, N + epsilon) 的情况，在这种情况下，您可以使 epsilon 任意小，但绝不会等于零。不可能取这个表达式的底线，因为 - 通过所采用的数值方法 - 无法确定实际值最终会低于还是高于 N。

于 2020-10-30T22:03:04.983 回答