Система счисления — это система записи чисел, то есть математическая нотация для представления чисел заданного набора с использованием цифр или других символов последовательным образом.
Одна и та же последовательность символов может представлять разные числа в разных системах счисления. Например, «11» представляет число одиннадцать в десятичной или десятичной системе счисления (сегодня это самая распространенная система в мире), число три в двоичной или двузначной системе счисления (используется в современных компьютерах) и число два в унарной системе счисления (используется при подсчете очков).
Число, которое представляет цифра, называется ее значением. Не все системы счисления могут представлять один и тот же набор чисел; например, римские цифры не могут представлять число ноль.
В идеале система счисления должна:
Например, обычное десятичное представление дает каждому ненулевому натуральному числу уникальное представление в виде конечной последовательности цифр, начинающейся с ненулевой цифры.
Системы счисления иногда называют системами счисления , но это название неоднозначно, поскольку оно может относиться к разным системам счисления, таким как система действительных чисел , система комплексных чисел , различные гиперкомплексные системы счисления, система p -адических чисел и т. д. Однако такие системы не являются темой данной статьи.
Первой настоящей письменной позиционной системой счисления считается индо-арабская система счисления . Эта система была создана в 7 веке в Индии, [1] но еще не была в своей современной форме, потому что использование цифры ноль еще не было широко принято. Вместо нуля иногда цифры отмечались точками, чтобы указать их значение, или в качестве заполнителя использовался пробел. Первое широко признанное использование нуля было в 876 году. [2] Первоначальные цифры были очень похожи на современные, вплоть до глифов, используемых для представления цифр. [1]
К XIII веку западные арабские цифры были приняты в европейских математических кругах ( Фибоначчи использовал их в своей Liber Abaci ). Они начали входить в общее употребление в XV веке. [3] К концу XX века практически все некомпьютерные вычисления в мире выполнялись с помощью арабских цифр, которые заменили родные системы счисления в большинстве культур.
Точный возраст цифр майя неясен, но возможно, что она старше, чем индо-арабская система. Система была двадцатеричной (основание 20), поэтому в ней было двадцать цифр. Майя использовали символ ракушки для обозначения нуля. Цифры писались вертикально, с единицами внизу. У майя не было эквивалента современного десятичного разделителя , поэтому их система не могла представлять дроби.
Тайская система счисления идентична индо-арабской системе счисления, за исключением символов, используемых для представления цифр. Использование этих цифр в Таиланде менее распространено , чем когда-то, но они все еще используются наряду с арабскими цифрами.
Стержневые цифры, письменные формы счетных палочек , когда-то использовавшиеся китайскими и японскими математиками, представляют собой десятичную позиционную систему, способную представлять не только ноль, но и отрицательные числа. Сами счетные палочки появились раньше индо-арабской системы счисления. Цифры Сучжоу являются вариантами стержневых цифр.
Наиболее часто используемая система счисления — десятичная . Индийским математикам приписывают разработку целочисленной версии, индо-арабской системы счисления . [4] Арьябхата из Кусумапуры разработал позиционную систему счисления в V веке, а столетие спустя Брахмагупта ввел символ для нуля. Система медленно распространилась на другие соседние регионы, такие как Аравия, из-за их торговой и военной деятельности с Индией. Математики Ближнего Востока расширили систему, включив в нее отрицательные степени 10 (дроби), как записано в трактате сирийского математика Абу-ль-Хасана аль-Уклидиси в 952–953 годах, а десятичная точка была введена [ когда? ] Синдом ибн Али , который также написал самый ранний трактат об арабских цифрах. Затем индо-арабская система счисления распространилась в Европу благодаря торговле купцов, и цифры, используемые в Европе, называются арабскими цифрами , поскольку они узнали их от арабов.
Простейшей системой счисления является унарная система счисления , в которой каждое натуральное число представлено соответствующим числом символов. Если , например, выбран символ / , то число семь будет представлено как /////// . Метки счета представляют собой одну из таких систем, которая все еще широко используется. Унарная система полезна только для небольших чисел, хотя она играет важную роль в теоретической информатике . Гамма-кодирование Элиаса , которое обычно используется при сжатии данных , выражает числа произвольного размера, используя унарность для указания длины двоичного числа.
Унарную запись можно сократить, введя различные символы для определенных новых значений. Очень часто эти значения являются степенями числа 10; так, например, если / обозначает единицу, − — десять, а + — 100, то число 304 можно компактно представить как +++ //// , а число 123 — как + − − /// без необходимости в нуле. Это называется знаково-значной записью . Древнеегипетская система счисления была такого типа, а римская система счисления была модификацией этой идеи.
Еще более полезными являются системы, которые используют специальные сокращения для повторений символов; например, используя первые девять букв алфавита для этих сокращений, где A означает «одно появление», B — «два появления» и т. д., можно было бы тогда написать C+ D/ для числа 304 (количество этих сокращений иногда называют основой системы ). Эта система используется при записи китайских цифр и других восточноазиатских цифр, основанных на китайских. Система счисления английского языка относится к этому типу («триста [и] четыре»), как и системы других разговорных языков, независимо от того, какие письменные системы они приняли. Однако во многих языках используются смеси основ и другие особенности, например, 79 во французском языке — soixante dix-neuf ( 60 + 10 + 9 ), а в валлийском — pedwar ar bymtheg a thrigain ( 4 + (5 + 10) + (3 × 20) ) или (несколько архаично) pedwar ugain namyn un ( 4 × 20 − 1 ). В английском языке можно сказать «четыре балла минус один», как в знаменитой Геттисбергской речи, представляющей «87 лет назад» как «четыре балла и семь лет назад».
Более элегантной является позиционная система , также известная как система счисления с разрядными значениями. Позиционные системы классифицируются по их основанию или радикалу , который является числом символов, называемых цифрами, используемых в системе. В десятичной системе используются десять различных цифр 0, ..., 9, а положение цифры используется для обозначения степени десяти, на которую цифра должна быть умножена, как в 304 = 3×100 + 0×10 + 4×1 или, точнее, 3×10 2 + 0×10 1 + 4×10 0 . Ноль, который не нужен в других системах, здесь имеет решающее значение, чтобы иметь возможность «пропустить» степень. Индо-арабская система счисления, которая возникла в Индии и теперь используется во всем мире, является позиционной системой с основанием 10.
Арифметика в позиционных системах намного проще, чем в более ранних аддитивных; кроме того, аддитивным системам требуется большое количество различных символов для различных степеней числа 10; позиционной системе требуется всего десять различных символов (предполагая, что она использует основание 10). [5]
Позиционная десятичная система в настоящее время повсеместно используется в человеческой письменности. Основание 1000 также используется (хотя и не повсеместно), путем группировки цифр и рассмотрения последовательности из трех десятичных цифр как одной цифры. Это значение общепринятой нотации 1,000,234,567, используемой для очень больших чисел.
В компьютерах основные системы счисления основаны на позиционной системе с основанием 2 ( двоичная система счисления ), с двумя двоичными цифрами , 0 и 1. Обычно используются позиционные системы, полученные путем группировки двоичных цифр по три ( восьмеричная система счисления ) или четыре ( шестнадцатеричная система счисления ). Для очень больших целых чисел используются основания 2 32 или 2 64 (группировка двоичных цифр по 32 или 64, длина машинного слова ), как, например, в GMP .
В некоторых биологических системах используется унарная система кодирования . Унарные числа используются в нейронных цепях, ответственных за производство птичьего пения . [6] Ядро в мозге певчих птиц, которое играет роль как в обучении, так и в производстве птичьего пения, — это HVC ( высокий вокальный центр ). Командные сигналы для различных нот в птичьем пении исходят из разных точек в HVC. Это кодирование работает как пространственное кодирование, которое является эффективной стратегией для биологических цепей из-за его присущей простоты и надежности.
Цифры, используемые при записи чисел с помощью цифр или символов, можно разделить на два типа, которые можно назвать арифметическими цифрами (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) и геометрическими цифрами (1, 10, 100, 1000, 10000 ...) соответственно. Знаковые системы используют только геометрические цифры, а позиционные системы используют только арифметические цифры. Знаковая система не нуждается в арифметических цифрах, поскольку они образуются путем повторения (за исключением ионической системы ), а позиционная система не нуждается в геометрических цифрах, поскольку они образуются путем позиционирования. Однако в разговорной речи используются как арифметические, так и геометрические цифры.
В некоторых областях компьютерных наук используется модифицированная позиционная система счисления с основанием k , называемая биективной нумерацией , в которой цифры 1, 2, ..., k ( k ≥ 1 ) и ноль представлены пустой строкой. Это устанавливает биекцию между множеством всех таких строк цифр и множеством неотрицательных целых чисел, избегая неуникальности, вызванной ведущими нулями. Биективная система счисления с основанием k также называется k -адической нотацией, не путать с p -адическими числами . Биективная основа 1 совпадает с унарной.
В позиционной системе счисления с основанием b (где b — натуральное число больше 1, называемое основанием системы ) , используются b основных символов (или цифр), соответствующих первым b натуральным числам, включая ноль. Для генерации остальных цифр используется положение символа на рисунке. Символ в последней позиции имеет свое собственное значение, и по мере его перемещения влево его значение умножается на b .
Например, в десятичной системе счисления (основание 10) число 4327 означает ( 4 ×103 ) + ( 3 × 102 ) + ( 2 ×101 ) + ( 7 ×100 ) , при этом 100 = 1 .
В общем случае, если основанием является b , то число в системе счисления с основанием b записывается в виде a n b n + a n − 1 b n − 1 + a n − 2 b n − 2 + ... + a 0 b 0 и пронумерованные цифры a n a n − 1 a n − 2 ... a 0 записываются в порядке убывания. Цифры — это натуральные числа от 0 до b − 1 включительно.
Если в тексте (например, в этом) обсуждается несколько оснований и существует неоднозначность, основание (само по себе представленное в базе 10) добавляется в нижнем индексе справа от числа, например: основание числа . Если контекст не указывает иное, числа без нижнего индекса считаются десятичными.
Используя точку для разделения цифр на две группы, можно также записывать дроби в позиционной системе. Например, число 10,11 с основанием 2 обозначает 1×2 1 + 0×2 0 + 1×2 −1 + 1×2 −2 = 2,75 .
В общем случае числа в системе счисления с основанием b имеют вид:
Числа b k и b − k являются весами соответствующих цифр. Позиция k является логарифмом соответствующего веса w , то есть . Наивысшая используемая позиция близка к порядку величины числа.
Количество отметок, необходимых в унарной системе счисления для описания веса , составило бы w . В позиционной системе для описания веса требуется всего лишь , при k ≥ 0. Например, для описания веса 1000 требуется четыре цифры, поскольку . Количество цифр, необходимых для описания позиции, равно (в позициях 1, 10, 100,... только для простоты в десятичном примере).
Число имеет конечное или повторяющееся расширение тогда и только тогда, когда оно рационально ; это не зависит от основания. Число, которое заканчивается в одном основании, может повторяться в другом (таким образом, 0,3 10 = 0,0100110011001... 2 ). Иррациональное число остается апериодическим (с бесконечным числом неповторяющихся цифр) во всех целочисленных основаниях. Так, например, в основании 2, π = 3,1415926... 10 можно записать как апериодическое 11,001001000011111... 2 .
Размещение надчеркиваний , n , или точек, ṅ , над общими цифрами является соглашением, используемым для представления повторяющихся рациональных расширений. Таким образом:
Если b = p — простое число , то можно определить числа с основанием p, расширение которых влево никогда не останавливается; такие числа называются p -адическими числами .
Также можно определить вариант основания b, в котором цифры могут быть положительными или отрицательными; это называется представлением знаковых цифр .
Более общим является использование смешанной системы счисления (здесь она обозначается как little-endian ), например , и т. д.
Это используется в Punycode , одним из аспектов которого является представление последовательности неотрицательных целых чисел произвольного размера в виде последовательности без разделителей, «цифр» из набора из 36: a–z и 0–9, представляющих 0–25 и 26–35 соответственно. Существуют также так называемые пороговые значения ( ), которые фиксируются для каждой позиции в числе. Цифра (в данной позиции в числе), которая ниже соответствующего ей порогового значения , означает, что она является наиболее значимой цифрой, следовательно, в строке это конец числа, а следующий символ (если присутствует) является наименее значимой цифрой следующего числа.
Например, если пороговое значение для первой цифры равно b (т. е. 1), то a (т. е. 0) обозначает конец числа (в нем всего одна цифра), поэтому в числах, состоящих из более чем одной цифры, диапазон первой цифры составляет только b–9 (т. е. 1–35), поэтому вес b 1 равен 35 вместо 36. В более общем случае, если t n является порогом для n -й цифры, легко показать, что . Предположим, что пороговые значения для второй и третьей цифр равны c (т. е. 2), тогда диапазон второй цифры равен a–b (т. е. 0–1), причем вторая цифра является наиболее значимой, в то время как диапазон равен c–9 (т. е. 2–35) при наличии третьей цифры. Как правило, для любого n вес ( n + 1)-й цифры равен весу предыдущей, умноженному на единицу (36 − порог n -й цифры). Таким образом, вес второго символа равен . А вес третьего символа равен .
Итак, у нас есть следующая последовательность чисел, содержащая не более 3 цифр:
а (0), ба (1), ка (2), ..., 9 а (35), бб (36), цб (37), ..., 9 б (70), бка (71), ..., 99 а (1260), бцб (1261), ..., 99 б (2450).
В отличие от обычной системы счисления, основанной на n , существуют числа типа 9 b , где 9 и b представляют каждое число 35; однако это представление уникально, поскольку ac и aca не допускаются — первая буква a завершила бы каждое из этих чисел.
Гибкость в выборе пороговых значений позволяет оптимизировать количество цифр в зависимости от частоты встречаемости чисел различной величины.
Случай, когда все пороговые значения равны 1, соответствует биективной нумерации , где нули соответствуют разделителям чисел с цифрами, отличными от нуля.
Медиафайлы по теме Системы счисления на Wikimedia Commons
