Продолжение логарифмической арифметики: оператор пола на закодированных терминах

Question

Я пытаюсь реализовать базовую арифметику для продолженных логарифмов Билла Госпера, которые представляют собой "мутацию" непрерывных дробей, позволяющую термину co-рутины испускать и потреблять очень маленькие сообщения даже при очень больших или очень малых числах.

Обратимая арифметика, такая как {+,-,*,/}, довольно просто описана Госпером, по крайней мере, в унарном представлении, но у меня возникают сложности с реализацией оператора по модулю, который эффективно усекает информацию из операции деления.

Я понял, что оператор по модулю может быть в основном определен с операциями, которые у меня уже есть:

мод b == a - b * этаж (a / b)

оставив мою единственную проблему с полом.

Я также читал, что закодированный формат длин серий для последовательных логарифмов эффективно описывает

"... целочисленная часть лог-базы 2 числа, оставшегося для описания."

Таким образом, немедленное получение первого слагаемого (проход) позволяет получить правильный результат, но оставляет значительную часть для определения, которая, как я полагаю, требует какого-то рода механизма переноса.

Я написал следующий код для проверки входных терминов и ожидаемых выходных терминов, но в основном я ищу идеи алгоритма высокого уровня, стоящие за реализацией пола.

Пример ввода (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)

Как я могу реализовать оператор пола в духе арифметики непрерывной дроби, потребляя термины только тогда, когда это необходимо, и испуская термины сразу, и особенно только используя закодированный формат длины прогона (в двоичном формате), а не унарное расширение, которое имеет тенденцию описывать Госпер.

Answer 1

Предполагая, что следующий коэффициент в кодировке длин серий бесконечен, вы можете получить нижнюю границу. Предполагая, что следующий член равен 1, вы можете получить верхнюю границу.

Вы можете просто обработать столько коэффициентов с кодировкой длин серий, пока не узнаете, что и нижняя, и верхняя граница находятся в полуоткрытом интервале [N, N + 1). В этом случае вы знаете, что нижний предел непрерывного логарифма равен N. Это похоже на то, что делает Билл Госпер в начале связанного документа.

Обратите внимание, однако, что этот процесс не обязательно завершается. Например, когда вы умножаете sqrt(2) на sqrt(2), вы, конечно же, получаете число 2. Однако логарифм продолжения для sqrt(2) бесконечен. Чтобы оценить продукт sqrt(2) * sqrt(2), вам понадобятся все коэффициенты, чтобы знать, что вы получите 2. С любым конечным числом членов вы не можете решить, будет ли продукт меньше 2 или наименее равный ему.

Обратите внимание, что эта проблема не является специфической для непрерывных логарифмов, но это фундаментальная проблема, которая возникает в любой системе, в которой вы можете иметь два числа, представление которых бесконечно, но произведение может быть представлено с конечным числом коэффициентов.

Чтобы проиллюстрировать это, предположим, что эти сопрограммы выводят не значения, закодированные по длине прогона, а десятичные цифры, и мы хотим вычислить этаж (sqrt(2) * sqrt(2)). Через сколько шагов можно быть уверенным, что товара будет минимум 2? Давайте возьмем 11 цифр, просто чтобы посмотреть, что произойдет: 1.41421356237 * 1.41421356237 = 1.9999999999912458800169

Как вы можете догадаться, мы произвольно приближаемся к 2, но никогда не "достигнем" 2. Действительно, не зная, что источником цифр является sqrt(2), может случиться так, что цифры заканчиваются после этой точки и что product будет ниже 2. Точно так же все следующие цифры могут быть 9, что приведет к значению продукта немного больше 2.

(Более простой пример - взять слово из подпрограммы, которая выдает 0,9999...)

Таким образом, в таких системах счисления произвольной точности вы можете оказаться в ситуациях, когда вы можете вычислить только некоторый интервал (N - эпсилон, N + эпсилон), где вы можете сделать эпсилон сколь угодно малым, но никогда не равным нулю. Невозможно взять слово за это выражение, поскольку - с помощью используемых численных методов - невозможно решить, окажется ли реальное значение ниже или выше N.