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

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

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

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

• даёт представления множества чисел (целых и/или вещественных);

• даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);

• отражает алгебраическую и арифметическую структуру чисел.

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

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

• непозиционные;

• смешанные.

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

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

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

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

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

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

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

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

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

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

• 2 — двоичная (в дискретной математике, информатике, программировании);

• 3 — троичная;

• 8 — восьмеричная;

• 10 — десятичная (используется повсеместно);

• 12 — двенадцатеричная (счёт дюжинами);

• 16 — шестнадцатеричная (используется в программировании, информатике);

• 20 — двадцатеричная;

• 60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{\displaystyle x=\sum _{k=1}^{n}{c_{k} \choose k}} , где {\displaystyle 0\leq c_{1}

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

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

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

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

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

…

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

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

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

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

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