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

Материал из Википедии — свободной энциклопедии

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

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

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

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

Системы счисления подразделяются на позиционные, непозиционные и смешанные.

[править] Позиционные системы счисления

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

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

Каждая позиционная система счисления определяется некоторым целым числом $b > 1$ (т. н. основание системы счисления) таким, что $b$ единиц в каждом разряде объединяется в одну единицу следующего по старшинству разряда. Система счисления с основанием $b$ также называется b-ричной.

Целое число x в b-ричной показательной системе счисления представляется в виде конечной линейной комбинации степеней числа b:

$x = \sum_{k=0}^{n-1} a_k b^k$ , где

a k

— это целые числа, называемые цифрами, удовлетворяющие неравенству $0 \leq a_k < b$ .

Каждая степень $b k$ в такой записи называется b-ричным разрядом, старшинство разрядов и соответствующих им цифр определяется значением показателя $k$ . Обычно для ненулевого числа $x$ требуют, чтобы старшая цифра $a n - 1$ в b-ричном представлении $x$ была также ненулевой.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число $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}.$

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

1 — единичная система счисления (как позиционная, может и не рассматриваться; счёт на пальцах, зарубки, узелки «на память» и др.),
2 — двоичная (в дискретной математике, информатике, программировании),
3 — троичная система счисления,
4 — четверичная система счисления, применяется в вычислительной технике^[1],
10 — десятичная система счисления,
12 — двенадцатеричная система счисления (счёт дюжинами),
16 — шестнадцатеричная (наиболее часто используется в программировании, а также в шрифтах),
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$ секунд.

[править] Фибоначчиева система счисления

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

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

$x = \sum_{k=0}^n f_k F_k$ , где

F k

— числа Фибоначчи, $f_k\in\{0,1\}$ , при этом в записи $f_nf_{n-1}\dots f_0$ не встречается две единицы подряд.

[править] Факториальная система счисления

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

$x = \sum_{k=1}^n d_k k!$ , где $0\leq d_k \leq k$ .

[править] Система счисления майя

Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

Для записи основными знаками были точки (единицы) и отрезки (пятёрки).

[править] Непозиционные системы счисления

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

[править] Биномиальная система счисления

Представление, использующее биномиальные коэффициенты

$x = \sum_{k=1}^n {c_k\choose k}$ , где $0\leq c_1 < c_2 < \dots < c_n$ .

[править] Греческая система счисления

Основная статья: Греческая система счисления

[править] Римская система счисления

Основная статья: Римские цифры

Каноническим примером фактически непозиционной системы счисления является римская, в которой в качестве цифр используются латинские буквы:
I обозначает 1,
V — 5,
X — 10,
L — 50,
C — 100,
D — 500,
M — 1000

Например, II = 1 + 1 = 2
здесь символ I обозначает 1 независимо от места в числе.

На самом деле, римская система не является полностью непозиционной, так как меньшая цифра, идущая перед большей, вычитается из неё, например:

IV = 4, в то время как:
VI = 6

[править] Система остаточных классов (СОК)

Представление числа в системе остаточных классов основано на понятии вычета и китайской теореме об остатках. СОК определяется набором взаимно простых модулей $(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})$ .

[править] Перевод чисел из СОК в десятичную систему счисления

Формула перевода имеет вид:

A = a₁*B₁+a₂*B₂+…+a_n*B_n-r*P, где a₁, …, a_n — представление числа А в СОК с основаниями p₁, p₂, …, p_n;

P = p₁* p₂* …* p_n;

r = 0,1,2,… (целые числа), причём r выбирают так, чтобы разность между левой и правой частью выражения была меньше P;

B_i = (P/p_i)*k_i, где k_i = 1, 2, …, p_i, причём k_i выбирается таким, чтобы остаток от деления B_i/p_i был равен 1.

Пример.

А = (2,4,6) в системе с основаниями: p₁ = 3, p₂ = 5, p₃ = 7.

P = p₁*p₂*p₃ = 3*5*7 = 105.

B₁ = 105/3*k₁ = 35*2 =70;

B₂ = 105/5*k₂ = 21*1 =21;

B₃ = 105/7*k₃ = 15*1 =15;

A = 2*70+4*21+6*15 — r*105;

A = 314 — r*105 = 104, где r=2.

[править] Система счисления Штерна-Броко

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

[править] См. также

[править] Ссылки

Л. Н. Беляева. «Системы счисления и признаки делимости»
С. Б. Гашков Системы счисления и их применение. — М.: МЦНМО, 2004. — (Библиотека «Математическое просвещение»).
С. В. Фомин Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике).
Яглом И., «Системы счисления», Квант, № 6, 1970.
Системы остаточных классов, модулярные ЭВМ
Позиционные системы счисления
«Скрипт для работы с системами счисления»
Одна из программ работы с системами счисления
Классификация систем счисления
Энергосбережение и системы счисления
А. Стахов «Роль систем счисления в истории компьютеров».
Двоичная (бинарная) система счисления

↑ http://potan.livejournal.com/91399.html Системы счисления (продолжение).

[0] ttp://potan.livejournal.com/91399.html Системы счисления (продолжение).

[1]