Системы счисления и представление чисел

Введение

Обозначения для представления чисел, представление чисел с помощью символов

Система счисления — это система записи для представления чисел, то есть математическое обозначение для представления чисел заданного множества с использованием цифр или других символов последовательным образом. Одна и та же последовательность символов может представлять разные числа в разных системах счисления. Например, "11" представляет число одиннадцать в десятичной системе счисления (наиболее распространенная система в мире сегодня), число три в двоичной системе счисления (используется в современных компьютерах) и число два в унарной системе счисления (используется для подсчета). Число, которое представляет данная запись, называется его значением. Не все системы счисления могут представлять один и тот же набор чисел; например, римские цифры не могут представлять число ноль. В идеале, система счисления должна:
Представлять полезный набор чисел (например, все целые числа или рациональные числа)
Предоставлять каждому представленному числу уникальное представление (или, по крайней мере, стандартное представление)
Отражать алгебраическую и арифметическую структуру чисел. Например, обычное десятичное представление предоставляет каждому ненулевому натуральному числу уникальное представление в виде конечной последовательности цифр, начинающейся с ненулевой цифры. Системы счисления иногда называют системами чисел, но это название неоднозначно, поскольку оно может относиться к различным системам чисел, таким как система действительных чисел, система комплексных чисел, система p-адических чисел и т. д. Однако такие системы не являются темой данной статьи.

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

Наиболее часто используемая система счисления — десятичная. Индийским математикам приписывают разработку целочисленной версии, индусско-арабской системы счисления. Арьябхата из Кусумапуры разработал позиционное обозначение в V веке, а столетие спустя Брахмагупта ввел символ нуля. Система медленно распространялась в другие окружающие регионы, такие как Аравия, благодаря их торговой и военной деятельности с Индией. Математики Ближнего Востока расширили систему, включив отрицательные степени 10 (дроби), как это зафиксировано в трактате сирийского математика Абу’ль Хасана аль-Уклидиси в 952–953 годах, а десятичная точка была введена Синдом ибн Али, который также написал самый ранний трактат об арабских цифрах. Индусско-арабская система счисления затем распространилась в Европу благодаря торговле, и цифры, используемые в Европе, называются арабскими цифрами, поскольку они узнали их от арабов. Самая простая система счисления — унитарная, в которой каждое натуральное число представлено соответствующим количеством символов. Если, например, выбрать символ |, то число семь будет представлено как |||||||. Такие системы, как счетные черты, до сих пор широко используются. Унитарная система полезна только для небольших чисел, хотя она играет важную роль в теоретической информатике. Кодирование Элиаса гамма, которое обычно используется в сжатии данных, выражает числа произвольного размера, используя унитарный код для указания длины двоичного числа. Унитарную нотацию можно сократить, введя различные символы для определенных новых значений. Очень часто эти значения являются степенями 10; так, например, если / означает один, − — десять, а + — сто, то число 304 можно компактно представить как ++++///, а число 123 — как +++/|||. Это называется знаково-значительной системой счисления. Древнеегипетская система счисления была такого типа, а римская система счисления — модификацией этой идеи. Еще более полезны системы, которые используют специальные сокращения для повторения символов; например, используя первые девять букв алфавита для этих сокращений, где A означает «одно вхождение», B — «два вхождения» и так далее, можно записать 304 как C+D/. Эта система используется при записи китайских цифр и других восточноазиатских цифр, основанных на китайском языке. Числовая система английского языка также относится к этому типу («триста [и] четыре»), как и системы других разговорных языков, независимо от используемых ими систем письменности. Однако многие языки используют смеси оснований и других особенностей; например, 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, 1, 2, 3, 4, 5, 6, 7, 8, 9, и позиция цифры используется для обозначения степени десятки, на которую она должна быть умножена, как в 304 или, точнее, 3 × 10² + 0 × 10¹ + 4 × 10⁰. Нуль, который не нужен в других системах, здесь имеет решающее значение, чтобы иметь возможность «пропускать» степень. Индусско-арабская система счисления, возникшая в Индии и используемая сейчас во всем мире, является позиционной системой с десятичным основанием. Арифметика в позиционных системах намного проще, чем в более ранних аддитивных системах; кроме того, аддитивным системам требуется большое количество различных символов для различных степеней 10, а позиционной системе требуется всего десять различных символов (при условии, что она использует основание 10). Позиционная десятичная система в настоящее время повсеместно используется в письменности. Основание 1000 также используется (хотя и не повсеместно), группируя цифры и рассматривая последовательность из трех десятичных цифр как одну цифру. Это значение общей нотации 1,000,234,567, используемой для очень больших чисел. В компьютерах основные системы счисления основаны на позиционной системе в основании 2 (двоичная система счисления) с двумя двоичными цифрами: 0 и 1. Обычно используются позиционные системы, полученные группировкой двоичных цифр по три (восьмеричная система счисления) или четыре (шестнадцатеричная система счисления). Для очень больших целых чисел используются основания 232 или 264 (группировка двоичных цифр по 32 или 64, длина машинного слова), как, например, в GMP. В определенных биологических системах используется унитарная система кодирования. Унитарные числа используются в нейронных цепях, ответственных за производство птичьих песен. Ядро в мозге певчих птиц, которое играет роль как в обучении, так и в производстве птичьих песен, — это 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 совпадает с унитарной.

The most commonly used system of numerals is decimal. Indian mathematicians are credited with developing the integer version, the Hindu–Arabic numeral system. Aryabhata of Kusumapura developed the place value notation in the 5th century and a century later Brahmagupta introduced the symbol for zero. The system slowly spread to other surrounding regions like Arabia due to their commercial and military activities with India. Middle Eastern mathematicians extended the system to include negative powers of 10 (fractions), as recorded in a treatise by Syrian mathematician Abu'l Hasan al Uqlidisi in 952–953, and the decimal point notation was introduced by Sind ibn Ali, who also wrote the earliest treatise on Arabic numerals. The Hindu–Arabic numeral system then spread to Europe due to merchants trading, and the digits used in Europe are called Arabic numerals, as they learned them from the Arabs. The simplest numeral system is the unary numeral system, in which every natural number is represented by a corresponding number of symbols. If the symbol is chosen, for example, then the number seven would be represented by Tally marks represent one such system still in common use. The unary system is only useful for small numbers, although it plays an important role in theoretical computer science. Elias gamma coding, which is commonly used in data compression, expresses arbitrary sized numbers by using unary to indicate the length of a binary numeral. The unary notation can be abbreviated by introducing different symbols for certain new values. Very commonly, these values are powers of 10; so for instance, if / stands for one, − for ten and + for 100, then the number 304 can be compactly represented as and the number 123 as without any need for zero. This is called sign value notation. The ancient Egyptian numeral system was of this type, and the Roman numeral system was a modification of this idea. More useful still are systems which employ special abbreviations for repetitions of symbols; for example, using the first nine letters of the alphabet for these abbreviations, with A standing for "one occurrence", B "two occurrences", and so on, one could then write C+ D/ for the number 304. This system is used when writing Chinese numerals and other East Asian numerals based on Chinese. The number system of the English language is of this type ("three hundred [and] four"), as are those of other spoken languages, regardless of what written systems they have adopted. However, many languages use mixtures of bases, and other features, for instance 79 in French is soixante dix neuf (60 + 10 + 9) and in Welsh is pedwar ar bymtheg a thrigain (4 + (5 + 10) + (3 × 20)) or (somewhat archaic) pedwar ugain namyn un (4 × 20 − 1). In English, one could say "four score less one", as in the famous Gettysburg Address representing "87 years ago" as "four score and seven years ago". More elegant is a positional system, also known as place value notation. Again working in base 10, ten different digits 0, , 9 are used and the position of a digit is used to signify the power of ten that the digit is to be multiplied with, as in or more precisely 3×102 + 0×101 + 4×100. Zero, which is not needed in the other systems, is of crucial importance here, in order to be able to "skip" a power. The Hindu–Arabic numeral system, which originated in India and is now used throughout the world, is a positional base 10 system. Arithmetic is much easier in positional systems than in the earlier additive ones; furthermore, additive systems need a large number of different symbols for the different powers of 10; a positional system needs only ten different symbols (assuming that it uses base 10). The positional decimal system is presently universally used in human writing. The base 1000 is also used (albeit not universally), by grouping the digits and considering a sequence of three decimal digits as a single digit. This is the meaning of the common notation 1,000,234,567 used for very large numbers. In computers, the main numeral systems are based on the positional system in base 2 (binary numeral system), with two binary digits, 0 and 1. Positional systems obtained by grouping binary digits by three (octal numeral system) or four (hexadecimal numeral system) are commonly used. For very large integers, bases 232 or 264 (grouping binary digits by 32 or 64, the length of the machine word) are used, as, for example, in GMP. In certain biological systems, the unary coding system is employed. Unary numerals used in the neural circuits responsible for birdsong production. The nucleus in the brain of the songbirds that plays a part in both the learning and the production of bird song is the HVC (high vocal center). The command signals for different notes in the birdsong emanate from different points in the HVC. This coding works as space coding which is an efficient strategy for biological circuits due to its inherent simplicity and robustness. The numerals used when writing numbers with digits or symbols can be divided into two types that might be called the arithmetic numerals (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) and the geometric numerals (1, 10, 100, 1000, 10000 ), respectively. The sign value systems use only the geometric numerals and the positional systems use only the arithmetic numerals. A sign value system does not need arithmetic numerals because they are made by repetition (except for the Ionic system), and a positional system does not need geometric numerals because they are made by position. However, the spoken language uses both arithmetic and geometric numerals. In some areas of computer science, a modified base k positional system is used, called bijective numeration, with digits 1, 2, , k (k ≥ 1), and zero being represented by an empty string. This establishes a bijection between the set of all such digit strings and the set of non negative integers, avoiding the non uniqueness caused by leading zeros. Bijective base k numeration is also called k adic notation, not to be confused with p adic numbers. Bijective base 1 is the same as unary.