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

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

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

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

• ее использование позволяет сократить вычислительную сложность алгоритма умножения чисел;

• в ней существенно уменьшается объем памяти для записи и хранения многих больших чисел.

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

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

Обобщенные операции – это операции с АК-объектами, имеющими разные схемы отношения. Для выполнения этих операций АК-объекты предварительно приводятся к одной схеме отношения с помощью простой операции добавление фиктивного атрибута. В частности, в ПРИМЕРе статьи Подсказки 1 и 2 («Во второй комнате нет тигра, а третья комната не пуста», «Первая комната не пуста, а во второй нет тигра») можно было выразить в сокращенных схемах отношения
и
.

Затем вычислить дополнение Подсказки 2 в сокращенной схеме отношения

и вычислить обобщенное пересечение, предварительно добавив на место отсутствующих фиктивные атрибуты,

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

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

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

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

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

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

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

Рассмотрим у-множество, элементами которого являются числовые n-кортежи. Введем для них отношение порядка (обычно отношение порядка в общем случае для у-множеств обозначается , но мы этот знак будем здесь использовать для отношения «меньше или равно» для обычных чисел). Пусть даны числовые n-кортежи и . Определим для них отношение порядка и операции.

• подтверждается, если и только если для всех . В противном случае n-кортежи не сравнимы.

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

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

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

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

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

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

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

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

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

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

.

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

.

.

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

.

.

Теперь, чтобы вычислить произведение этих чисел, нам достаточно вычислить «сумму» этих числовых кортежей, т.е. выполнить покомпонентное сложение. Получим
.

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

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

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

Например, вычислим результат деления 495 на число 1176. В результате получим

По полученному числовому кортежу восстановим число

• Обобщенная нижняя грань (): если числовые кортежи содержат только неотрицательные целые числа, то тут все понятно – мы вычисляем наибольший общий делитель (НОД) двух исходных чисел. А если в числовых кортежах содержатся отрицательные целые числа, тогда что? Нетрудно доказать, что это наибольшее рациональное число, результатом деления на которое исходных рациональных чисел, получатся целые числа.

• Обобщенная верхняя грань (): для числовых кортежей с неотрицательными целыми числами вычисляется наименьшее общее кратное (НОК) исходных чисел.

• Умножение на константу (имеется в виду умножение всех элементов числового кортежа на одну и ту же константу). Если константа – целое положительное k, то тут все понятно: исходное число возводится в степень k. А если константа дробь? Тоже ничего сверхъестественного: исходное число возводится в дробную степень. Тем самым появляется возможность выразить в FPR-системе счисления иррациональные числа.

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

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

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

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

• Обобщенное отношение частичного порядка (). Если в числовых кортежах содержатся только неотрицательные целые числа, то это отношение соответствует известному отношению делимости () для множества положительных целых чисел. Если числовые кортежи содержат отрицательные целые числа, то исходные числа могут быть и дробями, но при этом если , то можно легко доказать, что результатом деления будет целое число. Это обстоятельство позволяет ввести новое отношение порядка по делимости не только для целых, но и для рациональных чисел (). А вот как интерпретируются случаи, когда в числовых кортежах содержатся несократимые дроби, пока непонятно.

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

  , а - неотрицательное действительное число.

Но если не соблюдается, то сравнение и по величине с помощью числовых кортежей становится проблемой.

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

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

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

2. Проблема суммирования. Используя FPR-систему счисления, можно легко вычислить произведения и рациональные степени соответствующих чисел. Но можно ли построить алгоритмы для вычисления суммы чисел, не переводя их в традиционную систему счисления?

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

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

1. Предложенная система позволяет точно выразить все конечные рациональные (за исключением 0) числа и некоторые классы иррациональных чисел.

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

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

3. Для многих больших чисел FPR-система счисления позволяет значительно сэкономить место в памяти. Для тех, кто сомневается в этом, предлагаю сравнить объемы памяти для хранения записи и соответствующего ей числа , выраженного в традиционной системе счисления.

Заключение

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

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

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

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

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