Одна из удивительных вещей о реальном, практичном компьютере - удивляющем начинающих программистов, которым в любом случае была поставлена задача написать искусственные маленькие программы преобразования двоичных чисел в десятичные, - насколько глубоко укоренилась система двоичных чисел вфактический компьютер, и как мало и насколько распространены любые фактические процедуры двоичного / десятичного преобразованияНапример, в мире Си (и если мы ограничим наше внимание целыми числами на данный момент), существует, по сути, одна подпрограмма преобразования двоичной системы в десятичную, которая находится внутри printf, где обрабатывается директива %d. Существует, возможно, три десятичных в двоичные преобразователи: atof(), strtol() и %d преобразование внутри scanf. (Там может быть еще один внутри компилятора C, где он преобразует ваши десятичные константы в двоичные, хотя для них компилятор может просто вызвать strtol() напрямую.)
Я приведу все это для фона. Вопрос "каков реальный алгоритм для построения чисел с плавающей точкой внутри?"это справедливо, и я хотел бы думать, что знаю ответ, но, как я упоминал в комментариях, я огорчен, обнаружив, что на самом деле не знаю: я не могу описать ясный, четкий »алгоритм». Я могу и покажу вам некоторый код , который выполнит работу, но вы, вероятно, найдете ее неудовлетворительной, как будто я каким-то образом обманываю - потому что ряд интересных деталей происходит более или менее автоматически, как мы увидим.
По сути, я собираюсь написать версию стандартной функции библиотеки atof(). Вот мои основные правила:
- Я собираюсь предположить, что ввод представляет собой строку символов. (Это вовсе не предположение; это переформулировка исходной проблемы, которая заключается в написании версии
atof.) - Я собираюсь предположить, что мы можем построить плавающуюномер точки "0.0". (В IEEE 754 и большинстве других форматов это все биты 0, так что это не так уж сложно.)
- Я собираюсь предположить, что мы можем преобразовать целые числа 0-9 в соответствующие им числа с плавающей запятойэквиваленты.
- Я собираюсь предположить, что мы можем добавлять и умножать любые числа с плавающей запятой, которые мы хотим. (Это важная вещь, хотя я опишу эти алгоритмы позже.) Но на любом современном компьютере почти наверняка есть модуль с плавающей запятой, который имеет встроенные инструкции для основных операций с плавающей запятой, таких как сложение и умножение, поэтомуэто также не является необоснованным предположением. (Но в конечном итоге он скрывает некоторые интересные аспекты алгоритма, передавая разработчику аппаратного обеспечения правильное выполнение инструкций.)
- Сначала я предполагаю, что у нас есть доступ кстандартные функции библиотеки
atoi и pow. Это довольно большое предположение, но опять же, позже я опишу, как мы могли бы написать их с нуля, если бы захотели. Я также собираюсь предположить существование функций классификации символов в <ctype.h>, особенно isdigit().
Но это все. Оказывается, что с этими предпосылками мы можем сами написать полностью функциональную версию atof(). Это может быть не быстро, и почти наверняка у него не будет правильного поведения округления по краям, но оно будет работать довольно хорошо. (Я даже собираюсь обрабатывать отрицательные числа и показатели степени.) Вот как это работает:
- пропустить начальные пробелы
- искать
'-' - сканированиеЦифровые символы, преобразующие каждый из них в соответствующую цифру путем вычитания
'0' (он же ASCII 48) - накапливает число с плавающей запятой (без дробной части), представляющее целое число, подразумеваемое цифрами - значимое и - и это настоящая математика, умножив текущее накопление на 10 и добавив следующую цифру
- , если мы увидим десятичную точку, посчитаем количество цифр после нее
- когда мы закончим сканирование цифр, посмотрите, есть ли
e / E и еще несколько цифр, указывающих показатель степени - , если необходимо, умножьте или разделите наше накопленное число на степень 10,заботиться о цифрах после десятичной дроби и / или явном показателе степени.
Вот код:
#include <ctype.h>
#include <stdlib.h> /* just for atoi() */
#include <math.h> /* just for pow() */
#define TRUE 1
#define FALSE 0
double my_atof(const char *str)
{
const char *p;
double ret;
int negflag = FALSE;
int exp;
int expflag;
p = str;
while(isspace(*p))
p++;
if(*p == '-')
{
negflag = TRUE;
p++;
}
ret = 0.0; /* assumption 2 */
exp = 0;
expflag = FALSE;
while(TRUE)
{
if(*p == '.')
expflag = TRUE;
else if(isdigit(*p))
{
int idig = *p - '0'; /* assumption 1 */
double fdig = idig; /* assumption 3 */
ret = 10. * ret + fdig; /* assumption 4 */
if(expflag)
exp--;
}
else break;
p++;
}
if(*p == 'e' || *p == 'E')
exp += atoi(p+1); /* assumption 5a */
if(exp != 0)
ret *= pow(10., exp); /* assumption 5b */
if(negflag)
ret = -ret;
return ret;
}
Прежде чем мы пойдем дальше, я рекомендую вам скопировать и- вставьте этот код в ближайший компилятор C и скомпилируйте его, чтобы убедить себя, что я не обманул тоже плохо. Вот немного main(), чтобы вызвать его с помощью:
#include <stdio.h>
int main(int argc, char *argv[])
{
double d = my_atof(argv[1]);
printf("%s -> %g\n", argv[1], d);
}
(Если вам или вашей IDE не нравятся вызовы командной строки, вы можете использовать fgets или scanf для чтения строкивместо этого my_atof.
Но, я знаю, ваш вопрос был «Как конвертировать 9 в 1.001 * 2 ^ 3?», и я до сих пор не ответил на это,Я? Итак, давайте посмотрим, сможем ли мы найти, где это произойдет.
Прежде всего, эта битовая комбинация 1001 2 для 9 пришла из ... ниоткуда или везде, или она была там все время, или что-то. Вошел символ 9, вероятно, с битовой комбинацией 111001 2 (в ASCII). Мы вычли 48 = 110000 2 , и выскочили 1001 2 . (Даже перед выполнением вычитания вы можете увидеть, как он там прятался в конце 111001.)
Но что же превратило 1001 в 1.001E3? По сути, это было мое «предположение 3», заключенное в строке
double fdig = idig;
. Такую строку легко написать на C, поэтому нам не нужно знать, как это делается, и компилятор, вероятно, переворачиваетона превращается в инструкцию 'convert integer to float', поэтому разработчику компилятора также не нужно знать, как это сделать.
Но, если мы должны были реализовать это самина самом низком уровне, мы могли бы. Мы знаем, что имеем однозначное (десятичное) число, занимающее не более 4 бит. Мы можем вставить эти биты в поле значимости нашего формата с плавающей запятой с фиксированным показателем степени (возможно, -3). Нам, возможно, придется иметь дело с особенностями «неявного 1» бита, и если мы не хотим непреднамеренно создать денормализованное число, нам, возможно, придется еще немного поработать, но это будет достаточно просто и относительно легко получить. правильно, потому что есть только 10 случаев для проверки. (Черт, если бы мы обнаружили, что написание кода затрудняет работу с битами, мы могли бы даже использовать справочную таблицу из 10 записей.)
Поскольку 9 - однозначное число, мы закончили. Но для многозначного числа нашей следующей задачей является арифметика, которую мы должны сделать: умножить текущую сумму на 10 и добавить следующую цифру. Как это работает, точно?
Опять же, если мы пишем программу на C (или даже на ассемблере), нам не нужно знать, потому что наша машина с плавающей точкой добавляет и добавляет«Умножить» инструкции сделают все для нас. Но, опять же, если бы нам пришлось делать это самим, мы могли бы. (Этот ответ становится слишком длинным, поэтому я пока не собираюсь обсуждать алгоритмы сложения и умножения с плавающей запятой. Может быть, еще дальше.)
Наконец, представленный код «обманул», вызвавфункции библиотеки atoi и pow. У меня не будет проблем с тем, чтобы убедить вас в том, что мы могли бы реализовать atoi сами, если бы захотели / должны были: это в основном тот же код накопления цифр, который мы уже написали. И pow тоже не сложно, потому что в нашем случае нам не нужно реализовывать его в полной общности: мы всегда возводим в целочисленные степени, так что это прямое повторное умножение, и мы уже предположили, чтоуметь умножать.
(С учетом сказанного, вычисление большой степени 10 как части нашего десятичного-двоичного алгоритма является проблематичным. Как заметил @Eric Postpischil в своем ответе: «Обычно мы хотим вычислить двоичный результат с плавающей запятой безна самом деле вычисление 10 N . "Я, так как я не знаю ничего лучше, я все равно вычислю его, но если бы я написал свой pow(), я бы использовал двоичное возведение в степень *Алгоритм 1109 *, поскольку он очень прост в реализации и довольно приятен.)
Я сказал, что буду обсуждать процедуры сложения и умножения с плавающей точкой. Предположим, вы хотите добавить два числа с плавающей точкой. Если они имеют одинаковый показатель степени, это легко: добавьте два значения (и оставьте показатель одинаковым), и это ваш ответ. (Как вы добавляете значения: ну, я полагаю, у вас есть способ добавить целые числа.) Если показатели разные, но относительно близки друг к другу, вы можете выбрать меньший и добавить к нему N, чтобы сделать его таким жекак большее, одновременно сдвигая значение на вправо на N битов. (Вы только что создали денормализованное число.) Как только показатели будут одинаковыми, вы можете добавить значения и значения, как и раньше. После сложения может быть важно перенормировать числа, то есть определить, заканчивался ли один или несколько старших битов как 0, и, если это так, сдвинуть значение на лево и уменьшить экспоненту. Наконец, если показатели слишком разные, так что смещение одного значения на вправо на N битов сместит все это в сторону, это означает, что одно число настолько меньше другого, что все оно теряется в округлении при добавлении их.
Умножение: умножение с плавающей точкой на самом деле несколько проще, чем сложение. Вам не нужно беспокоиться о сопоставлении показателей: конечный продукт - это, в основном, новое число, значение которого является произведением двух значений, а показатель степени является суммой двух показателей. Единственная хитрость заключается в том, что произведение двух М-битных значений - это номинально 2 Мбит, и у вас может не быть множителя, который мог бы это сделать. Если единственный имеющийся у вас множитель достигает максимума в M-битном продукте, вы можете взять два M-битных значения и буквально разделить их пополам на биты:
signif1 = a * 2 M / 2 + b
signif2 = c * 2 M / 2 + d
Итак, по обычной алгебре имеем
signif1 × signif2 = ac × 2 M + ad × 2 M / 2 + bc × 2 M / 2 + bd
Каждый из этих частичных произведений ac, ad и т. Д. Является M-разрядным произведением. Умножение на 2 M / 2 или 2 M легко, потому что это просто сдвиг влево. И добавление терминов - это то, что мы уже знаем, как сделать. На самом деле мы заботимся только о верхних M битах продукта, поэтому, так как мы собираемся отбросить остальные, я думаю, мы могли бы обмануть и пропустить термин bd , так как он ничего не дает (хотя это можетв конечном итоге немного влияет на правильно округленный результат).
Но в любом случае, детали алгоритмов сложения и умножения, а также знания, которые они содержат о представлении с плавающей запятой, которое мы используем, в конечном итоге образуют другиеполовина ответа на вопрос о десятичном-двоичном «алгоритме», который вы ищете. Если вы преобразуете, скажем, число 5.703125, используя код, который я показал, из него выскочит двоичное число с плавающей точкой 1.01101101 2 × 2 2 , но мы нигде явно не вычислилиэто означает, и 1.01101101, или этот показатель 2 - они оба выпали из всех произведенных нами умножений и сложений в цифровом виде.
Наконец, если вы все еще со мной, вот быстрый и простой метод целочисленного питанияpow функция с использованием двоичного возведения в степень:
double my_pow(double a, unsigned int b)
{
double ret = 1;
double fac = a;
while(1) {
if(b & 1) ret *= fac;
b >>= 1;
if(b == 0) break;
fac *= fac;
}
return ret;
}
Это изящный маленький алгоритм. Если мы попросим его вычислить, скажем, 10 21 , он не умножит 10 на себя 21 раз. Вместо этого он многократно квадратов 10, что приводит к экспоненциальной последовательности 10 1 , 10 2 , 10 4 , 10 8, точнее, 10, 100, 10000, 100000000 ... Затем он просматривает двоичное представление 21, а именно 10101, и выбирает только промежуточные результаты 10 1 , 10 4 и 10 16 для умножения на его окончательное возвращаемое значение, получая 10 1 + 4 + 16 или 10 21 , по желанию. Поэтому он запускается во времени O (log 2 (N)), а не O (N).
И настройтесь на завтра для нашего следующего захватывающего эпизода, когда мы пойдемв обратном направлении, написание двоично-десятичного преобразователя, который потребует от нас сделать ... (зловещий аккорд)
длинное деление с плавающей запятой !