python - 续对数运算 : floor operator on run-length encoded terms

Question

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

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

我意识到模运算符大部分可以用我已有的操作来定义:

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

留下我唯一的问题。

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

'... the integer part of the log base 2 of the number remaining to be described.'

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

我编写了以下代码来测试输入项和预期的输出项，但我主要是在寻找实现 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)

How can I implement the floor operator in the spirit of continued fraction arithmetic by consuming terms only when necessary and emitting terms right away, and especially only using the run-length encoded format (in binary) rather than the unary expansion Gosper tends to describe.

Answer 1

通过假设游程编码中的下一个系数是无限的，您可以获得下限。通过假设下一项为 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。