Система счисления

Системы счисления в культуре
Индо-арабская
Арабская; Тамильская; Бирманская	Кхмерская; Лаосская; Монгольская; Тайская
Восточноазиатские
Китайская; Японская; Сучжоу; Корейская	Вьетнамская; Счётные палочки
Алфавитные
Абджадия; Армянская; Ариабхата; Кириллическая; Греческая	Грузинская; Эфиопская; Еврейская; Акшара-санкхья
Другие
Вавилонская; Египетская; Этрусская; Римская; Дунайская	Аттическая; Кипу; Майяская; Эгейская; Символы КППУ
Позиционные
	2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 60
	Нега-позиционная
	Симметричная
Смешанные системы
	Фибоначчиева
Непозиционные
	Единичная (унарная)

Систе́ма счисле́ния (англ. numeral system или system of numeration) — символический метод записи чисел, представление чисел с помощью письменных знаков.

Система счисления:

даёт представления множества чисел (целых и/или вещественных);
даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);
отражает алгебраическую и арифметическую структуру чисел.

Системы счисления подразделяются на:

позиционные (англ. positional system, place-value notation);
непозиционные;
смешанные.

Позиционные системы счисления

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у арабов.

Под позиционной системой счисления обычно понимается [math]\displaystyle{ b }[/math]-ичная система счисления, которая определяется целым числом [math]\displaystyle{ b\gt 1 }[/math], называемым основанием системы счисления. Целое число без знака [math]\displaystyle{ x }[/math] в [math]\displaystyle{ b }[/math]-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа [math]\displaystyle{ b }[/math]:

[math]\displaystyle{ x = \sum_{k=0}^{n-1} a_k b^k }[/math], где [math]\displaystyle{ a_k }[/math] — это целые числа, называемые цифрами, удовлетворяющие неравенству [math]\displaystyle{ 0 \leq a_k \leq (b-1) }[/math].

Каждая степень [math]\displaystyle{ b^k }[/math] в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя [math]\displaystyle{ k }[/math] (номером разряда). Обычно в записи ненулевых чисел начальные нули опускаются.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число [math]\displaystyle{ x }[/math] записывают в виде последовательности его [math]\displaystyle{ b }[/math]-ичных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

[math]\displaystyle{ x = a_{n-1} a_{n-2}\dots a_0. }[/math]

Например, число сто три представляется в десятичной системе счисления в виде:

[math]\displaystyle{ 103 = 1 \cdot 10^{2} + 0 \cdot 10^{1} + 3 \cdot 10^{0}. }[/math]

Наиболее часто употребляемыми в настоящее время позиционными системами являются:

2 — двоичная (в дискретной математике, информатике, программировании);
3 — троичная;
8 — восьмеричная;
10 — десятичная (используется повсеместно);
12 — двенадцатеричная (счёт дюжинами);
16 — шестнадцатеричная (используется в программировании, информатике);
20 — двадцатеричная;
60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

В позиционных системах чем больше основание системы счисления, тем меньшее количество разрядов (то есть записываемых цифр) требуется при записи числа.

Смешанные системы счисления

Смешанная система счисления является обобщением [math]\displaystyle{ b }[/math]-ичной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел [math]\displaystyle{ \{b_k\}_{k=0}^{\infty} }[/math], и каждое число [math]\displaystyle{ x }[/math] в ней представляется как линейная комбинация:

[math]\displaystyle{ x = \sum_{k=0}^{n-1} a_{k}b_k }[/math], где на коэффициенты [math]\displaystyle{ a_{k} }[/math], называемые как и прежде цифрами, накладываются некоторые ограничения.

Записью числа [math]\displaystyle{ x }[/math] в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса [math]\displaystyle{ k }[/math], начиная с первого ненулевого.

В зависимости от вида [math]\displaystyle{ b_k }[/math] как функции от [math]\displaystyle{ k }[/math] смешанные системы счисления могут быть степенными, показательными и т. п. Когда [math]\displaystyle{ b_k=b^k }[/math] для некоторого [math]\displaystyle{ b }[/math], смешанная система счисления совпадает с показательной [math]\displaystyle{ b }[/math]-ичной системой счисления.

Наиболее известным примером смешанной системы счисления является представление времени в виде количества суток, часов, минут и секунд. При этом величина «[math]\displaystyle{ d }[/math] дней, [math]\displaystyle{ h }[/math] часов, [math]\displaystyle{ m }[/math] минут, [math]\displaystyle{ s }[/math] секунд» соответствует значению [math]\displaystyle{ d\cdot 24\cdot 60\cdot 60 + h\cdot 60\cdot 60 + m\cdot 60 + s }[/math] секунд.

Факториальная система счисления

В факториальной системе счисления основаниями являются последовательность факториалов [math]\displaystyle{ b_k=k! }[/math], и каждое натуральное число [math]\displaystyle{ x }[/math] представляется в виде:

[math]\displaystyle{ x = \sum_{k=1}^n d_k k! }[/math], где [math]\displaystyle{ 0\leq d_k \leq k }[/math].

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: номер перестановки (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе [math]\displaystyle{ i! }[/math] будет обозначать число инверсий для элемента [math]\displaystyle{ i+1 }[/math] в том множестве, в котором производятся перестановки (число элементов меньших [math]\displaystyle{ i+1 }[/math], но стоящих правее его в искомой перестановке).

Пример: рассмотрим множество перестановок из 5 элементов, всего их 5! = 120 (от перестановки с номером 0 — (1,2,3,4,5) до перестановки с номером 119 — (5,4,3,2,1)), найдём перестановку с номером 100:

[math]\displaystyle{ 100 = 4!\cdot 4 + 3!\cdot 0 + 2!\cdot 2 + 1!\cdot 0 = 96 + 4; }[/math]

положим [math]\displaystyle{ t_i }[/math] — коэффициент при числе [math]\displaystyle{ i! }[/math], тогда [math]\displaystyle{ t_4 = 4 }[/math], [math]\displaystyle{ t_3 = 0 }[/math], [math]\displaystyle{ t_2 = 2 }[/math], [math]\displaystyle{ t_1 = 0 }[/math], тогда: число элементов меньших 5, но стоящих правее равно 4; число элементов меньших 4, но стоящих правее равно 0; число элементов меньших 3, но стоящих правее равно 2; число элементов меньших 2, но стоящих правее равно 0 (последний элемент в перестановке «ставится» на единственное оставшееся место) — таким образом, перестановка с номером 100 будет иметь вид: (5,3,1,2,4) Проверка данного метода может быть осуществлена путём непосредственного подсчёта инверсий для каждого элемента перестановки.

Фибоначчиева система счисления

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число [math]\displaystyle{ n }[/math] в ней представляется в виде:

[math]\displaystyle{ n = \sum_{k} f_k F_k }[/math], где [math]\displaystyle{ F_k }[/math] — числа Фибоначчи, [math]\displaystyle{ f_k\in\{0,1\} }[/math], при этом в коэффициентах [math]\displaystyle{ f_k }[/math] есть конечное количество единиц и не встречаются две единицы подряд.

Непозиционные системы счисления

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

К наиболее распространённым сегодня непозиционным системам счисления относятся римские цифры.

Биномиальная система счисления

В биномиальной системе счисления^[en] число x представляется в виде суммы биномиальных коэффициентов:

[math]\displaystyle{ x = \sum_{k=1}^n {c_k\choose k} }[/math], где [math]\displaystyle{ 0\leq c_1 \lt c_2 \lt \dots \lt c_n. }[/math]

При всяком фиксированном значении [math]\displaystyle{ n }[/math] каждое натуральное число представляется уникальным образом.^[1]

Система остаточных классов (СОК)

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей [math]\displaystyle{ (m_1, m_2, \dots, m_n) }[/math] с произведением [math]\displaystyle{ M=m_1\cdot m_2\cdot \dots\cdot m_n }[/math] так, что каждому целому числу [math]\displaystyle{ x }[/math] из отрезка [math]\displaystyle{ [0,M-1] }[/math] ставится в соответствие набор вычетов [math]\displaystyle{ (x_1, x_2, \dots, x_n) }[/math], где

[math]\displaystyle{ x \equiv x_1 \pmod{m_1}; }[/math]

[math]\displaystyle{ x \equiv x_2 \pmod{m_2}; }[/math]

…

[math]\displaystyle{ x \equiv x_n \pmod{m_n}. }[/math]

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [math]\displaystyle{ [0,M-1] }[/math].

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [math]\displaystyle{ [0,M-1] }[/math].

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям [math]\displaystyle{ (m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1}) }[/math].

Система счисления Штерна-Броко

Система счисления Штерна-Броко — способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.

См. также

Примечания

↑ Ландо С. К. Глава 1. Задача 1.13 // Лекции о производящих функциях. — 3-е изд., испр.. — М.: МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4. (недоступная ссылка)

Ссылки

Гашков С. Б. Системы счисления и их применение. — М.: МЦНМО, 2004. — (Библиотека «Математическое просвещение»). Архивная копия от 12 января 2014 на Wayback Machine
Фомин С. В. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике).
Яглом И. Системы счисления // Квант. — 1970. — № 6. — С. 2—10.
Цифры и системы счисления. Онлайн Энциклопедия Кругосвет.
Стахов А. Роль систем счисления в истории компьютеров. Архивировано 1 мая 2009 года.
Микушин А. В. Системы счисления. Курс лекций «Цифровые устройства и микропроцессоры»
Butler J. T., Sasao T. Redundant Multiple-Valued Number Systems В статье рассмотрены системы счисления, использующие цифры больше единицы и допускающие избыточность в представлении чисел

[1] Ландо С. К. Глава 1. Задача 1.13 // Лекции о производящих функциях. — 3-е изд., испр.. — М.: МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4. (недоступная ссылка)

[1]