Сайт Марии Федотовой, ученицы ФМЛ №239 СПб

Материалы к докладу

ИНТЕРВАЛЬНЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

на 2-ой Международной конференции молодых учёных и студентов "Актуальные проблемы современной науки" (Самара 11-13 сентября 2001г., докладчик - Федотова М.В. , научный руководитель - Федотов В.П.)

СЛОВАРЬ ТЕРМИНОВ, ОТНОСЯЩИХСЯ К СИСТЕМАМ СЧИСЛЕНИЯ (в логической последовательности)

Классификация

Система счисления — способ записи чисел с помощью заданного набора специальных знаков (цифр).

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

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

Универсальная система счисления система счисления, которая позволяет записать любое вещественное число (конечной или бесконечной последовательностью цифр).

Неуниверсальная система счисления система счисления, которая позволяет записать лишь относительно небольшие числа, иногда только целые (либо наоборот, только меньшие единицы).

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

Основание системы счисления — отношение весов соседних разрядов основной позиционной системы счисления.

Неосновная система счисления позиционная система счисления, в которой соотношение весов соседних разрядов может меняться.

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

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

Информационная система счисления система счисления, в которой запись числа (в отличие от традиционной) состоит из единственной последовательности цифр. При этом каждая очередная цифра (бит) уточняет значение числа (его положение на оси). Пусть несколько первых цифр указывают на то, что интересующее нас число t содержится в некотором подмножестве U числовой оси, которое, в свою очередь, разбито на несколько непересекающихся подмножеств V1 , … , Vk . Тогда выбор одного из k возможных значений очередной цифры указывает на одно из этих подмножеств.

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

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

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

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

 

Примеры систем счисления,

которыми пользовалось или будет пользоваться человечество

 Непозиционные (неуниверсальные) системы счисления

Единичная система счисления. Простейшая, но абсолютно неудобная система счисления. Основана на единственной цифре – единице (палочке). Позволяет записывать только натуральные числа. Чтобы представить число в этой системе счисления нужно записать столько палочек, каково само число. Использовалась нецивилизованными племенами, потребности которых в счете, как правило, не выходили за рамки первого десятка. Чисто формально единичную систему счисления можно отнести к числу основных (с основанием 1). Но, в отличие от остальных основных систем счисления, считать ее позиционной можно лишь с очень сильной натяжкой, а универсальной она вообще не является (в ней нельзя представить ноль, дроби и отрицательные числа).

Римская система счисления. С помощью семи цифр – I=1 , V=5 , X=10 , L=50 , C=100 , D=500 , M=1000 – можно весьма успешно и довольно выразительно представлять натуральные числа в диапазоне до нескольких тысяч. Продолжает ограниченно использоваться для указания порядковых числительных (часов, столетий, номеров съездов или конференций и т.п.).

Славянская система счисления. Буквам старой славянской азбуки были присвоены цифровые значения: от 1 до 10, затем через 10 до 100 и через 100 до 1000. Используя не более трех букв можно было записать любое натуральное число от 1 до 1110.

 

Позиционные неуниверсальные системы счисления

(Форматы представления чисел в микрокалькуляторах и компьютерах)

Запись в формате с фиксированной запятой использовалась в первых электронно-вычислительных машинах (в частности, в советских «Урал-1»). Она позволяет представить числа, абсолютная величина которых не превосходит единицы, и притом лишь те из них, которые имеют данное фиксированное число двоичных или двоично-десятичных разрядов.

Нормализованная (инженерная, научная) форма записи чисел используется сейчас большинством микрокалькуляторов, компьютеров и иных вычислительных устройств. Запись числа состоит из двух частей – мантиссы и порядка, каждая из которых имеет свой собственный знак и строго определенное число десятичных (двоичных или иных) разрядов. Диапазон для мантиссы определен одним из двух правил. Чаще всего, она меньше единицы, но больше единицы следующего младшего разряда соответствующей системы счисления (как правило, десятичной или двоичной). Противоположное правило: мантисса больше единицы, но меньше единицы следующего старшего разряда (одновременно может действовать только одно из этих двух правил, но никак не оба сразу).

Байтовая система счисления.  Содержимое файла в известном смысле не зависит от его типа и предназначения. С точки зрения внутренней структуры файл представляет собой конечную последовательность байтов. Каждый байт – это 8 битов, которые в двоичной системе счисления можно прочитать как целое число от 0 до 255. Каждое такое число (код) можно рассматривать как цифру в системе счисления с основанием 256. Так как файл представляет собой единую последовательность байтов (и в отличие от традиционной записи числа не разделен на целую и дробную части), то возможны два варианта прочтения файла, как числа. Во-первых, можно считать файл целым числом. Во-вторых, можно, напротив, считать целую часть нулевой (как и в записи в формате с фиксированной запятой). Каждый из этих двух подходов имеет свои плюсы и минусы. Явное преимущество второго состоит в том, что при записи в конец файла его числовое значение будет меняться в некотором смысле не очень значительно. Например, в случае текстовых файлов и при условии, что коды букв алфавита идут в порядке возрастания, именно во втором случае числовые значения файлов будут согласованы с положением этих текстов в словаре (в алфавитном порядке), тогда как в первом случае больший номер достанется файлу с более длинным текстом.

 

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

Двоичная система счисления. В настоящий момент – наиболее употребительная в информатике, вычислительной технике и смежных отраслях система счисления. Использует две цифры – 0 и 1, а также символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной части.

Троичная система счисления. Использует три цифры – 0, 1 и 2, а также символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. В более далекой перспективе просматривается возможность перехода компьютерной отрасли на троичную систему счисления, так как она позволяет более эффективно сворачивать числовую информацию (как показал Джон фон Нейман, это следует из того, что число 3 ближе, чем 2, к основанию e натуральных логарифмов).

Уравновешенная троичная система счисления. В отличие от обычной троичной системы счисления, вместо цифры 2 использует другую цифру – со значением –1. Это позволяет отказаться от особого обозначения для знака числа, так как знак числа определяется знаком его первой цифры. Кроме того, для этих цифр упрощаются таблицы сложения и умножения. Для удобства и большей выразительности вместо цифр чаще пишутся буквы:  -1=N (negative), 0=O (внешнее сходство), 1=P (positive). Так как получились три подряд идущие буквы алфавита, то переход от значения цифры к ее коду (обозначению) или обратно осуществляется одной общей арифметической операцией (не требует логических операций и анализа). Среди первых электронных вычислительных машин была и московская «Сетунь», арифметическое устройство которой базировалось на таком представлении чисел.

Система счисления с основанием 4. Использует четыре цифры – 0, 1, 2 и 3, а также символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. О практическом использовании этой системы счисления пока ничего не известно. Однако перспектива есть по двум причинам. Во-первых, аналогичная 8 и 16 связь с двоичной системой, что позволяет легко переводить числа из любой из этих систем в любую другую. Во-вторых, наличие именно 4 базовых аминокислот, ставших своеобразным алфавитом быстро развивающейся генетики.

Система счисления с основанием 7.  Семь дней недели, семь нот, семь чудес Света, семь цветов радуги (хотя нормальный глаз видит их там только шесть, не разделяя оттенков синего и голубого) и многочисленные другие примеры указывают на то, что и это число служило разрядной единицей. А название праздника «пятидесятница», как и пришедший из древнееврейского языка «юбилей» – это вовсе не половина от ста, а число, следующее за 49 – второй разрядной единицей системы счисления с основанием 7.

Восьмеричная система счисления. Использует восемь цифр – 0, 1, 2, 3, 4, 5, 6, и 7, а также символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Широко использовалась в программировании в 1950-70-ые гг. К настоящему времени практически полностью вытеснена шестнадцатеричной системой счисления, однако функции перевода числа из десятичной системы в восьмеричную и обратно сохраняются в микрокалькуляторах и многих языках программирования.

Десятичная система счисления. Использует десять обычных цифр – 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, а также символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Существует массовое заблуждение, будто именно десятичная система счисления является наиболее употребительным способом записи чисел. Между тем, более внимательный анализ правил чтения и записи чисел приводит к другому выводу: система счисления, которой мы обычно пользуемся, фактически является двойной, так как имеет основания – 10 и 1000. В частности, в русском языке известны названия только для первых семи разрядов десятичной системы счисления ( 1 – единица, 10 – десяток, 100 – сотня, 1000 – тысяча, 10000 – тьма, 100000 – легион, 1000000 – миллион ), но предпоследние два из них (легион  и тьма) давно вышли из употребления, а соседние с ними (миллион и тысяча) – названия классов, а не только разрядов. Итак, фактически в русском языке остались лишь два самостоятельных названия для десятичных разрядов: десяток и сотня. В других языках – аналогичная ситуация.

Одиннадцатеричная система счисления употребляется в языке для устного счета народом маори – коренным населением Новой Зеландии.
Двенадцатеричная система счисления. На ее широкое использование в прошлом явно указывают названия числительных во многих языках, а также сохранившиеся в ряде стран способы отсчета времени, денег и соотношения между некоторыми единицами измерения. Год состоит из 12 месяцев, а половина суток состоит из 12 часов. В русском языке счет часто идет дюжинами, чуть реже гроссами (по 144=122), но в старину использовалось и слово для 1728=123. В английском языке есть особые (а не образованные по общему правилу) слова eleven (11) и twelve (12). Английский фунт состоит из 12 шиллингов.

Шестнадцатеричная система счисления. Использует шестнадцать цифр – 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9 в их обычном смысле, а затем A=10, B=11 , C=12 , D=13 , E=14 , F=15 . Также использует символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Внедрена американской корпорацией IBM. Широко используется в программировании для IBM-совместимых компьютеров. С другой стороны, в некоторых языках сохранились и следы использования этой системы счисления в прошлом. Например, в романских языках (испанском, французском и др.) числительные от 11 до 16 образуются по одному правилу, а от 17 до 19 – по другому. А в русском языке известен пуд, равный 16 килограммам.

Уравновешенная девятнадцатеричная система счисления. Использует девятнадцать цифр – 0, ±1, ±2, ±3, ±4, ±5, ±6, ±7, ±8 и ±9, а также символы «+» и «–» для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Так как запись знаков внутри цифр достаточно неудобна, то плюс при положительных цифрах не пишут вообще, а отрицательные цифры вместо минуса надчеркивают. При таком подходе таблицы сложения и умножения в этой системе счисления повторяют те же таблицы для обычной десятичной системы, но с учетом знаков цифр (в частности, сложение заменяется вычитанием, а при умножении знак произведения зависит от четности числа отрицательных множителей). Так как 192=361 , то двух таких цифр достаточно для указания 360 направлений, измеряемых целым числом градусов.

Двадцатеричная система счисления. Во французском языке способ образования числительных от 80 до 99 явно указывает на употребление этой системы счисления в прошлом. Например, quatre-vingt-dix (90) в буквальном переводе означает «четыре по двадцать и десять». Не столь сильно выражены следы ее использования в других языках. Однако в большинстве европейских языков, как и в русском, числительные до 20 и после 20 образуются по разным правилам. В русском языке можно заметить также разные правила образования числительных, кратных ста, до 400=202 и после. Английский шиллинг состоит из 20 пенсов.

Система счисления с основанием 32. О практическом использовании этой системы счисления пока ничего не известно. Однако перспектива есть по двум причинам. Во-первых, аналогичная 8 и 16 связь с двоичной системой, что позволяет легко переводить числа из любой из этих систем в любую другую. Во-вторых, в русском языке (если не различать «е» и «ё») как раз 32 буквы.

Система счисления с основанием 36. Так как 36=10+26, то 36 –  последнее основание, до которого можно «дотянуть» обозначение цифр буквами латинского алфавита по правилу, действующему для шестнадцатеричной системы счисления.

Система счисления с основанием 40. Совершенно особое слово «сорок» и часто используемое в русском языке выражение «сорок сороков» явно указывают на употребление в прошлом и этой системы счисления. Числительные, обозначающие десятки, до 40 и после 40 образуются по разным правилам. Это же число 40 является соотношением между русскими единицами веса – пудом (16кг) и фунтом (400г).

Шестидесятеричная система счисления. Ведет свою историю еще с Древнего Египта, то есть с IV тысячелетия до нашей эры. Ее появление вызвано сочетанием двух причин. Во-первых, при счете на пальцах можно фиксировать до 60 различных положений (косточек или суставов между ними). Во-вторых, 60 лет – наименьшее общее кратное периодов обращения вокруг Солнца всех планет Солнечной системы, доступных для наблюдения без оптических приборов. Поэтому именно 60 лет были периодом, на который составлялись древние астрономические календари. Шестидесятилетний цикл летоисчисления широко известен как восточный календарь (в двух вариантах – японском и китайском). Шестидесятеричная система счисления до сих пор сохранилась в измерении углов и времени. Угол равностороннего треугольника (а в древности за основу брался именно он, так как его построить легче, чем прямой или развернутый) делится на 60 градусов. Градус, как и час, делится на 60 минут, а минута – на 60 секунд (и не важно, о чем здесь идет речь – о времени или углах). На шестидесятеричную систему счисления указывает и способ образования числительных от 60 до 79 во французском языке. Например, soixante-dix-nef (79) можно перевести как «шестьдесят и девятнадцать».

Тысячная система счисления должна была бы использовать тысячу различных цифр. Наверное, такое возможно в Китае, имеющем тысячи иероглифов. Но подавляющее большинство европейцев не имеет навыка удерживать в голове и различать столь большое количество различных знаков. И тем не менее, именно тысячная система счисления лежит в основе образования числительных во всех европейских языках. А вместо тысячи цифр используется их представление в десятичной системе, что в конечном счете приводит к двойной системе счисления: десятично-тысячной. Чтобы не путать разряды двух разных систем счисления, разряды тысячной системы счисления называют классами. Первые из них – единица, тысяча, миллион, миллиард. Так как большие числа употребляются сравнительно редко, то принятые в разных языках названия для последующих классов оказались в конфликте друг с другом. В одних языках (включая русский) слово «биллион» используется для обозначения 1000 миллиардов, а в других – как синоним самого миллиарда. Но зато дальше «полная ясность»: 1000 биллионов называется триллионом, 1000 триллионов называется квадриллионом, 1000 квадриллионов называется квинтиллионом, 1000 квинтиллионов называется секстиллионом, 1000 секстиллионов называется септиллионом, 1000 септиллионов называется окталлионом, 1000 окталлионов называется ноналлионом, 1000 ноналлионов называется дециллионом, 1000 дециллионов называется ундециллионом и т.д.

 

Двойные позиционные системы счисления

Двоично-восьмеричная система счисления. Если двоичную запись числа разбить на триады (тройки цифр) и вставить между ними пробелы, то получится двоично-восьмеричное представление числа. Так как 23=8 , то после замены каждой триады на восьмеричную цифру, равную значению этой триады, получится представление числа в восьмеричной системе счисления. Тем самым, двоично-восьмеричная система счисления становится промежуточным этапом перевода чисел из двоичной системы в восьмеричную и обратно. Простота алгоритма перевода, а также близость чисел 8 и 10 послужили причинами широкого распространения восьмеричной и двоично-восьмеричной систем счисления в программировании в 1950-70-ые годы.

Двоично-десятичная система счисления. Десятичные цифры от 0 до 9 заменяются представляющими их двоичными тетрадами:  0=0000 , 1=0001 , 2=0010 , 3=0011 , 4=0100 , 5=0101 , 6=0110 , 7=0111 , 8=1000 и 9=1001 . Такая запись очень часто используется как промежуточный этап перевода числа из десятичной системы в двоичную или обратно. Так как 10 не является точной степенью 2, то используются не все 16 тетрад, а алгоритмы арифметических операций над многозначными числами здесь более сложны, чем в основных системах счисления. И тем не менее, двоично-десятичная система счисления применяется даже на этом уровне во многих микрокалькуляторах и некоторых компьютерах (в частности, «Ямаха» стандарта MSX).

Двоично-шестнадцатеричная система счисления. Так как 24=16 , то двоично-шестнадцатеричная система счисления используется аналогично двоично-восьмеричной, как промежуточный этап при переводе чисел из двоичной системы в шестнадцатеричную и обратно.

Десятично-тысячная система счисления. Система счисления, которой мы обычно пользуемся, фактически является двойной и имеет основания 10 и 1000. Это проявляется как в записи «длинных» чисел с пробелами (в англоязычном формате – запятыми) между классами (тройками разрядов), так и в правилах чтения. Число читается по классам (т.е. разрядам тысячной системы счисления) и лишь внутри класса – по десятичным разрядам.

 

Более сложные позиционные системы счисления

Дата – время. Традиционный способ представления моментов и больших промежутков времени сочетает использование нескольких разных единиц измерения. При переходе от тысячелетий к векам, от них к десятилетиям, а затем к годам, вес разряда в записи даты изменяется в 10 раз. Год состоит из 12 месяцев, месяц – из 4 недель, неделя – из 7 суток. Сутки состоят из 24 часов, час – из 60 минут, а минута – из 60 секунд. Более мелкие интервалы времени, чаще всего, измеряют десятыми, сотыми, тысячными и т.д. долями секунды (хотя известно и об употреблении шестидесятеричного деления секунды и ее последующих долей). Таким образом, мы имеем здесь дело с системой счисления, сочетающей в себе сразу шесть различных оснований: 4, 7, 10, 12, 24 и 60.

Вавилонская клинописная система счисления использовалась еще на заре человеческой цивилизации – в III тысячелетии до нашей эры. Она сочетала три основания – 1, 10 и 60. Для чисел от 1 до 9 использовались вертикальные клинья (палочки), как в единичной системе счисления. Для сокращения записи использовался угловой клин, заменявший 10 вертикальных. Угловой клин можно было повторять до 5 раз, а вместо 6 угловых клиньев вновь писался вертикальный, но перед ними. Тем самым наборы от 1 до 9 вертикальных и от 1 до 5 угловых клиньев превращались в цифры (десятичные и шестидесятеричные). Еще один специальный символ (аналог нуля) использовался для указания пропуска пустых разрядов, т.е. для обозначения границы между шестидесятеричными классами, но лишь  в тех случаях, когда без него запись числа могла бы стать двусмысленной.

Индейцы племени майя пользовались весьма замысловатой системой счисления. В ней единица второго разряда равна 5, единица третьего – 4 единицам второго разряда, четвертого – 18 единицам третьего, а единица каждого последующего разряда – 20 единицам предыдущего.

Факториальная система счисления известна специалистам в теории чисел. В ней единица второго разряда равна 2, единица третьего – 3 единицам второго разряда, четвертого – 4 единицам третьего и т.д.: единица k-ого разряда равна k единицам предыдущего и имеет вес k! . 

Фибоначчиевская система счисления известна еще более узкому кругу специалистов. В ней вес k-ого разряда равен k-ому числу из последовательности Фибоначчи:  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … , в которой каждый очередной член равен сумме двух предыдущих. Это позволяет не только использовать всего 2 цифры – 0 и 1 , но и дополнительно потребовать, чтобы нигде в записи числа две единицы не стояли рядом. Так как в итоге единицы встречаются в записи числа сравнительно редко, то это существенно облегчает вычисления.

 

На предыдущую страницу

Сайт управляется системой uCoz