Мы наконец разобрались с целыми числами, которые оказались более интересными, чем многие считают. Но сегодня они нам снова понадобятся. Правда для уже как средство, а не как объект для изучения. Кроме того, сегодня мы сегодня будем заниматься машинным, но не аппаратным представлением чисел, в отличии от предыдущих статей. То есть, одной из интерпретаций наборов бит.
В обычной жизни нам часто встречаются не только целые, но и дробные числа или, сокращенно, дроби. Причем чаще дроби не столько обыкновенные, сколько десятичные. Впрочем, десятичная дробь это просто несколько иная форма записи записи, так как десятичная дробь это обыкновенная дробь с знаменателем равным 10.
Нас же сегодня будут интересовать не просто дроби, а рациональные числа. Рациональное число является обыкновенной дробью у которой числитель является целым числом, а знаменатель числом натуральным. Всем известное определение из курса школьной математики. Что такое целые числа мы уже знаем. Целое число может быть положительным, отрицательным, равным 0. Натуральные числа это подмножество целых чисел из которого исключены отрицательные числа и 0.
Рассмотренные ранее беззнаковые целые числа не являются натуральными, так как могут равняться 0.
Знак числителя (целого числа) дроби, является знаком всей дроби. То, что знаменатель является натуральным числом, исключает конфликты знаков. Иначе мы бы считали положительными дроби имеющие числитель и знаменатель одного знака, а отрицательными имеющие разные знаки. Кроме того, исключается "аварийная" ситуация с равным 0 знаменателем.
Есть небольшая неоднозначность в определении натуральных чисел, причем и среди математиков. Эта неоднозначность касается вопроса, включать ли 0 в набор натуральных чисел. Международный стандарт
ISO 80000-2:2009(E)
определяет как множество включающее 0 (обозначается N), так и множество без 0 (обозначается N*). В большинстве русскоязычных (включая советские) источников множество натуральных чисел не включает 0.
Представление чисел в формате с плавающей запятой, научном, экспоненциальном, виде, будет рассматриваться в следующей статье.
Когда ЭВМ не может быть точной
Существуют рациональные числа, которые не могут быть представлены абсолютно точно ни в десятичной системе счисления, ни в двоичной. И формат чисел с плавающей запятой, который мы будем рассматривать в следующей статье, ни чем нам не поможет. Простейшим примером такого рационального числа является дробь
1/3 = 0,33333333333333333(3)
Последняя цифра в скобках обозначает "и 3 в периоде". То есть, эта дробь, записанная в десятичном виде, является бесконечной. Бесконечную дробь невозможно представить абсолютно точно. Конечно, чем больше записано цифр после запятой, тем меньше погрешность. Но эта погрешность никогда не станет равной 0.
При этом запись в виде обыкновенной дроби является точной.
И это принципиальная проблема, которую нужно как то решать. Причем для большинства процессоров готовых средств нет. Если нужно считать точно, приходится выкручиваться программистам. Вот мы сегодня и посмотрим, как можно выкрутиться.
Представление рациональных чисел в виде пары целых
Такое представление напрашивается само собой из определения обыкновенной дроби. Нам нужно целое число для хранения числителя и беззнаковое для знаменателя. Разрядность чисел сегодня для нас не имеет значения.
Однако, пара чисел, со знаком и без знака, не совсем точно соответствует определению рационального числа, так как не исключает равенства знаменателя нулю. А значит, нам потребуется дополнительный программный контроль. Мы даже можем использовать для хранения знаменателя целые числа со знаком, для однообразия, если расширим программный контроль до проверки не только равенства нулю, но и знака знаменателя.
Арифметические операции с таким представлением рациональных чисел будут выполняться по всем известным формулам. Причем работать мы будем только с целыми числами. А это не только быстрее, но и является важным преимуществом для процессоров не имеющих команд работы с числами с плавающей запятой.
В языке С рациональные числа могут быть представлены в виде структуры
На аппаратном, машинном, уровне такая структура будет соответствовать паре слов (байт, полуслов, двойных слов, и т.д.). Поэтому остается полностью применимым все, что мы ранее рассматривали. Но появляются и свои тонкости.
Сложение и вычитание
При ручном счете, например, на листе бумаги, мы можем воспользоваться способностями своего мозга и, хоть и только в некоторых относительно простых случаях, легко привести участвующие в сложении или вычитании дроби к общему знаменателю. В математике это называется нахождением наименьшего общего кратного (НОК).
Однако, нахождение НОК не такая простая операция, в общем случае. Я не буду погружаться в математику, это не тема статьи. Но вычисление НОК очень хотелось бы избежать. Как минимум, для экономии времени. Простейшим, но очень далеким от идеала, способом является
Аналогично и для вычитания, поэтому отдельно его рассматривать не будем.
Однако, такая экономия времени и сил, как всегда, имеет свою темную сторону. Скоро мы это рассмотрим.
Умножение и деление
Тут все просто, как в школьном учебнике, и отдельно рассматривать особого смысла нет. Но все таки, даже отсутствие особенностей не избавляет нас от сложностей. Вот ими сейчас и займемся.
Нормализация
Мы лихо использовали умножение при приведении дробей к общему знаменателю. И не задумывались, что умножение и деление тоже включают в себя умножение числителей и знаменателей. Что это значит? А это значит, что при выполнении арифметических операций у нас начинают неконтролируемо расти числитель и знаменатель.
Это может быть незаметно при выполнении пары операций. Но в длинных цепочках вычислений уже становится критичным. Да и при выводе на печать как то некрасиво получается. Например,
3565 / 10695 вместо 1 /3
Но красота не так страшно, как возникновение переполнения разрядной сетки. А значит, нам нужно, как минимум, периодически, выполнять нормализацию нашего рационального числа. Нормализация сводится к нахождению наибольшего общего делителя (НОД) числителя и знаменателя. На найденный НОД нам потребуется разделить числитель и знаменатель нашей дроби, что не изменит ее значения, но позволит избегать переполнения.
Нахождение НОД тоже является далеко не самой простой и быстрой операцией. Существуют различные алгоритмы вычисления НОД, которые мы не будем рассматривать, так как статья не о математике. Поэтому нужно как то минимизировать эту медленную операцию.
Увы, полностью избежать ее мы не можем. Но можно выполнять нормализацию только при возникновении переполнения при выполнении операции с рациональными числами. Это позволит свести затраты времени к минимуму. Кроме того, нормализация потребуется перед выводом рационально числа, дроби, на печать.
Десятичные дроби, или числа с фиксированной точкой
Иногда можно закрыть глаза не неточное представление рационального числа в виде десятичной дроби, но важно максимально быстрое выполнение вычислений, причем в процессоре нет аппаратной поддержки работы с десятичными дробями (в формате плавающей запятой). Причем диапазон таких десятичных дробей в программе не является слишком большим.
Например, достаточным является точность в три цифры после запятой. Другим примером является представление денег в финансовых программах в рублях и копейках. По сути, копейки это две цифры после запятой при представлении денег в рублях.
Если для финансовых вычислений высокая скорость может быть не столь важна, то для некоторых применений она оказывается важнее высокой точности. При этом использовать мощные CISC процессоры может быть нецелесообразным. Что же делать?
На самом деле, уверен, многие читатели уже знаю ответ. Мы можем работать с десятичными дробями как с целыми числами. При этом местоположение десятичной точки (запятой) мы определяем вне определения собственно целого числа, условно. Например, мы можем считать, что две последние цифры целого числа являются дробной частью.
Таким образом, целое число 123456 будет являться эквивалентом числа 1234,56. Обратите внимание, что двоичное представление числа при этом не изменяется
123456 = 011110001001000000
1234,56 = 011110001001000000
1,23456 = 011110001001000000
Меняется только наша интерпретация семантики этого битового набора. Я говорил о этом в первой статье цикла, мы видели это во второй статье, и вот столкнулись с этим снова.
Глядя на число, как набор бит, мы не в состоянии сказать, где будет располагаться запятая. Эта информация хранится отдельно. Причем не обязательно где то в программе, вполне возможно, только в голове программиста.
Может показаться, что такое представление десятичных дробей радикально отличается от рассмотренного ранее для обыкновенных дробей. Однако, это совсем не так! Это тот же самый формат! Просто теперь у нас знаменатель является степенью 10. И мы можем хранить, или подразумевать, показатель степени, а не собственно знаменатель. А если знаменатель одинаков для всех чисел в программе, его можно просто не хранить отдельно.
Однако, если в программе могут использоваться числа с разным положением "виртуальной" запятой, нельзя забывать, что может потребоваться их приведение к общему знаменателю.
В остальном, такое представление десятичных дробей, в виде чисел с фиксированной точкой, целых чисел, особенностей не имеет. И в программах используется частенько.
Когда прикладная область требует "странного"
Увы, в нашем несовершенном мире бал правят специалисты в предметных областях :) А значит, их требования приходится учитывать и в языках программирования, и в прикладных программах, и в библиотеках функций, которыми пользуются прикладные программисты. И эти требования могут быть очень странными, с точки зрения программиста-математика.
Например, может требоваться, что бы рациональные числа, представляемые в виде десятичных дробей, обязательно имели определенное число цифр как в числе в целом, так и в дробной части. Если опять вспомнить финансовые программы, то может требоваться обязательно 5 цифр до десятичной точки, и две цифры после нее. И это не считая, например, размещением знака числа после всех его цифр.
Знак числа мы трогать не будем, а вот с тами жестким форматом представления чисел, с точки зрения прикладной программы, попробуем разобраться.
Но сначала посмотрим, как такие требования могут быть представлены в языках программирования. Да, я знаю, что выбрал для примера архаичные языки. И начну я с языка PL/1. В этом языке переменная может быть описана так
DECLARE VAR FIXED DECIMAL(7,2);
Переменная VAR представлена семью десятичными цифрами, две из которых располагаются справа от десятичной точки.
В PL/1 есть и тип FIXED BINARY, с которым проблем не возникает, но изучение PL/1 не является целью статьи.
Вторым языком я выбрал COBOL. В этом языке аналогичная переменная может быть описана так
77 VAR PIC 9(5)V9(2).
77 означает, что это переменная, которая не может быть структурой. То есть, обычная ординарная переменная. И эта переменная хранит число без знака из 5 десятичных цифр, запятой, двух десятичных цифр после запятой.
Такая функциональность в языках программирования появилась по требования прикладных областей, задачи которых решались на ЭВМ. А раз есть требования и функционал, значит нам необходимо обеспечить реализацию. Пусть и не совсем на аппаратном уровне, достаточно на уровне среды времени выполнения языка.
Казалось бы, какая сложность обеспечить заданное количество цифр? Достаточно обеспечить соответствующую разрядность и проблема решена. Не так просто. Давайте посмотрим, сколько бит потребуется для представления числа с 5 цифрами до запятой и двумя после. В формате с фиксированной точкой это будет соответствовать 7 цифрам.
Для представления числа 9 999 999 достаточно 3 байт (24 бита), если число не имеет знака
9 999 999 = 1001 1000 1001 0110 0111 1111
Вы все еще уверены, что проблема решена? Тогда посмотрите, что будет, если к этому числу прибавить 1. С точки зрения требований прикладного специалиста должно быть зафиксировано переполнение, то есть, ошибка. Но с точки зрения двоичного процессора ЭВМ никакого переполнения не возникает. Ведь 24 бит достаточно для хранения числа 16777215.
А это проблема. Мы не можем использовать формирование флагов признаков результата командами процессора. Мы должны после каждой операции выполняться сравнение результата с граничным значением. Это возможно, однако, есть и еще один вариант.
Но сначала давайте задумаемся, в чем причина возникновения этой проблемы? А причина в том, что для представления десятичной цифры требуется не целое число бит. Но дробного количества бит в ЭВМ не бывает. Однако...
Давайте вспомним о существовании преставления целых чисел в формате BCD. Упакованных или нет, нам сейчас не важно. Важен только принцип. Мы можем использовать BCD кодирование и соответствующие машинные команды для обработки чисел как совокупности именно десятичных, а не двоичных чисел.
Обязательно ли использовать BCD представление для чисел с фиксированной запятой и жестко заданным количеством цифр? Конечно, не обязательно. Не секрет, что любая задача может быть решена, и не только на ЭВМ, самыми разными способами. Но все таки, в компиляторе PL/1 для IBM-PC используется именно представление в виде BCD.
Вот нам и пригодились "приборные" форматы чисел, которые мы рассматривали в предыдущей статье. На самом деле, если говорить о финансовых программах, такое представление, и такой синтаксис, появилось для эмуляции поведения механических арифмометров и табуляторов. Для прямого переноса методов расчетов. Во всяком случае, изначально. Однако, это прижилось и используется даже в наши дни, когда механические арифмометры помнят уже немногие.
Заключение
Сегодня мы рассматривали низкоуровневое представление данных, которое является машинным, но не аппаратным. Своеобразная иллюстрация того, как обычные целые числа, которые мы рассматривали ранее, могут использоваться для представления куда более сложных рациональных чисел, которые целыми не являются.
Однако, рассмотренные сегодня форматы представления чисел с фиксированной запятой не позволяют писать программы, в которых используются рациональные числа полного диапазона. Конечно, не от минус бесконечности до плюс бесконечности, но в пределах нескольких десятков порядков. И в следующей статьи мы будем разбираться, как можно решить и эту проблему.
Будет интересно.