Представление с подписанными цифрами

Проблемы, возникавшие при вычислениях, побудили ранних авторов — Колсона (1726) и Коши (1840) — использовать представление с подписанными цифрами. Дальнейший шаг — замена отрицательных цифр новыми — был предложен Зеллингом (1887) и Кайори (1928).

В 1928 году Флориан Кайори отметил повторяющуюся тему подписанных цифр, начиная с Колсона (1726) и Коши (1840)^[2]. В своей книге A History of Mathematical Notations Кайори озаглавил соответствующий раздел как «Отрицательные числа»^[3]. Для полноты, Колсон^[4] приводит примеры и описывает сложение (с. 163-4), умножение (с. 165-6) и деление (с. 170-1) с использованием таблицы кратных делителя. Он объясняет удобство аппроксимации усечением при умножении. Колсон также изобрёл инструмент (счётная таблица), который производил вычисления с помощью подписанных цифр.

Эдуард Зеллинг^[5] предлагал инвертировать цифры 1, 2, 3, 4 и 5 для обозначения отрицательного знака. Он также предлагал использовать слова snie, jes, jerd, reff и niff для устного обозначения. Большинство других ранних источников использовали черту над цифрой для обозначения отрицательного знака. Другое немецкое использование подписанных цифр было описано в 1902 году в энциклопедии Клейна.

Пусть ${\displaystyle {\mathcal {D}}}$ — конечное множество цифр мощности ${\displaystyle b>1}$ (если ${\displaystyle b\leq 1}$, то позиционная система счисления тривиальна и представляет только тривиальное кольцо), каждая цифра обозначается как ${\displaystyle d_{i}}$ для ${\displaystyle 0\leq i<b.}$ ${\displaystyle b}$ называется основанием или разрядом. ${\displaystyle {\mathcal {D}}}$ может быть использовано для представления с подписанными цифрами, если ему сопоставлена единственная функция ${\displaystyle f_{\mathcal {D}}:{\mathcal {D}}\rightarrow \mathbb {Z} }$ такая, что ${\displaystyle f_{\mathcal {D}}(d_{i})\equiv i{\bmod {b}}}$ для всех ${\displaystyle 0\leq i<b.}$ Эта функция ${\displaystyle f_{\mathcal {D}}}$ строго и формально определяет, каким образом целые значения присваиваются символам/глифам из ${\displaystyle {\mathcal {D}}}$. Преимущество такого формализма состоит в том, что определение «целых чисел» (независимо от способа их задания) не смешивается с конкретной системой их записи; таким образом, эти два различных (хотя и тесно связанных) понятия остаются разделёнными.

${\displaystyle {\mathcal {D}}}$ может быть разбито на три непересекающихся подмножества ${\displaystyle {\mathcal {D}}_{+}}$, ${\displaystyle {\mathcal {D}}_{0}}$ и ${\displaystyle {\mathcal {D}}_{-}}$, соответствующих положительным, нулевым и отрицательным цифрам соответственно, так что для всех ${\displaystyle d_{+}\in {\mathcal {D}}_{+}}$ выполняется ${\displaystyle f_{\mathcal {D}}(d_{+})>0}$, для всех ${\displaystyle d_{0}\in {\mathcal {D}}_{0}}$ — ${\displaystyle f_{\mathcal {D}}(d_{0})=0}$, а для всех ${\displaystyle d_{-}\in {\mathcal {D}}_{-}}$ — ${\displaystyle f_{\mathcal {D}}(d_{-})<0}$. Мощность ${\displaystyle {\mathcal {D}}_{+}}$ обозначается ${\displaystyle b_{+}}$, ${\displaystyle {\mathcal {D}}_{0}}$ — ${\displaystyle b_{0}}$, ${\displaystyle {\mathcal {D}}_{-}}$ — ${\displaystyle b_{-}}$, так что ${\displaystyle b=b_{+}+b_{0}+b_{-}}$.

Сбалансированными называются такие представления, в которых для каждой положительной цифры ${\displaystyle d_{+}}$ существует соответствующая отрицательная цифра ${\displaystyle d_{-}}$ такая, что ${\displaystyle f_{\mathcal {D}}(d_{+})=-f_{\mathcal {D}}(d_{-})}$. Следовательно, ${\displaystyle b_{+}=b_{-}}$. Только нечётные основания могут иметь сбалансированные представления, поскольку иначе ${\displaystyle d_{b/2}}$ должна быть противоположна самой себе и, следовательно, равна 0, но ${\displaystyle 0\neq {\frac {b}{2}}}$. В сбалансированной форме отрицательные цифры ${\displaystyle d_{-}\in {\mathcal {D}}_{-}}$ обычно обозначаются как положительные с чертой сверху: ${\displaystyle d_{-}={\bar {d}}_{+}}$ для ${\displaystyle d_{+}\in {\mathcal {D}}_{+}}$. Например, множество цифр сбалансированной троичной системы: ${\displaystyle {\mathcal {D}}_{3}=\lbrace {\bar {1}},0,1\rbrace }$ с ${\displaystyle f_{{\mathcal {D}}_{3}}({\bar {1}})=-1}$, ${\displaystyle f_{{\mathcal {D}}_{3}}(0)=0}$ и ${\displaystyle f_{{\mathcal {D}}_{3}}(1)=1}$. Такая конвенция используется в конечных полях нечётного простого порядка ${\displaystyle q}$:^[6]

${\displaystyle \mathbb {F} _{q}=\lbrace 0,1,{\bar {1}}=-1,...d={\frac {q-1}{2}},\ {\bar {d}}={\frac {1-q}{2}}\ |\ q=0\rbrace .}$

Для любого множества цифр ${\displaystyle {\mathcal {D}}}$ существует дуальное множество ${\displaystyle {\mathcal {D}}^{\operatorname {op} }}$, получаемое обратным порядком цифр, с изоморфизмом ${\displaystyle g:{\mathcal {D}}\rightarrow {\mathcal {D}}^{\operatorname {op} }}$, определяемым как ${\displaystyle -f_{\mathcal {D}}=g\circ f_{{\mathcal {D}}^{\operatorname {op} }}}$. Таким образом, для любого представления с подписанными цифрами ${\displaystyle {\mathcal {N}}}$ кольца ${\displaystyle N}$, построенного из ${\displaystyle {\mathcal {D}}}$ с оценкой ${\displaystyle v_{\mathcal {D}}:{\mathcal {N}}\rightarrow N}$, существует дуальное представление ${\displaystyle {\mathcal {N}}^{\operatorname {op} }}$, построенное из ${\displaystyle {\mathcal {D}}^{\operatorname {op} }}$ с оценкой ${\displaystyle v_{{\mathcal {D}}^{\operatorname {op} }}:{\mathcal {N}}^{\operatorname {op} }\rightarrow N}$ и изоморфизмом ${\displaystyle h:{\mathcal {N}}\rightarrow {\mathcal {N}}^{\operatorname {op} }}$, определяемым как ${\displaystyle -v_{\mathcal {D}}=h\circ v_{{\mathcal {D}}^{\operatorname {op} }}}$, где ${\displaystyle -}$ — оператор противоположного элемента в ${\displaystyle N}$. Множество цифр для сбалансированных представлений является самодуальным.

Пусть заданы множество цифр ${\displaystyle {\mathcal {D}}}$ и функция ${\displaystyle f:{\mathcal {D}}\rightarrow \mathbb {Z} }$ как выше. Определим эндофункцию на целых числах ${\displaystyle T:\mathbb {Z} \rightarrow \mathbb {Z} }$ следующим образом:

${\displaystyle T(n)={\begin{cases}{\frac {n-f(d_{i})}{b}}&{\text{ если }}n\equiv i{\bmod {b}},0\leq i<b\end{cases}}}$

Если единственной периодической точкой ${\displaystyle T}$ является неподвижная точка ${\displaystyle 0}$, то множество всех представлений целых чисел ${\displaystyle \mathbb {Z} }$ с помощью ${\displaystyle {\mathcal {D}}}$ задаётся плюс Клини ${\displaystyle {\mathcal {D}}^{+}}$, то есть множеством всех конечных конкатенированных строк цифр ${\displaystyle d_{n}\ldots d_{0}}$ длины не менее одной, где ${\displaystyle n\in \mathbb {N} }$. Каждое представление ${\displaystyle m\in {\mathcal {D}}^{+}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {D}}^{+}\rightarrow \mathbb {Z} }$

${\displaystyle v_{\mathcal {D}}(m)=\sum _{i=0}^{n}f_{\mathcal {D}}(d_{i})b^{i}}$.

Примером служит сбалансированная троичная система с цифрами ${\displaystyle {\mathcal {D}}=\lbrace {\bar {1}},0,1\rbrace }$.

В противном случае, если существует ненулевая периодическая точка ${\displaystyle T}$, то существуют целые числа, представляемые бесконечным числом ненулевых цифр из ${\displaystyle {\mathcal {D}}}$. Примером служит стандартная десятичная система счисления с множеством цифр ${\displaystyle \operatorname {dec} =\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace }$, где для представления противоположного элемента ${\displaystyle -1}$ требуется бесконечное число цифр ${\displaystyle 9}$, так как ${\displaystyle T_{\operatorname {dec} }(-1)={\frac {-1-9}{10}}=-1}$, а также позиционная система с множеством цифр ${\displaystyle {\mathcal {D}}=\lbrace {\text{A}},0,1\rbrace }$ и ${\displaystyle f({\text{A}})=-4}$, где для представления числа ${\displaystyle 2}$ требуется бесконечное число цифр ${\displaystyle {\text{A}}}$, поскольку ${\displaystyle T_{\mathcal {D}}(2)={\frac {2-(-4)}{3}}=2}$.

Если целые числа могут быть представлены с помощью плюс Клини ${\displaystyle {\mathcal {D}}^{+}}$, то множество всех представлений с подписанными цифрами для десятичных дробей, или ${\displaystyle b}$-адических рациональных чисел ${\displaystyle \mathbb {Z} [1\backslash b]}$, задаётся как ${\displaystyle {\mathcal {Q}}={\mathcal {D}}^{+}\times {\mathcal {P}}\times {\mathcal {D}}^{*}}$, декартово произведение плюс Клини ${\displaystyle {\mathcal {D}}^{+}}$ (все конечные строки цифр ${\displaystyle d_{n}\ldots d_{0}}$ длины не менее одной), синглетона ${\displaystyle {\mathcal {P}}}$ (содержащего разделитель дробной части — ${\displaystyle .}$ или ${\displaystyle ,}$), и звезда Клини ${\displaystyle {\mathcal {D}}^{*}}$ (все конечные строки цифр ${\displaystyle d_{-1}\ldots d_{-m}}$, где ${\displaystyle m,n\in \mathbb {N} }$). Каждое представление ${\displaystyle q\in {\mathcal {Q}}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {Q}}\rightarrow \mathbb {Z} [1\backslash b]}$

${\displaystyle v_{\mathcal {D}}(q)=\sum _{i=-m}^{n}f_{\mathcal {D}}(d_{i})b^{i}}$

Если целые числа могут быть представлены с помощью плюс Клини ${\displaystyle {\mathcal {D}}^{+}}$, то множество всех представлений с подписанными цифрами для вещественных чисел ${\displaystyle \mathbb {R} }$ задаётся как ${\displaystyle {\mathcal {R}}={\mathcal {D}}^{+}\times {\mathcal {P}}\times {\mathcal {D}}^{\mathbb {N} }}$, декартово произведение плюс Клини ${\displaystyle {\mathcal {D}}^{+}}$ (все конечные строки цифр ${\displaystyle d_{n}\ldots d_{0}}$ длины не менее одной), синглетона ${\displaystyle {\mathcal {P}}}$ (разделитель дробной части), и пространство Кантора ${\displaystyle {\mathcal {D}}^{\mathbb {N} }}$ (множество всех бесконечных строк цифр ${\displaystyle d_{-1}d_{-2}\ldots }$, где ${\displaystyle n\in \mathbb {N} }$). Каждое представление ${\displaystyle r\in {\mathcal {R}}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {R}}\rightarrow \mathbb {R} }$

${\displaystyle v_{\mathcal {D}}(r)=\sum _{i=-\infty }^{n}f_{\mathcal {D}}(d_{i})b^{i}}$.

Бесконечный ряд всегда сходится к конечному вещественному числу.

Любые числа в системе с основанием ${\displaystyle b}$ могут быть представлены как подмножество ${\displaystyle {\mathcal {D}}^{\mathbb {Z} }}$, множества всех двусторонних бесконечных последовательностей цифр из ${\displaystyle {\mathcal {D}}}$, где ${\displaystyle \mathbb {Z} }$ — множество целых чисел, а кольцо чисел в системе с основанием ${\displaystyle b}$ представляется кольцо формальных рядов ${\displaystyle \mathbb {Z} [[b,b^{-1}]]}$, то есть двусторонним бесконечным рядом

${\displaystyle \sum _{i=-\infty }^{\infty }a_{i}b^{i}}$

где ${\displaystyle a_{i}\in \mathbb {Z} }$ для ${\displaystyle i\in \mathbb {Z} }$.

Множество всех представлений с подписанными цифрами для целых по модулю ${\displaystyle b^{n}}$, ${\displaystyle \mathbb {Z} \backslash b^{n}\mathbb {Z} }$, задаётся как ${\displaystyle {\mathcal {D}}^{n}}$, множество всех конечных строк цифр ${\displaystyle d_{n-1}\ldots d_{0}}$ длины ${\displaystyle n}$, где ${\displaystyle n\in \mathbb {N} }$. Каждое представление ${\displaystyle m\in {\mathcal {D}}^{n}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {D}}^{n}\rightarrow \mathbb {Z} /b^{n}\mathbb {Z} }$

${\displaystyle v_{\mathcal {D}}(m)\equiv \sum _{i=0}^{n-1}f_{\mathcal {D}}(d_{i})b^{i}{\bmod {b}}^{n}}$

Группа Прюфера — это факторгруппа ${\displaystyle \mathbb {Z} (b^{\infty })=\mathbb {Z} [1\backslash b]/\mathbb {Z} }$ целых и ${\displaystyle b}$-адических рациональных чисел. Множество всех представлений с подписанными цифрами для группы Прюфера задаётся звездой Клини ${\displaystyle {\mathcal {D}}^{*}}$, то есть всеми конечными строками цифр ${\displaystyle d_{1}\ldots d_{n}}$, где ${\displaystyle n\in \mathbb {N} }$. Каждое представление ${\displaystyle p\in {\mathcal {D}}^{*}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {D}}^{*}\rightarrow \mathbb {Z} (b^{\infty })}$

${\displaystyle v_{\mathcal {D}}(m)\equiv \sum _{i=1}^{n}f_{\mathcal {D}}(d_{i})b^{-i}{\bmod {1}}}$

Круговая группа — это факторгруппа ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$ вещественных по целым. Множество всех представлений с подписанными цифрами для круговой группы задаётся пространством Кантора ${\displaystyle {\mathcal {D}}^{\mathbb {N} }}$, то есть всеми правосторонними бесконечными строками цифр ${\displaystyle d_{1}d_{2}\ldots }$. Каждое представление ${\displaystyle m\in {\mathcal {D}}^{n}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {D}}^{\mathbb {N} }\rightarrow \mathbb {T} }$

${\displaystyle v_{\mathcal {D}}(m)\equiv \sum _{i=1}^{\infty }f_{\mathcal {D}}(d_{i})b^{-i}{\bmod {1}}}$

Бесконечный ряд всегда сходится.

Множество всех представлений с подписанными цифрами для ${\displaystyle b}$-адических целых, ${\displaystyle \mathbb {Z} _{b}}$, задаётся пространством Кантора ${\displaystyle {\mathcal {D}}^{\mathbb {N} }}$, то есть всеми левосторонними бесконечными строками цифр ${\displaystyle \ldots d_{1}d_{0}}$. Каждое представление ${\displaystyle m\in {\mathcal {D}}^{n}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {D}}^{\mathbb {N} }\rightarrow \mathbb {Z} _{b}}$

${\displaystyle v_{\mathcal {D}}(m)=\sum _{i=0}^{\infty }f_{\mathcal {D}}(d_{i})b^{i}}$

Множество всех представлений с подписанными цифрами для ${\displaystyle b}$-адических соленоидов, ${\displaystyle \mathbb {T} _{b}}$, задаётся пространством Кантора ${\displaystyle {\mathcal {D}}^{\mathbb {Z} }}$, то есть всеми двусторонними бесконечными строками цифр ${\displaystyle \ldots d_{1}d_{0}d_{-1}\ldots }$. Каждое представление ${\displaystyle m\in {\mathcal {D}}^{n}}$ имеет оценку ${\displaystyle v_{\mathcal {D}}:{\mathcal {D}}^{\mathbb {Z} }\rightarrow \mathbb {T} _{b}}$

${\displaystyle v_{\mathcal {D}}(m)=\sum _{i=-\infty }^{\infty }f_{\mathcal {D}}(d_{i})b^{i}}$

В устной и письменной форме чисел в индоарийских языках используется отрицательная цифра (например, «un» в хинди и бенгали, «un» или «unna» в панджаби, «ekon» в маратхи) для чисел между 11 и 90, оканчивающихся на девять. Примеры для панджаби (префикс «ik» означает «один»):^[7]

• 19 unni, 20 vih, 21 ikki
• 29 unatti, 30 tih, 31 ikatti
• 39 untali, 40 chali, 41 iktali
• 49 unanja, 50 panjah, 51 ikvanja
• 59 unahat, 60 sath, 61 ikahat
• 69 unattar, 70 sattar, 71 ikhattar
• 79 unasi, 80 assi, 81 ikiasi
• 89 unanve, 90 nabbe, 91 ikinnaven.

Аналогично, в языке сесото используются отрицательные числительные для образования чисел 8 и 9:

• 8 robeli (/Ро-бэй-ди/) — «сломать два», то есть два пальца вниз
• 9 robong (/Ро-бонг/) — «сломать один», то есть один палец вниз

В классической латыни^[8] числа 18 и 19 на практике не имели ни устной, ни письменной формы, соответствующей «восемь» или «девять» — несмотря на их существование. Вместо этого в классической латыни:

• 18 = duodēvīgintī («два до двадцати»), (IIXX или XIIX),
• 19 = ūndēvīgintī («один до двадцати»), (IXX или XIX)
• 20 = vīgintī («двадцать»), (XX).

Для последующих чисел [28, 29, 38, 39, …, 88, 89] аддитивная форма была более распространена, однако для указанных чисел вышеуказанная форма оставалась предпочтительной. Таким образом, при приближении к тридцати числительные выражались как:^[9]

• 28 = duodētrīgintā («два до тридцати»), реже также vīgintī octō / octō et vīgintī («двадцать восемь / восемь и двадцать»), (IIXXX или XXIIX против XXVIII, последнее полностью вытеснено.)
• 29 = ūndētrīgintā («один до тридцати»), хотя менее предпочтительная форма также была возможна.

Это одна из основных причин, по которым современные историки объясняют широкое распространение субтрактивных I- и II- в этом диапазоне числительных по сравнению с другими. Числа 98 и 99 также могли выражаться в обеих формах, однако «два до ста» звучало бы необычно — что подтверждается редкостью таких написаний в подлинных источниках.

Ещё один язык, в котором встречается эта особенность (сейчас — лишь в остатках, но всё ещё в активном употреблении), — это финский язык, где (прописью) числительные образуются подобным образом, если встречается цифра 8 или 9. Схема такова:^[10]

• 1 = «yksi» (Примечание: yhd- или yht- чаще при склонении; напр. «yhdessä» = «вместе, как одно [целое]»)
• 2 = «kaksi» (Также kahde-, kahte- при склонении)
• 3 = «kolme»
• 4 = «neljä»

…

• 7 = «seitsemän»
• 8 = «kah(d)eksan» (осталось два [до десяти])
• 9 = «yh(d)eksän» (остался один [до десяти])
• 10 = «kymmenen» (десять)

Этот список не исключение — аналогичная схема встречается и в больших числительных, например:

• 399 = «kolmesataayhdeksänkymmentäyhdeksän»

Такие особенности сохраняются даже в кратчайших разговорных формах числительных:

• 1 = «yy»
• 2 = «kaa»
• 3 = «koo»

…

• 7 = «seiska»
• 8 = «kasi»
• 9 = «ysi»
• 10 = «kymppi»

Это явление не влияет на запись чисел: финны используют стандартную западно-арабскую десятичную запись.

В английском языке распространено выражение времени, например, «seven to three» (2:53, за семь минут до 3:00), где 'to' выполняет функцию вычитания.

Существуют и другие системы с подписанными цифрами, для которых основание ${\displaystyle b\neq b_{+}+b_{-}+1}$. Примером является код Буса, где множество цифр ${\displaystyle {\mathcal {D}}=\lbrace {\bar {1}},0,1\rbrace }$ с ${\displaystyle b_{+}=1}$ и ${\displaystyle b_{-}=1}$, но основание ${\displaystyle b=2<3=b_{+}+b_{-}+1}$. Стандартная двоичная система счисления использует только цифры ${\displaystyle \lbrace 0,1\rbrace }$.

Следует отметить, что нестандартные представления с подписанными цифрами не являются однозначными. Например:

${\displaystyle 0111_{\mathcal {D}}=4+2+1=7}$

${\displaystyle 10{\bar {1}}1_{\mathcal {D}}=8-2+1=7}$

${\displaystyle 1{\bar {1}}11_{\mathcal {D}}=8-4+2+1=7}$

${\displaystyle 100{\bar {1}}_{\mathcal {D}}=8-1=7}$

Неприлегающая форма (NAF) для кодирования Буса гарантирует однозначное представление для каждого целого значения. Однако это справедливо только для целых чисел. Например, рассмотрим следующие периодические двоичные числа в NAF:

${\displaystyle {\frac {2}{3}}=0.{\overline {10}}_{\mathcal {D}}=1.{\overline {0{\bar {1}}}}_{\mathcal {D}}}$