Система счисления - Numeral system

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

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

Число, которое представляет цифра, называется ее значением.

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

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

Например, обычный десятичный представление целых чисел дает каждому ненулевому целому числу уникальное представление в виде конечный последовательность из цифры, начиная с ненулевой цифры. Однако, когда десятичное представление используется для рациональный или действительные числа, такие числа, как правило, имеют бесконечное количество представлений, например, 2.31 также можно записать как 2.310, 2.3100000, 2.309999999 ... и т. д., все из которых имеют одинаковое значение, за исключением некоторых научных и других контексты, в которых более высокая точность подразумевается большим количеством показанных фигур.

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

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

Наиболее часто используемая система цифр - это Индусско-арабская система счисления.^[1] Два Индийские математики приписывают его развитие. Арьябхата из Кусумапура разработал обозначение мест в 5 веке и столетие спустя Брахмагупта представил символ для нуль. Система счисления и концепция нуля, разработанные индусами в Индии, постепенно распространились на другие окружающие регионы, такие как Аравия, из-за их коммерческой и военной деятельности с Индией. Затем индуистско-арабская система счисления распространилась в Европе вместе со многими другими научными знаниями, благодаря торговцам, торгующим и использующим стабильную простую систему счисления. Западный мир изменил их и назвал арабскими цифрами, как они узнали их от арабов. Следовательно, нынешняя западная система счисления является модифицированной версией индуистской системы счисления, разработанной в Индии. Он также очень похож на нотацию санскрит-деванагари, которая до сих пор используется в Индии и соседнем Непале.

Самая простая система счисления - это унарная система счисления, в котором каждый натуральное число представлен соответствующим количеством символов. Если символ / выбрано, например, тогда число семь будет представлено ///////. Счетные отметки представляют собой одну из таких систем, которые все еще широко используются. Унарная система полезна только для небольших чисел, хотя она играет важную роль в теоретическая информатика. Гамма-кодирование Элиаса, который обычно используется в Сжатие данных, выражает числа произвольного размера, используя унарный код для указания длины двоичного числа.

Унарная запись может быть сокращена путем введения различных символов для определенных новых значений. Очень часто это значения степени 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-адическая нотация, не путать с п-адические числа. Биективное основание 1 такое же, как унарное.

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

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

Например, в десятичный система (основание 10), цифра 4327 означает $(4 \times10 3) + (3 \times10 2) + (2 \times10 1) + (7 \times10 0)$ , отмечая, что $100 = 1$ .

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

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

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

В общем, цифры в базе б системы имеют вид:

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

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

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

{displaystyle {egin {array} {l | rrrrrrr} {ext {Position}} & 3 & 2 & 1 & 0 & -1 & -2 & cdots hline {ext {Weight}} & b ^ {3} & b ^ {2} & b ^ {1} & b ^ {0 } & b ^ {- 1} & b ^ {- 2} & cdots {ext {Digit}} & a_ {3} & a_ {2} & a_ {1} & a_ {0} & c_ {1} & c_ {2} & cdots hline {ext {Пример десятичного веса}} & 1000 & 100 & 10 & 1 & 0.1 & 0.01 & cdots {ext {Decimal example digit}} & 4 & 3 & 2 & 7 & 0 & 0 & cdots end {array}}}

Число имеет завершающее или повторяющееся расширение если и только если это рациональный; это не зависит от базы. Число, оканчивающееся на одной базе, может повторяться в другой (таким образом $0.3 10 = 0.0100110011001... 2$ ). Иррациональное число остается апериодическим (с бесконечным количеством неповторяющихся цифр) во всех целочисленных основаниях. Таким образом, например, в базе 2, $π = 3.1415926... 10$ можно записать как апериодическое 11.001001000011111 ...₂.

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

14/11 = 1.272727272727... = 1.27 или 321.3217878787878 ... = 321.32178.

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

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

В более общем плане используется смешанный корень обозначение (здесь написано прямой порядок байтов ) подобно ${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 соответственно. Цифра ниже порогового значения означает, что это самая старшая цифра, следовательно, конец числа. Пороговое значение зависит от позиции в номере. Например, если пороговое значение для первой цифры равно b (то есть 1), то a (то есть 0) отмечает конец числа (у него только одна цифра), поэтому в числах, состоящих из более чем одной цифры, диапазон составляет только b –9 (1–35), поэтому вес б₁ равно 35 вместо 36. Предположим, что пороговые значения для второй и третьей цифр равны c (2), тогда третья цифра имеет вес 34 × 35 = 1190, и у нас есть следующая последовательность:

a (0), ba (1), ca (2), .., 9a (35), bb (36), cb (37), .., 9b (70), bca (71), .., 99a (1260), bcb (1261) и др.

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

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

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

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

0.999... - каждый ненулевой завершающий десятичный разделитель имеет два равных представления

Источники

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

внешняя ссылка

СМИ, связанные с Системы счисления в Wikimedia Commons

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

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

[3] Fiete, I.R .; Сын, Х.С. (2007). «Нейросетевые модели производства, обучения и кодирования птичьего пения». In Squire, L .; Олбрайт, Т .; Блум, Ф .; Gage, F .; Спитцер, Н. Новая энциклопедия неврологии.

[1]

[2]

[3]