续对数算法:游程长度编码项上的下限运算符 [英] Continued logarithm arithmetic: floor operator on run-length encoded terms

问题描述

我正在尝试对比尔·戈斯珀(Bill Gosper)的连续对数进行基本算术，这是连续分数的突变"，允许术语例程"即使在非常大或非常小的数字上也可以发出和使用非常小的消息.

Gosper至少以一元表示形式相当直观地描述了诸如{+，-，*，/}之类的可逆算法，但是我很难实现有效地从除法运算中截断信息的模运算符./p>

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

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

剩下我唯一的问题.

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

'......对数以2为底的整数部分描述."

因此，立即产生(通过)第一个术语会产生正确的输出，但仍有很大一部分待确定，我认为这需要某种进位机制.

我已经编写了以下代码来测试输入项和预期的输出项，但是我主要是在寻求实施底层的基础上寻找高级算法思路.

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

输入:[7，0，3，0，0，0，0，1，3，3，1]

输出:[7，0，3，1，4，2，1，1]

来自分数的

 导入分数def const(frac):"分数大于等于1或0的CL双流.""而部分:如果frac> == 2:产量1分数=分数(分数，2)别的:产量0压裂-= 1frac =分数(1，frac)如果frac否则为0def rle(bit_seq):"游程编码的CL位流.""s = 0对于bit_seq中的位:s + =位如果不是:产量s = 0def floor(rle_seq):"小于rle_seq的最大整数的RLE CL项.""#经过产量""floor()的示例输入/输出对.""num =分数(1234)对于范围为(1，int(num)+1)的den:输入=列表(rle(const(num/den)))output = list(rle(const(num//den)))#整数除法！print(>"，输入)print(>>"，输出)print(> *"，list(floor(input)))打印()断言(列表(地板(输入))==输出) 

我如何本着持续的精神实施地板操作员仅在必要时通过消耗项进行小数运算立即发出术语，尤其是仅使用游程长度编码格式(二进制)，而不是一元扩展Gosper倾向于描述.

解决方案

通过假设游程长度编码中的下一个系数是无限的，您可以得到一个下限.通过假设下一项为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)的情况，在这种情况下，您可以使ε任意小，但从不等于零.不可能对此表达式进行讨论，因为-通过所采用的数值方法-无法确定实际值最终将低于N还是.

I'm trying to implement basic arithmetic on Bill Gosper's continued logarithms, which are a 'mutation' of continued fractions allowing the term co-routines to emit and consume very small messages even on very large or very small numbers.

Reversible arithmetic, such as {+,-,*,/} are fairly straightforwardly described by Gosper at least in a unary representation, but I'm having difficulty implementing the modulo operator which effectively truncates information from the division operation.

I've realized the modulo operator can be mostly defined with operations I already have:

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

leaving my only problem with floor.

I've also read that the run-length encoded format for continued logarithms effectively describes

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

So yielding the first term right away (pass through) produces the correct output so far, but leaves a significant portion to be determined which I assume requires some sort of carry mechanism.

I've written the following code to test input terms and the expected output terms, but I'm mainly looking for high level algorithm ideas behind implementing floor.

An example input (1234 / 5) to output pair is

Input: [7, 0, 3, 0, 0, 0, 0, 1, 3, 3, 1]

Output: [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.

解决方案

By assuming that the next coefficient in the run-length encoding is infinite, you can get a lower bound. By assuming that the next term is 1, you can get an upper bound.

You can simply process as many run-length encoded coefficients until you know that both the lower and the upper bound are in the half-open interval [N, N + 1). In this case you know that the floor of the continued logarithm is N. This is similar to what Bill Gosper does at the start of the linked document.

Note, however, that this process doesn't necessarily terminate. For example, when you multiply sqrt(2) by sqrt(2), you get, of course, the number 2. However, the continued logarithm for sqrt(2) is infinite. To evaluate the product sqrt(2) * sqrt(2) you will need all the coefficients to know that you will end up with 2. With any finite number of terms, you can't decide if the product is less than 2 or at least equal to it.

Note that this problem is not specific to continued logarithms, but it is a fundamental problem that occurs in any system in which you can have two numbers for which the representation is infinite but the product can be represented with a finite number of coefficients.

To illustrate this, suppose that these coroutines don't spit out run-length encoded values, but decimal digits, and we want to calculate floor(sqrt(2) * sqrt(2)). After how many steps can we be sure that the product will be at least 2? Let's take 11 digits, just to see what happens: 1.41421356237 * 1.41421356237 = 1.9999999999912458800169

As you might guess, we get arbitrarily close to 2, but will never 'reach' 2. Indeed, without knowing that the source of the digits is sqrt(2), it might just happen that the digits terminate after that point and that the product ends up below 2. Similarly, all following digits might be 9's, which would result in a product slightly above 2.

(A simpler example would be to take the floor of a routine that produces 0.9999...)

So in these kind of arbitrary-precision numerical systems you can end up in situations where you can only calculate some interval (N - epsilon, N + epsilon), where you can make epsilon arbitrarily small, but never equal to zero. It is not possible to take the floor of this expression, as -- by the numerical methods employed -- it is not possible to decide if the real value will end up below or above N.

这篇关于续对数算法:游程长度编码项上的下限运算符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！