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

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

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

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

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

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

• позиционные;
• непозиционные;
• смешанные.

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

Основная статья: Позиционная система счисления

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

Под позиционной системой счисления обычно понимается $b$-ичная система счисления, которая определяется целым числом $b>1$, называемым «основанием» системы счисления. Целое число без знака $x$ в $b$-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа $b$:

$x=\sum _{k=0}^{n-1}a_{k}b^{k}$, где $a_{k}$ — это целые числа, называемые «цифрами», удовлетворяющие неравенству $0\leq a_{k}\leq (b-1)$.

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

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

$x=a_{n-1}a_{n-2}\dots a_{0}.$

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

$103=1\cdot 10^{2}+0\cdot 10^{1}+3\cdot 10^{0}.$

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

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

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

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

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

$x=\sum _{k=0}^{n-1}a_{k}b_{k}$, где на коэффициенты $a_{k}$, называемые как и прежде «цифрами», накладываются некоторые ограничения.

Записью числа $x$ в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса $k$, начиная с первого ненулевого.

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

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

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

В факториальной системе счисления основаниями являются последовательность факториалов $b_{k}=k!$, и каждое натуральное число $x$ представляется в виде:

$x=\sum _{k=1}^{n}d_{k}k!$, где $0\leq d_{k}\leq k$.

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

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

$100=4!\cdot 4+3!\cdot 0+2!\cdot 2+1!\cdot 0=96+4;$

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

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

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

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число $n$ в ней представляется в виде:

$n=\sum _{k}f_{k}F_{k}$, где $F_{k}$ — числа Фибоначчи, $f_{k}\in \{0,1\}$, при этом в коэффициентах $f_{k}$ есть конечное количество единиц и не встречаются две единицы подряд.

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

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

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

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

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

$x=\sum _{k=1}^{n}{c_{k} \choose k}$, где $0\leq c_{1}<c_{2}<\dots <c_{n}.$

При всяком фиксированном значении $n$ каждое натуральное число представляется уникальным образом.

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

Основная статья: Система остаточных классов

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором попарно взаимно простых модулей $(m_{1},m_{2},\dots ,m_{n})$ с произведением $M=m_{1}\cdot m_{2}\cdot \dots \cdot m_{n}$ так, что каждому целому числу $x$ из отрезка $[0,M-1]$ ставится в соответствие набор вычетов $(x_{1},x_{2},\dots ,x_{n})$, где

$x\equiv x_{1}{\pmod {m_{1}}};$

$x\equiv x_{2}{\pmod {m_{2}}};$

…

$x\equiv x_{n}{\pmod {m_{n}}}.$

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

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

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

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

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

См. также

• История математики
• Системы записи чисел
• Алфавитная запись чисел
• Число
• Счёты
• Логарифмическая система счисления

Ссылки

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