AntiLogik Aug 7 2023 at 13:29

Приложения алгебры кортежей. Часть 1. Гибкая система счисления с простыми основаниями

Medium

8 min

High performance*Algorithms*Mathematics*Data compression*

Opinion

В настоящее время известно большое число систем счисления. Подробный перечень (не знаю, насколько полный) приведен в англоязычной Википедии. В этом списке я не нашел ту систему, которая будет изложена здесь. Она относится к классу систем с переменным основанием (mixed radix). Предлагаю ее назвать Flexible number system with a Prime Radixes, сокращенно FPR-системой счисления.

Но для того, чтобы ее понять, необходимы знания некоторых понятий алгебры кортежей (АК) и частично упорядоченных множеств хотя бы в том объеме, который имеется в соответствующей статье в Википедии. Об АК кратко было рассказано в статье «Как совместить логику и семантику в одной алгебраической системе». Там же есть ссылки на публикации с более подробным описанием АК.

В данной статье будут обоснованы следующие преимущества предложенной системы счисления:

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

Свойство гибкости

Для понимания данного текста важную роль играют такие понятия АК как схема отношения, фиктивная компонента и обобщенные операции. Напомню, что атрибуты – это имена переменных, домены – множества, задающие области значений атрибутов, схема отношения - заключенная в прямые скобки последовательность атрибутов, фиктивные компоненты в АК – это предельные значения доменов атрибутов: $\ast$ - множество всех значений соответствующего атрибута (полная компонента) и $\varnothing$ (пустая компонента).

Обобщенные операции – это операции с АК-объектами, имеющими разные схемы отношения. Для выполнения этих операций АК-объекты предварительно приводятся к одной схеме отношения с помощью простой операции добавление фиктивного атрибута. В частности, в ПРИМЕРе статьи Подсказки 1 и 2 («Во второй комнате нет тигра, а третья комната не пуста», «Первая комната не пуста, а во второй нет тигра») можно было выразить в сокращенных схемах отношения
$\quad \quad M_1[R_2R_3] = [\{L,E\} \quad \{L,T\}]$ и
$\quad \quad M_2[R_1R_2] = [\{L,T\} \quad \{L,E\}]$ .

Затем вычислить дополнение Подсказки 2 в сокращенной схеме отношения
$\overline{M_2}[R_1R_2] = \begin{bmatrix} \{E\} & * \\ * & \{T\} \end{bmatrix}$
и вычислить обобщенное пересечение, предварительно добавив на место отсутствующих фиктивные атрибуты,
$M_1[R_2R_3] \cap_G \overline{M_2}[ R_1R_2] = [\ast \quad \{L,E\} \quad \{L,T\}] \cap \begin {bmatrix} \{E\} & * & *\\ * & \{T\} & * \end{bmatrix} = [\{E\}\quad \{L,E\} \quad \{L,T\}].$

Результат получился тот же самый.

Аналогично определяются и обобщенные отношения: объекты с разными схемами отношения перед проверкой равенства или включения приводятся к одинаковым схемам отношения с помощью добавления фиктивных атрибутов.

Обобщенные операции и отношения как раз и обеспечивают в математической системе свойство гибкости.

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

Решетка числовых кортежей

Для представления чисел в FPR-системе счисления будут использоваться числовые n-кортежи (т.е. кортежи чисел длины n).

Решетка – это частично упорядоченное множество (сокращенно у-множество (poset)), для которого определены две операции: точная нижняя грань (обозначается inf или $\wedge$ ) и точная верхняя грань (обозначается sup или $\vee$ ). В общем случае эти операции выполняются для всех пар элементов решетки, но бывают другие варианты (нам они не понадобятся). В отличие от просто верхней (или нижней) грани точная верхняя (нижняя) грань дает в результате единственный элемент решетки.

Рассмотрим у-множество, элементами которого являются числовые n-кортежи. Введем для них отношение порядка $\sqsubseteq$ (обычно отношение порядка в общем случае для у-множеств обозначается $\leq$ , но мы этот знак будем здесь использовать для отношения «меньше или равно» для обычных чисел). Пусть даны числовые n-кортежи $A=(a_1, a_2, \cdots, a_n)$ и $B=(b_1, b_2, \cdots, b_n)$ . Определим для них отношение порядка и операции.

$A \sqsubseteq B$ подтверждается, если и только если $a_i \leq b_i$ для всех $i = 1, 2,\ldots, n$ . В противном случае n-кортежи не сравнимы.
$A \wedge B = (min(a_1, b_1), min(a_2, b_2), \cdots, min(a_n, b_n)).$
$A \vee B = (max(a_1, b_1), max(a_2, b_2), \cdots, max(a_n, b_n)).$

Если числа, содержащиеся в n-кортежах, ограничить наибольшим и наименьшим значениями величины, то мы получим решетку, что вообще-то несложно доказать.

Помимо «решеточных» операций $\wedge$ и $\vee$ для числовых кортежей можно ввести «экзотические» операции, например, сложение и вычитание:

$A + B = ((a_1 + b_1), (a_2 + b_2), \cdots, (a_n + b_n)).$
$A - B = ((a_1 - b_1), (a_2 - b_2), \cdots, (a_n - b_n)).$

Пока неясно, для чего они нужны, но дальше все станет понятным.

FPR-система счисления

Для числовых n-кортежей введем следующие обозначения и определения.
Рассмотрим возрастающий ряд простых чисел без пропусков и введем для них соответствующие обозначения P_i :

$\begin{matrix} P_1 & P_2 & P_3 & P_4 & P_5 & \cdots & P_{15} & \cdots & P_{84} & \cdots & P_{169} & \cdots \\ 2 & 3 & 5 & 7 & 11 & \cdots & 47 & \cdots & 433 & \cdots & 1009 & \cdots \end{matrix}$

Переменные P_i будем использовать в качестве атрибутов числовых кортежей, строго соблюдая порядок в схемах отношений: атрибут P_m расположен после атрибута P_k лишь при условии k < m .

Сначала рассмотрим вариант, в котором компонентами наших числовых кортежей будут неотрицательные целые числа. Они будут обозначать степени соответствующих простых чисел. Как известно, любое целое число можно разложить на простые множители. Например,
$484 = 2 \cdot 2 \cdot 11 \cdot 11 = 2^2 \cdot 11^2$ . Тогда, если использовать схему отношения, получим следующую запись этого числа с помощью числовых кортежей:
$484 \Rightarrow N_i[P_1P_5](2, 2)$ (после схемы отношения числа записывается числовой кортеж, с помощью которого это число можно выразить в позиционной системе счисления).

В качестве компонент в числовых кортежах допускаются отрицательные числа. Это позволяет отобразить в FPR-системе счисления любое положительное рациональное число. Например,
$\frac {33} {40}\Rightarrow N_k[P_1P_2P_3P_5](-3, 1, -1, 1).$

Известно, что любое число в степени 0 равно 1. Тогда можно считать, что компонента 0 в числовом кортеже играет роль фиктивной компоненты.

Например, число 484 можно выразить не только в схеме отношения [P_1P_5] , но и, допустим, в схеме отношения [P_1P_2P_4P_5] :

$484 = 2^2 \cdot 3^0 \cdot 7^0 \cdot 11^2 \Rightarrow N_m[P_1P_2P_4P_5](2, 0, 0, 2)$ .

Отсюда ясно, что с помощью фиктивных компонент и соответственно фиктивных атрибутов можно выполнять операции с числами, у которых числовые кортежи имеют разные схемы отношения. В качестве примера вычислим произведение чисел 1176 и 495, используя числовые кортежи. Запишем эти числа в FPR-системе счисления:

$1176 \Rightarrow N_1[P_1P_2P_4](3, 1, 2)$ .

$495 \Rightarrow N_2[P_2P_3P_5](2, 1, 1)$ .

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

$1176 \Rightarrow N_1[P_1P_2P_3P_4P_5](3, 1, 0, 2, 0)$ .

$495 \Rightarrow N_2[P_1P_2P_3P_4P_5](0. 2, 1, 0, 1)$ .

Теперь, чтобы вычислить произведение этих чисел, нам достаточно вычислить «сумму» этих числовых кортежей, т.е. выполнить покомпонентное сложение. Получим
$N_3[P_1P_2P_3P_4P_5](3. 3, 1, 2, 1) \Rightarrow 2^3 \cdot 3^3 \cdot 5 \cdot 7^2 \cdot 11 = 582120$ .

Операции в FPR-системе счисления

Обобщенное сложение (): после добавления недостающих фиктивных атрибутов в числовых кортежах вычисляются суммы соответствующих компонент. Эта операция соответствует произведению исходных чисел.
Обобщенное вычитание (): после добавления недостающих фиктивных атрибутов в числовых кортежах вычисляются разности соответствующих компонент. Эта операция соответствует делению исходных чисел.

Например, вычислим результат деления 495 на число 1176. В результате получим
(0. 2, 1, 0, 1) - (3, 1, 0, 2, 0) = (-3, 1, 1, -2, 1)

По полученному числовому кортежу восстановим число
$N_4[P_1P_2P_3P_4P_5](-3, 1, 1, -2, 1) \Rightarrow \frac {3 \cdot 5 \cdot 11} {2^3 \cdot 7^2}= \frac {165} {392}.$

Обобщенная нижняя грань ( $\wedge_G$ ): если числовые кортежи содержат только неотрицательные целые числа, то тут все понятно – мы вычисляем наибольший общий делитель (НОД) двух исходных чисел. А если в числовых кортежах содержатся отрицательные целые числа, тогда что? Нетрудно доказать, что это наибольшее рациональное число, результатом деления на которое исходных рациональных чисел, получатся целые числа.
Обобщенная верхняя грань ( $\vee_G$ ): для числовых кортежей с неотрицательными целыми числами вычисляется наименьшее общее кратное (НОК) исходных чисел.
Умножение на константу (имеется в виду умножение всех элементов числового кортежа на одну и ту же константу). Если константа – целое положительное k, то тут все понятно: исходное число возводится в степень k. А если константа дробь? Тоже ничего сверхъестественного: исходное число возводится в дробную степень. Тем самым появляется возможность выразить в FPR-системе счисления иррациональные числа.
Отрицательные исходные числа. Приведенные операции с числовыми кортежами показывают, что их элементами могут быть отрицательные и рациональные числа. С помощью таких числовых кортежей можно выразить все положительные целые, рациональные и некоторые классы иррациональных чисел (те, у которых сомножители являются результатом вычисления дробных степеней целых чисел). Невыразимо в этой системе точное значение нуля и отрицательные числа. Но с отрицательными числами положение можно легко исправить. Введем еще один атрибут . Тогда четное целое значение соответствующего элемента в числовом кортеже означает, что мы имеем дело с положительными исходными числами, если же соответствующее число в кортеже целое нечетное, то исходное число отрицательное.

А возможны ли для атрибута P_0 другие значения в числовых кортежах? На ум приходит число $\frac 1 2.$ В этом случае нашему взору откроется мнимое число.

Отношения в FPR-системе счисления

Обозначим исходные числа в позиционной системе счисления, которым соответствуют числовые кортежи и , соответственно N(A) и N(B) .

Обобщенное отношение частичного порядка ( $\sqsubseteq_G$ ). Если в числовых кортежах содержатся только неотрицательные целые числа, то это отношение соответствует известному отношению делимости ( $\mid$ ) для множества положительных целых чисел. Если числовые кортежи содержат отрицательные целые числа, то исходные числа могут быть и дробями, но при этом если $A \sqsubseteq_G B$ , то можно легко доказать, что результатом деления $\frac {N(B)} {N(A)}$ будет целое число. Это обстоятельство позволяет ввести новое отношение порядка по делимости не только для целых, но и для рациональных чисел ( $\mid_R$ ). А вот как интерпретируются случаи, когда в числовых кортежах содержатся несократимые дроби, пока непонятно.
Отношение порядка по величине. Ясно, что если $A \sqsubseteq_G B$ , то всегда верно $N(A) \le N(B)$ . Это можно легко доказать, используя свойство неубывания показательной функции , где
, а - неотрицательное действительное число.

Но если $A \sqsubseteq_G B$ не соблюдается, то сравнение N(A) и N(B) по величине с помощью числовых кортежей становится проблемой.

Нерешенные проблемы

Хотя теории FPR-систем счисления пока что нет, но проблемы уже возникли. Но, может быть, это обстоятельство как раз и увеличивает шансы перехода данных заметок в теорию?

Проблема сравнения чисел по величине. Из предыдущего ясно, что из $A \sqsubseteq_G B$ следует $N(A) \le N(B)$ . Но если отношение порядка для числовых кортежей не соблюдается, то как проверить отношение порядка по величине для исходных чисел, не переводя их в позиционную систему счисления с постоянным основанием? Ответа на это вопрос нет, как нет и доказательства того, что такой алгоритм проверки для общего случая невозможен.
Проблема суммирования. Используя FPR-систему счисления, можно легко вычислить произведения и рациональные степени соответствующих чисел. Но можно ли построить алгоритмы для вычисления суммы чисел, не переводя их в традиционную систему счисления?

В процессе развития новой теории, несомненно, появятся и другие проблемы.

Позитивные моменты

Предложенная система позволяет точно выразить все конечные рациональные (за исключением 0) числа и некоторые классы иррациональных чисел.
Нетрудно проверить, что вычислительная сложность алгоритма вычисления произведения чисел в FPR-системе счисления линейно зависит от числа атрибутов (n) в обобщенной схеме отношения этих чисел, что соответствует оценке вычислительной сложности. Эта оценка существенно меньше оценок вычислительной сложности известных алгоритмов для традиционных систем счисления. Здесь возможно следующее возражение: но ведь перевод числа из FPR-системы счисления в традиционную требует немалых вычислительных ресурсов, которые не учитываются при оценке вычислительной сложности этого алгоритма для FPR-системы.

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

Для многих больших чисел FPR-система счисления позволяет значительно сэкономить место в памяти. Для тех, кто сомневается в этом, предлагаю сравнить объемы памяти для хранения записи $N[R_4R_{181}](3, 100)$ и соответствующего ей числа , выраженного в традиционной системе счисления.

Заключение

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

Но если кто-то всерьез займется этой проблемой, то на соавторстве не буду настаивать. И не буду возражать, если найдется более подходящее название для этой системы счисления. Например, можно назвать просто и без затей: К-система (не подумайте плохого: под буквой «К» подразумевается не моя фамилия, а слово «Кортеж»).

Но от ссылки на эту статью не откажусь.

На форуме dxdy (https://dxdy.ru/topic155252.html ) предложили программу на языке PARI/GP, с помощью которой заданное целое число в десятичной системе счисления можно преобразовать в запись этого числа в FPR-системе, причем в формате TeX. Пример работы программы (перевод числа 1234567890 в FPR-запись):

? fpr(1234567890)

$1234567890_{10}=[P_{1}P_{2}P_{3}P_{504}P_{529}](1,2,1,1,1)$

А вот код программы ( с разрешения автора):

[code]fpr(x)=my(f=factor(x),n=#f[,1]);print1("$",x,"_{10}=");for(i=1,n,print1("P_{",primepi(f[i,1]),"}"));print("$")[\code]

Продолжение следует.

Дизайн баннера выполнен Анной Горской

Hubs: