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

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

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

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

В идеале система счисления будет:

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

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

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

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

Наиболее распространенной системой счисления является десятичная . Индийским математикам приписывают разработку целочисленной версии — индийско-арабской системы счисления . ^[1] Арьябхата из Кусумапуры разработал систему обозначений разрядов в 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 лет назад» означает «четыре балла и семь лет назад».

Более элегантной является позиционная система , также известная как нотация разрядов. Опять же, работая с базой 10, используются десять различных цифр 0, ..., 9, а положение цифры используется для обозначения степени десяти, на которую нужно умножить цифру, как в 304 = 3 × 100 + 0. ×10 + 4×1 или точнее 3×10 ² + 0×10 ¹ + 4×10 ⁰. Ноль, который не нужен в других системах, здесь имеет решающее значение, чтобы иметь возможность «пропустить» степень. Индо-арабская система счисления, зародившаяся в Индии и сейчас используемая во всем мире, представляет собой позиционную систему счисления с основанием 10.

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

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

В компьютерах основные системы счисления основаны на позиционной системе по основанию 2 ( двоичная система счисления ), с двумя двоичными цифрами , 0 и 1. Позиционные системы получаются путем группировки двоичных цифр по трем ( восьмеричная система счисления ) или четырем ( шестнадцатеричная система счисления ). система ) обычно используются. Для очень больших целых чисел основание 2. ³² или 2 ⁶⁴ (группировка двоичных цифр по 32 или 64, длине машинного слова ) используются, как, например, в GMP .

В некоторых биологических системах унарная система кодирования используется . Унарные цифры, используемые в нейронных цепях , отвечающих за пение птиц . ^[3]Ядром в мозгу певчих птиц, который играет роль как в обучении, так и в производстве птичьего пения, является 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 \times10 3) + (3 \times10 2) + (2 \times10 1) + (7 \times10 0)$ , отметив, что $100 = 1$ .

В общем, если b является основанием, записывают число в системе счисления по основанию b, выражая его в форме $a n b н + а п - 1 б п - 1 + а п - 2 б п - 2 + ... + а 0 б 0$ и записываем пронумерованные цифры $a n a n - 1 a n - 2 ... a 0$ в порядке убывания. Цифры представляют собой натуральные числа от 0 до $b - 1$ включительно.

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

Разделив цифры на две группы точкой, можно также записывать дроби в позиционной системе. Например, цифра 10,11 с основанием 2 обозначает $1\times2. 1 + 0\times2 0 + 1\times2 -1 + 1\times2 -2 = 2.75$ .

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

(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}.

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

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

{\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 10 = 0,0100110011001... 2$ ). Иррациональное число остается апериодическим (с бесконечным числом неповторяющихся цифр) во всех целочисленных основаниях. Таким образом, например, в системе счисления 2 $π = 3,1415926... 10$ можно записать как апериодическое 11,001001000011111... ₂ .

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

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

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

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

Обобщенные целые числа переменной длины [ править ]

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

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

Например, если пороговое значение для первой цифры равно b (т. е. 1), то a (т. е. 0) отмечает конец числа (оно имеет только одну цифру), поэтому в числах, содержащих более одной цифры, диапазон первой цифры равен только b–9 (т.е. 1–35), поэтому вес b ₁ равен 35 вместо 36. В более общем смысле, если t _n является порогом для n -й цифры, легко показать, что $b_{n+1}=36-t_{n}$ . Предположим, что пороговые значения для второй и третьей цифр равны c (т. е. 2), тогда диапазон второй цифры — a–b (т. е. 0–1), причем вторая цифра является наиболее значимой, а диапазон — c–9 (т. е. 2–35) при наличии третьей цифры. Обычно для любого n вес ( n + 1)-й цифры равен весу предыдущей, умноженной на (36 — порог n -й цифры). Таким образом, вес второго символа равен $36-t_{0}=35$ . А вес третьего символа $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, соответствует биективной нумерации , где нули соответствуют разделителям чисел с цифрами, отличными от нуля.

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

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

^ Дэвид Юджин Смит; Луи Чарльз Карпински (1911). Индо-арабские цифры . Джинн и компания.
^ Чоудхури, Арнаб. Разработка эффективного множителя с использованием DBNS . Журналы ГИАП. ISBN 978-93-83006-18-2 .
^ Фите, ИК; Сын, HS (2007). «Нейросетевые модели производства, обучения и кодирования пения птиц». В Сквайре, Л.; Олбрайт, Т.; Блум, Ф.; Гейдж, Ф.; Спитцер, Н. Новая энциклопедия неврологии.

Источники [ править ]

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

Внешние ссылки [ править ]

СМИ, связанные с системами счисления, на Викискладе?

[1] Дэвид Юджин Смит; Луи Чарльз Карпински (1911). Индо-арабские цифры . Джинн и компания.

[2] Чоудхури, Арнаб. Разработка эффективного множителя с использованием DBNS . Журналы ГИАП. ISBN 978-93-83006-18-2 .

[3] Фите, ИК; Сын, HS (2007). «Нейросетевые модели производства, обучения и кодирования пения птиц». В Сквайре, Л.; Олбрайт, Т.; Блум, Ф.; Гейдж, Ф.; Спитцер, Н. Новая энциклопедия неврологии.

[1]

[2]

[3]