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

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

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

Одна и та же последовательность символов может означать разные числа в разных системах счисления. Например, "11" в десятичной системе (сегодня самой распространённой в мире) означает число одиннадцать, в двоичной системе (используется в современных компьютерах) — число три, а в унарной системе (применяемой при счёте зарубками) — число два.

Число, которое обозначает запись, называется его значением. Кроме того, не все системы счисления способны выражать одинаковые множества чисел; например, в римской, греческой и египетской нотации нет символа для числа ноль.

Идеальная система счисления должна:

• Охватывать полезное множество чисел (например, все целые или рациональные числа)
• Давать каждому числу единственное, однозначное представление (или хотя бы стандартное)
• Отражать алгебраическую и арифметическую структуру чисел

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

Иногда системы счисления называют числовыми системами, однако этот термин неоднозначен, так как он может обозначать и иные математические системы: систему действительных чисел, систему комплексных чисел, различные гиперкомплексные системы, систему p-адических чисел и т. д. Тем не менее, эта статья не об этих системах.

История

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

Индийские математики, например Брахмагупта в VII веке, сыграли решающую роль в формализации арифметических правил и введении понятия нуля. Позднее исламские учёные, такие как Аль-Хорезми, развили эти идеи. С развитием систем счисления эффективность позиционной записи и введение нуля способствовали формированию современной записи чисел, оказав влияние на мировую торговлю, науку и технологии.

Первой подлинной позиционной системой считается индийско-арабская система счисления. Она сложилась в VII веке в Индии^[1], но ещё не в современном виде, так как цифра ноль не была широко принята. Вместо нуля иногда ставились точки или использовался пробел. Первое широко признанное применение нуля относится к 876 году^[2]. Первоначальные цифры были очень похожи на современные, вплоть до используемых символов^[1].

К XIII веку западно-арабские цифры начали применяться в Европе. Фибоначчи использовал их в своём Liber Abaci. Несмотря на первоначальное сопротивление, индийско-арабские цифры получили признание благодаря удобству в вычислениях, особенно в торговле и банковском деле.

Изобретение печатного станка в XV веке способствовало стандартизации их использования, так как печатные тексты предпочитали их римским цифрам. К концу XV века они вошли в обиход^[3]. К концу XX века почти все некомпьютерные вычисления в мире выполнялись арабскими цифрами, вытеснившими национальные системы.

В XVII веке система стала доминировать в научных трудах и повлияла на открытия Исаака Ньютона и Рене Декарта. В XIX–XX веках широкое распространение арабских цифр обеспечило развитие мировой финансовой системы, инженерии и технологий, заложив основу для вычислительной техники и цифровых данных.

Другие исторические системы счисления с использованием цифр

Точный возраст цифр майя неизвестен, но возможно, они старше индийско-арабской системы. Эта система была двадцатеричной (с основанием 20) и включала двадцать цифр. Майя использовали символ раковины для обозначения нуля. Цифры записывались вертикально, разряд единиц располагался внизу. У майя не было аналога современного десятичного разделителя, поэтому их система не могла представлять дроби.

Тайская система цифр идентична индийско-арабской системе, за исключением используемых символов. Сейчас эти цифры в Таиланде применяются реже, чем раньше, но до сих пор используются наряду с арабскими цифрами.^[4]

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

Математический трактат Sūnzĭ Suànjīng, датируемый III–V вв. н.э., содержит подробные инструкции по этой системе. Считается, что она применялась как минимум с IV века до н.э.^[5] Изначально ноль рассматривался не как число, а как пустое место.^[6] Позднее появились правила для записи нуля и отрицательных чисел.

Первое использование круглого символа 〇 для нуля засвидетельствовано в Математическом трактате в девяти разделах 1247 года.^[7] Происхождение этого символа неизвестно; возможно, он произошёл от модифицированного квадратного знака^[8]. Сучжоуские цифры, потомки цифр-палочек, до сих пор применяются для некоторых коммерческих целей.

Основные системы счисления

Наиболее широко используемая система счисления — десятичная. Разработку целочисленного варианта приписывают индийским математикам, создавшим индийско-арабскую систему цифр.^[8] В V веке Арьябхата из Кусумапуры разработал позиционную запись, а спустя столетие Брахмагупта ввёл символ для нуля. Постепенно система распространилась в Аравию благодаря торговым и военным контактам. Математики Ближнего Востока расширили систему, добавив отрицательные степени числа 10 (дроби). Об этом писал сирийский математик Абу-ль-Хасан аль-Уклидиси (952–953 гг.). Синд ибн Али ввёл запись десятичной точки и написал первый трактат об арабских цифрах. В Европу система попала через торговцев, и цифры стали называться «арабскими».

Самая простая система — унарная, где каждое натуральное число представляется соответствующим числом символов. Например, если выбран символ /, то число 7 записывается как ///////. Засечки (tally marks) — пример такой системы, сохранившейся до наших дней. Унарная система удобна только для малых чисел, но играет важную роль в теоретической информатике. Например, кодирование Элиаса-гамма использует унарную запись для обозначения длины двоичного числа.

Унарную запись можно сокращать, вводя новые символы для некоторых значений, обычно степеней 10. Например, если / — 1, − — 10, + — 100, то число 304 записывается как +++ ////, а 123 как + − − ///. Такой метод называется аддитивной записью. К этой категории относилась система древнеегипетских чисел, а римская система была её модификацией.

Более полезны системы, применяющие сокращения для повторов символов. Например, используя первые девять букв алфавита (A — один раз, B — два раза и т.д.), можно записать число 304 как C+ D/. Такая система используется в китайских и других восточноазиатских числах. Английский язык также принадлежит к этому типу («three hundred four»). Но во многих языках применяются смешанные основы: например, по-французски 79 — soixante dix-neuf (60 + 10 + 9).

Наиболее совершенной является позиционная система (система разрядов). Системы классифицируются по основанию (радиксу). В десятичной системе используются цифры 0–9, а позиция цифры показывает, на какую степень 10 её умножить: 304 = 3×100 + 0×10 + 4×1, то есть 3×10² + 0×10¹ + 4×10⁰. Ноль имеет здесь решающее значение, так как позволяет «пропускать» разряды.

Арифметические действия в позиционных системах выполнять гораздо проще, чем в аддитивных. В последних требуется множество символов для разных степеней 10, а в десятичной системе достаточно десяти.^[10]

Сегодня десятичная позиционная система универсальна в письменности. Иногда используется основание 1000 (например, запись 1,000,234,567).

В компьютерах основная система — двоичная (основание 2). Используются цифры 0 и 1. Группировка двоичных цифр по 3 даёт восьмеричную систему, по 4 — шестнадцатеричную. Для очень больших чисел применяют системы с основаниями 2³² или 2⁶⁴.

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

Цифры делятся на два типа: арифметические (0–9) и геометрические (1, 10, 100...). Знаково-значные системы используют только геометрические цифры, а позиционные — только арифметические. В устной речи применяются оба типа.

В информатике применяется модифицированная система с основанием k, называемая биективной. В ней цифры 1, 2, …, k, а ноль обозначается пустой строкой. Биективная система с основанием 1 равна унарной.

Позиционные системы подробно

В позиционной системе счисления с основанием b (b — натуральное число больше 1, называемое основанием или радиксом системы) используется b основных символов (цифр), соответствующих первым b натуральным числам, включая ноль. Остальные числа формируются за счёт положения цифры: крайняя правая цифра имеет собственное значение, при переходе влево её значение умножается на b.

Например, в десятичной системе (основание 10) число 4327 означает: (4×10³) + (3×10²) + (2×10¹) + (7×10⁰), где 10⁰ = 1.

В общем случае число в системе с основанием b записывается в виде:
aₙbⁿ + aₙ₋₁bⁿ⁻¹ + ... + a₀b⁰, а цифры aₙ aₙ₋₁ ... a₀ записываются по порядку. Цифры — это натуральные числа от 0 до b – 1.

Если обсуждаются разные основания, для избежания неоднозначности основание указывается в нижнем индексе:числооснование. Если не указано, число считается десятичным.

Используя точку для разделения, можно записывать дроби. Например, в системе с основанием 2 запись 10.11 означает: 1×2¹ + 0×2⁰ + 1×2⁻¹ + 1×2⁻² = 2.75.

В общем случае число в системе с основанием b имеет вид:

Значения bᵏ и b⁻ᵏ называются весами цифр. Позиция k — это логарифм соответствующего веса. Наибольшая позиция соответствует порядку числа.

В унарной системе для веса потребовалось бы w палочек. В позиционной системе достаточно лишь logbw + 1 цифр. Например, для 1000 нужны 4 цифры, так как log₁₀1000 + 1 = 4.

Рациональные числа всегда имеют конечное или периодическое представление. В одной системе число может быть конечным, а в другой — периодическим (например, 0.3₁₀ = 0.010011...₂). Иррациональные числа во всех основаниях дают непериодическую бесконечную запись (например, π).

Для обозначения периодов используется черта над цифрами (27). Например: 14/11 = 1.272727... = 1.27.

Если b = p — простое число, можно определить систему с основанием p, где запись бесконечно продолжается влево; это p-адические числа.

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

Обобщённые целые числа переменной длины

Более общий подход — это использование смешанной системы оснований (здесь в форме little-endian), например: a₀a₁a₂ для выражения a₀ + a₁·b₁ + a₂·b₁·b₂ и так далее.

Это используется в Punycode, где последовательность неотрицательных целых чисел произвольного размера представляется строкой без разделителей, используя «цифры» из 36 символов: a–z и 0–9, обозначающих значения от 0 до 25 и от 26 до 35 соответственно.

Существуют также так называемые пороговые значения t₀, t₁, ..., фиксированные для каждой позиции числа. Если цифра aᵢ в данной позиции меньше своего порога tᵢ, это означает, что она — старший разряд. Таким образом, в строке это указывает конец числа, а следующий символ (если он есть) — младший разряд следующего числа.

Например, если пороговое значение для первой цифры b = 1, то a = 0 означает конец числа (одноразрядное число). Следовательно, для многозначных чисел первая цифра может быть только в диапазоне b–9 (1–35). Тогда вес b₁ равен 35 вместо 36. В общем виде, если tₙ — порог для n-й цифры, то:
bₙ₊₁ = 36 − tₙ

Пусть пороговые значения для второй и третьей цифры равны c = 2. Тогда диапазон второй цифры — a–b (0–1), если это старший разряд, и c–9 (2–35), если есть третий разряд. В общем случае вес (n + 1)-й цифры равен весу предыдущей, умноженному на 36 − tₙ.

Пример:
Вес 2-го символа = 36 − t₀ = 35
Вес 3-го символа = 35 × (36 − t₁) = 35 × 34 = 1190

Таким образом, получаем следующую последовательность чисел максимум с 3 разрядами:
a (0), ba (1), ca (2), ..., 9a (35), bb (36), cb (37), ..., 9b (70), bca (71), ..., 99a (1260), bcb (1261), ..., 99b (2450)

В отличие от обычной системы счисления, здесь встречаются числа вроде 9b, где и 9, и b обозначают 35. Но представление остаётся однозначным, так как ac и aca недопустимы — первый символ a завершает число.

Гибкость в выборе пороговых значений позволяет оптимизировать количество цифр в зависимости от частоты встречаемости чисел разных размеров.

Случай, когда все пороговые значения равны 1, соответствует биективной нумерации, где нули играют роль разделителей чисел с ненулевыми цифрами.