Как можно представить натуральные числа, чтобы предлагать постоянное добавление времени?

Ответ Cirdec в основном не связанный с вопросом вопрос заставил меня задаться вопросом, как лучше представлять натуральные числа с добавлением по времени, вычитанием на единицу и тестированием на нуль.

Почему арифметика Peano недостаточно хороша:

Предположим, что мы используем

data Nat = Z | S Nat

Тогда мы можем написать

Z + n = n
S m + n = S(m+n)

Мы можем рассчитать m+n в O (1) раз, поместив m-r дебет (для некоторой константы r), по одному на каждый конструктор S, добавленный на n. Чтобы получить O (1) isZero, мы должны иметь не более p дебетов для конструктора S для некоторой константы p. Это отлично работает, если мы вычислим a + (b + (c+...)), но развалимся, если вычислить ((...+b)+c)+d. Проблема заключается в том, что дебетовые счётчики складываются на передней панели.

Один вариант

Легкий выход - просто использовать катаные списки, такие как те, которые Окасаки описывает, напрямую. Есть две проблемы:

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

Ответ 1

Насколько я знаю, Идрис (строго типичный чисто функциональный язык, который очень близок к Haskell) имеет дело с этим довольно просто. Компилятор знает Nat и Fin (верхняя граница Nat s) и по возможности заменяет их целыми типами и операциями машины, поэтому полученный код довольно эффективен. Однако это неверно для пользовательских типов (даже изоморфных), а также для этапа компиляции (для проверки типов были использованы некоторые примеры кода, использующие Nat, которые привели к экспоненциальному росту во время компиляции, я могу предоставить их, если необходимо).

В случае Haskell я думаю, что подобное расширение компилятора может быть реализовано. Другая возможность - сделать макросы TH, которые преобразуют код. Конечно, обе опции не легки.

Ответ 2

Я понимаю, что в базовой терминологии компьютерного программирования основная проблема заключается в том, что вы хотите объединить списки в постоянное время. В списках нет читов, таких как прямые ссылки, поэтому вы не можете, например, перейти к концу в O (1) раз.

Вместо этого вы можете использовать кольца, которые вы можете объединить в O (1) раз, независимо от того, используется ли a+(b+(c+...)) или ((...+c)+b)+a. Узлы в кольцах не обязательно должны быть дважды связаны, просто ссылка на следующий node.

Вычитание - это удаление любых node, O (1), а тестирование для нуля (или одного) тривиально. Однако тестирование для n > 1 равно O (n).

Если вы хотите сократить пространство, то при каждой операции вы можете объединить узлы в точках вставки или удаления, а остальные - выше. Чем больше операций вы выполняете, тем компактнее будет представление! Я думаю, что худший случай все равно будет O (n).

Ответ 3

Мы знаем, что существуют два "экстремальных" решения для эффективного сложения натуральных чисел:

Эффективная память, стандартное двоичное представление натуральных чисел, использующее память O (log n), и требует O (log n) времени для добавления. (См. Также главу "Бинарные представления" в книга Окасаки.)
Эффективность процессора, использующая только время O (1). (См. Главу "Структурная абстракция" в книге.) Однако решение использует память O (n), поскольку мы будем представлять натуральное число n как список из n копий ().

Я не делал фактических вычислений, но я считаю, что для численного добавления O (1) нам не потребуется полная мощность очередей F (1) FIFO, было бы достаточно, чтобы загрузить стандартный список [] (LIFO) таким же образом. Если вам интересно, я мог бы попытаться подробнее остановиться на этом.

Проблема с эффективным решением CPU заключается в том, что нам нужно добавить избыточность в представление памяти, чтобы мы могли сэкономить время процессора. В некоторых случаях добавление такой избыточности может быть выполнено без ущерба для размера памяти (например, для операции увеличения/уменьшения O (1)). И если мы разрешаем произвольные древовидные формы, например, в эффективном решении CPU с загрузочными списками, просто слишком много форм дерева, чтобы отличить их в O (log n) памяти.

Итак, вопрос: можем ли мы найти правильное количество избыточности, чтобы было достаточно сублидерного объема памяти и с которым мы могли бы достичь добавления O (1)? Я считаю, что ответ нет:

Пусть имеет представление + алгоритм, имеющий O (1) дополнение времени. Пусть тогда имеет место величина m-бит, которую мы вычисляем как сумму чисел 2 ^ k, каждая из которых имеет величину (m-k) -бита. Для представления каждого из этих слагаемых нам нужно (независимо от представления) минимум (m-k) бит памяти, поэтому в начале мы начинаем с (по крайней мере) (m-k) 2 ^ k бит памяти. Теперь в каждом из этих 2 ^ k дополнений нам разрешено выполнять постоянное количество операций, поэтому мы можем обрабатывать (и в идеале удалять) общее количество бит C 2 ^ k. Поэтому в конце нижняя граница для числа бит, которые нам нужны для представления результата, равна (m-k-C) 2 ^ k бит. Так как k можно выбрать произвольно, то наш противник может установить k = mC-1, что означает, что общая сумма будет представлена по крайней мере 2 ^ (mC-1) = 2 ^ m/2 ^ (C + 1) ∈ O ( 2 ^ м). Таким образом, натуральное число n всегда будет иметь O (n) бит памяти!