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

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

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

История

править

Исторически первое изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам. Они использовали 60-ричную позиционную систему счисления.

Независимо от евразийских цивилизаций двадцатеричную позиционную систему счисления изобрели индейцы майя.

Древнейшая известная запись позиционной десятичной системы обнаружена в Индии в 595 году. Индийская нумерация пришла сначала в арабские страны, затем и в Западную Европу. О ней рассказал среднеазиатский математик аль-Хорезми. Простые и удобные правила сложения и вычитания чисел, записанных в позиционной системе, сделали её особенно популярной. А поскольку труд аль-Хорезми был написан на арабском, то за индийской нумерацией в Европе закрепилось иное название — «арабская» (арабские цифры).

Определения

править

Позиционная система счисления определяется целым числом  , называемым основанием системы счисления. Система счисления с основанием   также называется  -ичной (в частности, двоичной, троичной, десятичной и т.п.).

Целое число без знака   в  -ичной системе счисления представляется в виде конечной линейной комбинации степеней числа  [1]:

 , где   — это целые числа, называемые цифрами, удовлетворяющие неравенству  

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

С помощью   позиций в  -ичной системе счисления можно записать целые числа в диапазоне от   до  , т.е. всего   различных чисел.

Запись чисел

править

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

 

В ненулевых числах   начальные нули обычно опускаются.

Для записи чисел в системах счисления с основанием до 36 включительно в качестве цифр (знаков) используются арабские цифры (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) и, затем, буквы латинского алфавита (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z). При этом, a = 10, b = 11 и т. д., иногда x = 10.

При одновременной работе с несколькими системами счисления для их различения основание системы обычно указывается в виде нижнего индекса, который записывается в десятичной системе:

  — это число 123 в десятичной системе счисления;
  — то же число в восьмеричной системе счисления;
  — то же число, но в двоичной системе счисления;
  — то же число, но в десятичной системе счисления с двоичным кодированием десятичных цифр (BCD);
  — то же число, но в несимметричной троичной системе счисления;
  — то же число, но в симметричной троичной системе счисления, знаки «i», «7», «2» и «−» обозначают «−1», знаки «1» и «+» обозначают «+1».

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

  • в ассемблере и записях общего рода, не привязанных к конкретному языку, буквой h (от hexadecimal) в конце числа (синтаксис Intel);
  • в Паскале знаком «$» в начале числа;
  • в Си и многих других языках комбинацией 0x или 0X (от hexadecimal) в начале.

В некоторых диалектах языка Си по аналогии с «0x» используется префикс «0b» для обозначения двоичных чисел (обозначение «0b» не входит в стандарт ANSI C).

В русских счётах для записи чисел в десятичной показательной позиционной системе счисления применяется унарнодесятичная система записи (представления) десятичных цифр с одной избыточной унарнодесятичной цифрой «1111111111» = 10_10 на каждый разряд.

Примеры

править

Свойства

править

Позиционная система счисления обладает рядом свойств:

  • Основание системы счисления в ней самой всегда записывается как 10; например, в двоичной системе счисления 10 означает число 2. Данное утверждение неприменимо к унарной системе счисления, в которой используется только одна цифра.
  • Для записи числа x в b-ичной системе счисления требуется   цифр, где   означает взятие целой части числа.
  • Сравнивать числа, записанные в позиционной системе счисления, можно поразрядно, предварительно дополнив их ведущими нулями до одинаковой длины. При этом сравнение идёт от старшего разряда к младшему до тех пор, пока цифра в одном числе не будет больше соответствующей цифры в другом. Например, для сравнения чисел 321 и 312 в десятичной системе счисления сравниваются цифры в одинаковых разрядах слева направо:
    • 3 = 3 — результат сравнения чисел на данном шаге не определён;
    • 2 > 1 — первое число больше (независимо от оставшихся цифр).
Таким образом, естественный порядок на числах соответствует лексикографическому порядку на их записях в позиционной системе счисления при условии, что эти записи дополнены ведущими нулями до одинаковой длины.
  • Арифметические операции над числами. Позиционная система счисления позволяет без труда выполнять сложение, вычитание, умножение, деление и деление с остатком чисел, зная только таблицу сложения однозначных чисел, а для трёх последних операций ещё и таблицу умножения в соответствующей системе (см., например, деление столбиком).

Экономичность

править

В цифровой технике система счисления с основанием   реализуется регистрами, состоящими из наборов триггеров, каждый из которых может принимать   различных состояний, кодирующих цифры числа. При этом особое значение приобретает экономичность системы счисления — возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков.[1] Если количество триггеров равно  , то общее количество знаков равно  , а количество представимых ими чисел соответственно —  . Как функция от  , это выражение достигает максимума при   равном числу e = 2,718281828….[3] При целых значениях   максимум достигается для  . Таким образом, наиболее экономичной является троичная система счисления (используемая в троичных ЭВМ), следом за которой идут двоичная система (традиционно используемая в большинстве распространённых ЭВМ) и четверичная.

Экономичность системы счисления — немаловажное обстоятельство с точки зрения её использования в вычислительной машине. Поэтому, хотя применение в вычислительной машине троичной системы вместо двоичной влечёт некоторые конструктивные трудности (при этом нужно пользоваться элементами, каждый из которых может находиться не в двух, а в трёх устойчивых состояниях), эта система уже была использована[4] в некоторых реально существующих вычислительных устройствах.[1]С. В. Фомин

Эквивалентное описание экономичности системы счисления можно получить, используя понятие информационной энтропии. При условии равновероятности появления каждой из цифр в записи числа информационная энтропия записи n-разрядного числа в системе счисления с основанием b принимает значение   (с точностью до постоянного коэффициента). Поэтому плотность записи (то есть, количество информации на один разряд) чисел в системе счисления с основанием b равна  , которая также принимает максимальное значение при b = e, а для целых значений b — при b = 3.

Переход к другому основанию

править

Перевод в десятичную систему счисления

править

Если целое число в  -ичной системе счисления равно

 

то для перевода в десятичную систему вычисляем следующую сумму:[5]

 

или в виде схемы Горнера:

 

Например:

 

Аналогичные действия имеют место также для дробной части: 

Перевод из десятичной системы счисления

править
Целая часть
  1. Последовательно (итеративно) делить с остатком целую часть десятичного числа на основание, пока десятичное число (частное) не станет равно нулю.
  2. Полученные при делении остатки являются цифрами нужного числа. Число в новой системе записывают, начиная с последнего остатка.[5][6]
Дробная часть
  1. Дробную часть десятичного числа умножаем на основание системы, в которую требуется перевести, и отделяем целую часть. Продолжаем умножать дробную часть на основание новой системы и отделять целую часть, пока число не станет равным 0 точно.
  2. Цифры дробной части в новой системе счисления — это целые части, полученные в первом шаге, которые, убывая по старшинству с самого старшего разряда дробной части, идут в порядке, в каком были они и были получены.

Примечание. Иногда при переводе дробного рационального числа из десятичной системы по таким алгоритмам может получиться бесконечная периодическая дробь: например,  . Чтобы обнаружить период, нужно провести итерации, описанные в первом пункте, и понять, не встретится ли та же дробная часть, что и была несколько итераций назад[7]. (О периодических дробях в разных системах счисления написано ниже.)

Примеры

  переведём в двоичную систему:

44 делим на 2. частное 22, остаток 0
22 делим на 2. частное 11, остаток 0
11 делим на 2. частное  5, остаток 1
 5 делим на 2. частное  2, остаток 1
 2 делим на 2. частное  1, остаток 0
 1 делим на 2. частное  0, остаток 1

Частное равно нулю — деление закончено. Теперь, записав все остатки снизу вверх, получим число  

Для дробной части алгоритм выглядит так:

0,625 умножаем на 2. Дробная часть 0,250. Целая часть 1.
0,250 умножаем на 2. Дробная часть 0,500. Целая часть 0.
0,500 умножаем на 2. Дробная часть 0,000. Целая часть 1.

Таким образом,  

Перевод из двоичной в восьмеричную и шестнадцатеричную системы

править

Для этого типа операций существует упрощённый алгоритм.[8]

Целая часть

править

Для восьмеричной — разбиваем переводимое число на количество цифр, равное степени 2 (2 возводится в ту степень, которая требуется, чтобы получить основание системы, в которую требуется перевести (2³=8), в данном случае 3, то есть триад). Преобразуем триады по таблице триад:

000 — 0; 100 — 4;
001 — 1; 101 — 5;
010 — 2; 110 — 6;
011 — 3; 111 — 7.

Для шестнадцатеричной — разбиваем переводимое число на количество цифр, равное степени 2 (2 возводится в ту степень, которая требуется, чтобы получить основание системы, в которую требуется перевести (24=16), в данном случае 4, то есть тетрад). Преобразуем тетрады по таблице тетрад:

0000 — 0; 0100 — 4; 1000 — 8; 1100 — C;
0001 — 1; 0101 — 5; 1001 — 9; 1101 — D;
0010 — 2; 0110 — 6; 1010 — A; 1110 — E;
0011 — 3; 0111 — 7; 1011 — B; 1111 — F.

Пример:

преобразуем 1011002
восьмеричная — 101 100 → 548
шестнадцатеричная — 0010 1100 → 2C16

Дробная часть

править

Перевод дробной части из двоичной системы счисления в системы счисления с основаниями 8 и 16 осуществляется точно так же, как и для целых частей числа, за тем лишь исключением, что разбивка на октавы и тетрады идёт вправо от десятичной запятой, недостающие разряды дополняются нулями справа. Например, рассмотренное выше число 1100,0112 будет выглядеть как 14,38 или C,616.

Перевод из восьмеричной и шестнадцатеричной систем в двоичную[8]

править

Для этого типа операций также существует упрощённый алгоритм, обратный вышенаписанному алгоритму.

Для восьмеричной — преобразуем по таблице в триплеты:

0 000 4 100
1 001 5 101
2 010 6 110
3 011 7 111

Для шестнадцатеричной — преобразуем по таблице в квартеты:

0 0000 4 0100 8 1000 C 1100 
1 0001 5 0101 9 1001 D 1101
2 0010 6 0110 A 1010 E 1110
3 0011 7 0111 B 1011 F 1111

Пример:

преобразуем
548 → 101 1002
2C16 → 0010 11002

Вариации и обобщения

править

Запись рациональных чисел

править

Рациональное число   в  -ичной системе счисления представляется в виде линейной комбинации (вообще говоря, бесконечной) степеней числа  :

 

где   — цифры целой части (до разделителя),   — цифры дробной части (после разделителя),   — число разрядов целой части.

Конечной записью в  -ичной системе счисления обладают только рациональные числа, представимые в виде  , где   и   — целые числа, то есть такие, после умножения которых на основание   за конечное число итераций возможно получить целое число:

 

где   и   представляют собой  -ичные записи соответственно частного и остатка от деления   на  .

Рациональные числа, не представимые в виде  , записываются в виде периодических дробей.

Симметричные системы счисления

править

Симметричные (уравновешенные, знакоразрядные) системы счисления по основанию   отличаются тем, что используют цифры не из множества  , а из множества   где, грубо говоря, все   цифр «отражаются» относительно нуля. Чтобы цифры были целыми, нужно, чтобы   было нечётным. В симметричных системах счисления не требуется дополнительных обозначений для знака числа.[9] Кроме того, вычисления в симметричных системах удобны тем, что не требуется особых правил округления — округление к ближайшему целому сводится к простому отбрасыванию лишних разрядов, что резко уменьшает систематические ошибки вычислений.

Чаще всего используется симметричная троичная система счисления с цифрами  . Она применяется в троичной логике и была технически реализована в вычислительной машине «Сетунь».

Отрицательные основания

править

Существуют позиционные системы с отрицательными основаниями, называемые нега-позиционными:

Нецелочисленные основания

править

Иногда также рассматривают позиционные системы счисления с нецелочисленными основаниями: рациональными, иррациональными, трансцендентными.

Примерами таких систем счисления являются:

Комплексные основания

править

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

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

Примеры

Далее будем записывать позиционную систему счисления в следующем виде  , где   — основание системы счисления, а A — множество цифр. В частности, множество A может иметь вид:

  •  
  •   где   и  . При   множество   превращается в множество  .

Примерами систем счисления с комплексными основаниями являются (далее j — мнимая единица):

  •  [12]
    • Пример:  
  •  [11]
    • Пример:  
  •  [13]
  •   где  ,   — целое положительное число, которое может принимать несколько значений при данном R;[14]
  •   где множество   состоит из комплексных чисел вида  , а числа   Например:  [13]
  •   где   .[15]
Двоичные комплексные системы счисления

Ниже перечислены основания двоичных позиционных систем счисления и представления чисел 2, −2 и −1 в них:

  •  :   (система счисления с натуральным основанием);
  •  :  ,  ,   (нега-позиционная система счисления);
  •  :  ,  ,   (система счисления с комплексным основанием);
  •  :  ,  ,   (система счисления с комплексным основанием);
  •  :  ,  ,   (система счисления с комплексным основанием);
  •  :  ,  ,   (система счисления с комплексным основанием).

Непоказательные системы счисления

править

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

 

позволяет записывать бо́льшие диапазоны чисел тем же числом знаков.

Примечания

править
  1. 1 2 3 4 С. В. Фомин. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике). Архивировано 16 октября 2004 года. (альтернативная ссылка Архивная копия от 2 июня 2013 на Wayback Machine)
  2. Битюков Сергей. 13 звуков и интервалов. Их восприятие и обозначение. Лады отклонения и модуляции (рус.). Хабр (7 августа 2021). Дата обращения: 26 августа 2021. Архивировано 12 августа 2021 года.
  3. Hayes, Brian. Third base (англ.) // American Scientist[англ.] : magazine. — 2001. — Vol. 89, no. 6. — P. 490—494. — doi:10.1511/2001.40.3268. Архивировано 24 марта 2016 года.
  4. См. Троичный компьютер.
  5. 1 2 Перевод чисел из одной системы счисления в другую онлайн. matworld.ru. Дата обращения: 8 мая 2021. Архивировано 9 мая 2021 года.
  6. Глава 4 — Арифметические основы компьютеров. mif.vspu.ru. Дата обращения: 8 мая 2021. Архивировано 19 февраля 2020 года.
  7. Перевод дробных чисел из одной системы счисления в другую — урок. Информатика, 11 класс. www.yaklass.ru. Дата обращения: 8 мая 2021. Архивировано 8 мая 2021 года.
  8. 1 2 Перевод чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно. www.5byte.ru. Дата обращения: 8 мая 2021. Архивировано 15 мая 2021 года.
  9. С. Б. Гашков. Системы счисления и их применение. — 2004. — 52 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8. Архивировано 12 января 2014 года. Архивированная копия. Дата обращения: 8 марта 2008. Архивировано из оригинала 12 января 2014 года.
  10. А. В. Никитин Система Бергмана Архивная копия от 5 мая 2009 на Wayback Machine.
  11. 1 2 Хмельник С. И. Специализированная ЦВМ для операций с комплексными числами // Вопросы радиоэлектроники. — 1964. — Т. XII, вып. 2. (недоступная ссылка)
  12. 1 2 Knuth D. E. An Imaginary Number System // Communication of the ACM. — 1960. — Т. 3, № 4. — С. 245—247. — doi:10.1145/367177.367233.
  13. 1 2 Хмельник С. И. Кодирование комплексных чисел и векторов. — Mathematics in Computers. — Израиль, 2004. — ISBN 978-0-557-74692-7. Архивировано 17 июня 2008 года.
  14. Хмельник С. И. Позиционное кодирование комплексных чисел // Вопросы радиоэлектроники. — 1966. — Т. XII, вып. 9. (недоступная ссылка)
  15. Khmelnik S.I. Method and system for processing complex numbers. — Patent USA, US2003154226 (A1). — 2001. Архивировано 9 января 2023 года.

Ссылки

править