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

Обозначения для выражения чисел

Числа, записанные в разных системах счисления

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

Одна и та же последовательность символов может представлять разные числа в разных системах счисления. Например, «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 ² + 0×10 ¹ + 4×10 ⁰ . Ноль, который не нужен в других системах, здесь имеет решающее значение, чтобы иметь возможность «пропустить» степень. Индо-арабская система счисления, которая возникла в Индии и теперь используется во всем мире, является позиционной системой с основанием 10.

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

Позиционная десятичная система в настоящее время повсеместно используется в человеческой письменности. Основание 1000 также используется (хотя и не повсеместно), путем группировки цифр и рассмотрения последовательности из трех десятичных цифр как одной цифры. Это значение общепринятой нотации 1,000,234,567, используемой для очень больших чисел.

В компьютерах основные системы счисления основаны на позиционной системе с основанием 2 ( двоичная система счисления ), с двумя двоичными цифрами , 0 и 1. Обычно используются позиционные системы, полученные путем группировки двоичных цифр по три ( восьмеричная система счисления ) или четыре ( шестнадцатеричная система счисления ). Для очень больших целых чисел используются основания 2 ³² или 2 ⁶⁴ (группировка двоичных цифр по 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 × ¹⁰² ) + ( 2 ×101 ⁾ + ( 7 ×100 ⁾ , при этом 100 = 1 .

В общем случае, если основанием является b , то число в системе счисления с основанием b записывается в виде a _n b ⁿ + a _{n − 1} b ^{n − 1} + a _{n − 2} b ^{n − 2} + ... + a ₀ b ⁰ и пронумерованные цифры a _n a _{n − 1} a _{n − 2} ... a ₀ записываются в порядке убывания. Цифры — это натуральные числа от 0 до b − 1 включительно.

Если в тексте (например, в этом) обсуждается несколько оснований и существует неоднозначность, основание (само по себе представленное в базе 10) добавляется в нижнем индексе справа от числа, например: _{основание} числа . Если контекст не указывает иное, числа без нижнего индекса считаются десятичными.

Используя точку для разделения цифр на две группы, можно также записывать дроби в позиционной системе. Например, число 10,11 с основанием 2 обозначает 1×2 ¹ + 0×2 ⁰ + 1×2 ⁻¹ + 1×2 ⁻² = 2,75 .

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

${\displaystyle (a_{n}a_{n-1}\cdots a_{1}a_{0}.c_{1}c_{2}c_{3}\cdots )_{b}=\sum _{k=0}^{n}a_{k}b^{k}+\sum _{k=1}^{\infty }c_{k}b^{-k}.}$

Числа b ^k и b ^{− k} являются весами соответствующих цифр. Позиция k является логарифмом соответствующего веса w , то есть . Наивысшая используемая позиция близка к порядку величины числа. ${\displaystyle k=\log _{b}w=\log _{b}b^{k}}$

Количество отметок, необходимых в унарной системе счисления для описания веса , составило бы w . В позиционной системе для описания веса требуется всего лишь , при k ≥ 0. Например, для описания веса 1000 требуется четыре цифры, поскольку . Количество цифр, необходимых для описания позиции, равно (в позициях 1, 10, 100,... только для простоты в десятичном примере). ${\displaystyle k+1=\log _{b}w+1}$ ${\displaystyle \log _{10}1000+1=3+1}$ ${\displaystyle \log _{b}k+1=\log _{b}\log _{b}w+1}$

${\displaystyle {\begin{array}{l|rrrrrrr}{\text{Position}}&3&2&1&0&-1&-2&\cdots \\\hline {\text{Weight}}&b^{3}&b^{2}&b^{1}&b^{0}&b^{-1}&b^{-2}&\cdots \\{\text{Digit}}&a_{3}&a_{2}&a_{1}&a_{0}&c_{1}&c_{2}&\cdots \\\hline {\text{Decimal example weight}}&1000&100&10&1&0.1&0.01&\cdots \\{\text{Decimal example digit}}&4&3&2&7&0&0&\cdots \end{array}}}$

Число имеет конечное или повторяющееся расширение тогда и только тогда, когда оно рационально ; это не зависит от основания. Число, которое заканчивается в одном основании, может повторяться в другом (таким образом, 0,3 ₁₀ = 0,0100110011001... ₂ ). Иррациональное число остается апериодическим (с бесконечным числом неповторяющихся цифр) во всех целочисленных основаниях. Таким образом, например, в основании 2, π = 3,1415926... ₁₀ можно записать как апериодическое 11,001001000011111... ₂ .

Размещение надчеркиваний , n , или точек, ṅ , над общими цифрами является соглашением, используемым для представления повторяющихся рациональных расширений. Таким образом:

14/11 = 1,272727272727... = 1, 27   или 321,3217878787878... = 321,321 78 .

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

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

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

Более общим является использование смешанной системы счисления (здесь она обозначается как little-endian ), например , и т. д. ${\displaystyle a_{0}a_{1}a_{2}}$ ${\displaystyle a_{0}+a_{1}b_{1}+a_{2}b_{1}b_{2}}$

Это используется в Punycode , одним из аспектов которого является представление последовательности неотрицательных целых чисел произвольного размера в виде последовательности без разделителей, «цифр» из набора из 36: a–z и 0–9, представляющих 0–25 и 26–35 соответственно. Существуют также так называемые пороговые значения ( ), которые фиксируются для каждой позиции в числе. Цифра (в данной позиции в числе), которая ниже соответствующего ей порогового значения , означает, что она является наиболее значимой цифрой, следовательно, в строке это конец числа, а следующий символ (если присутствует) является наименее значимой цифрой следующего числа. ${\displaystyle t_{0},t_{1},\ldots }$ ${\displaystyle a_{i}}$ ${\displaystyle t_{i}}$

Например, если пороговое значение для первой цифры равно b (т. е. 1), то a (т. е. 0) обозначает конец числа (в нем всего одна цифра), поэтому в числах, состоящих из более чем одной цифры, диапазон первой цифры составляет только b–9 (т. е. 1–35), поэтому вес b ₁ равен 35 вместо 36. В более общем случае, если t _n является порогом для n -й цифры, легко показать, что . Предположим, что пороговые значения для второй и третьей цифр равны c (т. е. 2), тогда диапазон второй цифры равен a–b (т. е. 0–1), причем вторая цифра является наиболее значимой, в то время как диапазон равен c–9 (т. е. 2–35) при наличии третьей цифры. Как правило, для любого n вес ( n  + 1)-й цифры равен весу предыдущей, умноженному на единицу (36 − порог n -й цифры). Таким образом, вес второго символа равен . А вес третьего символа равен . ${\displaystyle b_{n+1}=36-t_{n}}$ ${\displaystyle 36-t_{0}=35}$ ${\displaystyle 35(36-t_{1})=35\cdot 34=1190}$

Итак, мы имеем следующую последовательность чисел, содержащую не более 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, соответствует биективной нумерации , где нули соответствуют разделителям чисел с цифрами, отличными от нуля.

Смотрите также

• Список систем счисления
• Форматы компьютерных чисел
• Нестандартные позиционные системы счисления
• История древних систем счисления
• История чисел
• Список тем по системам счисления
• Названия чисел
• Повторяющаяся десятичная дробь
• Система счисления остатков
• Длинные и короткие чешуйки
• Научная нотация
• -иллион
• Числовое познание
• Система счисления

Ссылки

1. O'Connor, JJ и Robertson, EF Арабские цифры. Январь 2001 г. Получено 20 февраля 2007 г.
2. Билл Кассельман (февраль 2007 г.). "Все за ничто". Тематическая колонка . AMS.
3. Брэдли, Джереми. «Как были изобретены арабские цифры». www.theclassroom.com . Получено 22 июля 2020 г.
4. Дэвид Юджин Смит; Луис Чарльз Карпински (1911). Индо-арабские цифры. Джинн и компания.
5. Чоудхури, Арнаб. Разработка эффективного множителя с использованием DBNS. Журналы GIAP. ISBN 978-93-83006-18-2.
6. Fiete, IR; Seung, HS (2007). «Нейросетевые модели создания, обучения и кодирования пения птиц». В Squire, L.; Albright, T.; Bloom, F.; Gage, F.; Spitzer, N. Новая энциклопедия нейронауки.

Источники

• Жорж Ифра. Всеобщая история чисел: от доисторических времен до изобретения компьютера , Wiley, 1999. ISBN 0-471-37568-3 . 
• Д. Кнут . Искусство программирования . Том 2, 3-е изд. Эддисон–Уэсли . С. 194–213, «Позиционные системы счисления».
• AL Kroeber (Альфред Луис Крёбер) (1876–1960), Справочник индейцев Калифорнии, Бюллетень 78 Бюро американской этнологии Смитсоновского института (1919)
• Дж. П. Мэллори; Д. К. Адамс, Энциклопедия индоевропейской культуры , издательство Fitzroy Dearborn, Лондон и Чикаго, 1997.
• Ганс Дж. Ниссен; Питер Дамероу; Роберт К. Энглунд (1993). Архаичная бухгалтерия: ранние письменные работы и методы экономического управления на древнем Ближнем Востоке . Издательство Чикагского университета . ISBN 978-0-226-58659-5.
• Шмандт-Бессерат, Дениз (1996). Как появилось письмо . Издательство Техасского университета . ISBN 978-0-292-77704-0.
• Заславский, Клаудия (1999). Африка имеет значение: число и закономерности в африканских культурах . Chicago Review Press. ISBN 978-1-55652-350-2.

Внешние ссылки

• Медиафайлы по теме Системы счисления на Wikimedia Commons