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

Ответ 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) бит памяти!