Как вручную разобрать число с плавающей запятой из строки

Я бы напрямую собрал число с плавающей запятой, используя его двоичное представление.

Прочитайте в числе один символ за другим и сначала найдите все цифры. Сделайте это в целочисленной арифметике. Также следите за десятичной точкой и показателем степени. Это будет важно позже.

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

Биты, следующие сразу за первым битом, и есть ваша мантисса.

Получить экспоненту тоже не сложно. Вы знаете первую однобитовую позицию, позицию десятичной точки и необязательную экспоненту из научного представления. Объедините их и добавьте смещение экспоненты с плавающей запятой (я думаю, что это 127, но проверьте ссылку, пожалуйста).

Этот показатель степени должен быть где-то в диапазоне от 0 до 255. Если он больше или меньше, у вас есть положительное или отрицательное бесконечное число (частный случай).

Сохраните показатель степени в битах с 24 по 30 вашего числа с плавающей запятой.

Самый значащий бит — это просто знак. Единица означает отрицательное значение, ноль означает положительное значение.

Это сложнее описать, чем оно есть на самом деле, попробуйте разложить число с плавающей запятой и взгляните на показатель степени и мантиссу, и вы увидите, насколько это просто на самом деле.

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

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

Если вы не боитесь математики, настоятельно рекомендую прочитать следующую статью Дэвида Голдберга: Что должен знать каждый программист об арифметике с плавающей запятой. Вы лучше поймете, что происходит под капотом, и почему биты расположены именно так.

Мой лучший совет — начать с работающей реализации atoi и двигаться дальше. Вы быстро обнаружите, что что-то упускаете, но несколько взглядов на strtod , и вы окажетесь на правильном пути (а это очень-очень долгий путь). В конце концов вы будете хвалить вставьте сюда диету за то, что существуют стандартные библиотеки.

/* use this to start your atof implementation */

/* atoi - [email protected] */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
  unsigned long ival = 0, c, n = 1, i = 0, oval;
  for( ; c = value[i]; ++i) /* chomp leading spaces */
    if(!isspace(c)) break;
  if(c == '-' || c == '+') { /* chomp sign */
    n = (c != '-' ? n : -1);
    i++;
  }
  while(c = value[i++]) { /* parse number */
    if(!isdigit(c)) return 0;
    ival = (ival * 10) + (c - '0'); /* mult/accum */
    if((n > 0 && ival > LONG_MAX)
    || (n < 0 && ival > (LONG_MAX + 1UL))) {
      /* report overflow/underflow */
      errno = ERANGE;
      return (n > 0 ? LONG_MAX : LONG_MIN);
    }
  }
  return (n>0 ? (long)ival : -(long)ival);
}

«Стандартный» алгоритм преобразования десятичного числа в наилучшее приближение с плавающей запятой — это Как читать числа с плавающей запятой Уильяма Клингера. числа точно, которые можно загрузить с здесь. Обратите внимание, что для правильного выполнения этого требуются целые числа с множественной точностью, по крайней мере, в определенном проценте случаев, чтобы обрабатывать крайние случаи.

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

См. также статью Дэвида М. Гея Правильно округленные двоично-десятичные и десятично-двоичные преобразования. для алгоритмов, работающих в обоих направлениях.

Вы можете игнорировать десятичное число при разборе (кроме его местоположения). Скажем, ввод был: 156.7834e10... Это можно было бы легко разобрать на целое число 1567834, за которым следует e10, которое вы затем изменили бы на e6, поскольку десятичное число было 4 цифрами от конца «цифровой» части числа с плавающей запятой. .

Точность - это проблема. Вам нужно будет проверить спецификацию IEEE языка, который вы используете. Если количество битов в мантиссе (или дроби) больше, чем количество битов в вашем типе Integer, вы, возможно, потеряете точность, когда кто-то введет число, например:

5123.123123e0 — в нашем методе преобразуется в 5123123123, что НЕ соответствует целому числу, но биты для 5.123123123 могут соответствовать мантиссе спецификации числа с плавающей запятой.

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

В любом случае, удачи!

Да, вы можете разложить построение на операции с плавающей запятой, если эти операции ТОЧНЫ, и вы можете позволить себе единственный финал неточная операция.

К сожалению, операции с плавающей запятой скоро становятся неточными, когда вы превышаете точность мантиссы, результаты округляются. Как только появится «ошибка» округления, она будет накапливаться в дальнейших операциях...
Итак, как правило, НЕТ, вы не можете использовать такой наивный алгоритм для преобразования произвольных десятичных знаков, это может привести к неправильно округленному числу, отличающемуся от правильного на несколько ulp, как вам уже сказали другие.

НО ДАВАЙТЕ ПОСМОТРИМ, НАСКОЛЬКО МЫ МОЖЕМ ЗАЙТИ:

Если вы тщательно восстановите поплавок следующим образом:

if(biasedExponent >= 0)
    return integerMantissa * (10^biasedExponent);
else
    return integerMantissa / (10^(-biasedExponent));

существует риск превышения точности как при суммировании целочисленной мантиссы, если она имеет много цифр, так и при возведении 10 в степень смещенного экспонента...

К счастью, если первые две операции точны, то можно позволить себе окончательную неточную операцию * или /, благодаря свойствам IEEE результат будет округлен правильно.

Давайте применим это к числам с плавающей запятой одинарной точности, которые имеют точность 24 бита.

10^8 > 2^24 > 10^7

Отметив, что число, кратное 2, только увеличит показатель степени и оставит мантиссу неизменной, нам нужно иметь дело только со степенями 5 для возведения в степень 10:

5^11 > 2^24 > 5^10

Тем не менее, вы можете позволить себе 7-значную точность в целочисленной мантиссе и смещенный экспонент между -10 и 10.

С двойной точностью, 53 бита,

10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22

Таким образом, вы можете позволить себе 15 десятичных цифр и смещенный показатель степени между -22 и 22.

Вам решать, всегда ли ваши числа будут попадать в правильный диапазон... (Если вы действительно хитры, вы можете сбалансировать мантиссу и экспоненту, вставив/удалив конечные нули).

В противном случае вам придется использовать некоторую повышенную точность.
Если ваш язык предоставляет целые числа произвольной точности, то сделать это правильно будет немного сложно, но не так сложно, я сделал это в Smalltalk и написал об этом в блоге http://smallissimo.blogspot.fr/2011/09/уточнение-и-оптимизация.html и http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

Обратите внимание, что это простые и наивные реализации. К счастью, libc более оптимизирована.

Моей первой мыслью было разобрать строку на мантисса int64 и десятичный показатель степени int, используя только первые 18 цифр мантиссы. Например, 1.2345e-5 будет разобрано на 12345 и -9. Затем я продолжал бы умножать мантиссу на 10 и уменьшать показатель степени до тех пор, пока мантисса не станет длиной 18 цифр (> 56 бит точности). Затем я бы посмотрел десятичный показатель в таблице, чтобы найти множитель и двоичный показатель, которые можно использовать для преобразования числа из десятичной формы n * 10 ^ m в двоичную форму p * 2 ^ q. Коэффициент будет другим int64, поэтому я умножу на него мантиссу, чтобы получить верхние 64 бита результирующего 128-битного числа. Эту мантиссу int64 можно преобразовать в число с плавающей запятой, потеряв только необходимую точность, а показатель степени 2^q можно применить с помощью умножения без потери точности.

Я ожидаю, что это будет очень точно и очень быстро, но вы также можете обрабатывать специальные числа NaN, -infinity, -0.0 и бесконечность. Я не думал о денормализованных числах или режимах округления.

Для этого вы должны понимать стандарт IEEE 754 для правильного двоичного представления. После этого вы можете использовать Float.intBitsToFloat или Double.longBitsToDouble.

http://en.wikipedia.org/wiki/IEEE_754

Если вам нужен максимально точный результат, вы должны использовать более высокую внутреннюю рабочую точность, а затем преобразовать результат с понижением до желаемой точности. Если вы не возражаете против нескольких ULP ошибок, вы можете просто многократно умножать на 10 по мере необходимости с желаемой точностью. Я бы избегал функции pow(), так как она будет давать неточные результаты для больших показателей.

Невозможно преобразовать любую произвольную строку, представляющую число, в двойное число или число с плавающей запятой без потери точности. Есть много дробных чисел, которые могут быть точно представлены в десятичном виде (например, «0,1»), которые могут быть аппроксимированы только в двоичном формате с плавающей запятой или двойным числом. Это похоже на то, как дробь 1/3 не может быть точно представлена ​​в десятичном виде, вы можете написать только 0,333333...

Если вы не хотите использовать библиотечную функцию напрямую, почему бы не посмотреть исходный код этих библиотечных функций? Вы упомянули Java; большинство JDK поставляются с исходным кодом для библиотек классов, поэтому вы можете посмотреть, как работает метод java.lang.Double.parseDouble(String). Конечно, что-то вроде BigDecimal лучше подходит для управления режимами точности и округления, но вы сказали, что это должно быть число с плавающей запятой или двойное число.

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

Я согласен с термином. Конечный автомат — лучший способ выполнить эту задачу, поскольку есть много глупых способов сломать синтаксический анализатор. Я работаю над одним сейчас, я думаю, что он завершен, и у него есть, я думаю, 13 состояний.

Проблема не тривиальна.

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

Я нашел это сегодня http://speleotrove.com/decimal/decarith.pdf

который на странице 18 дает несколько интересных тестовых примеров.

Да, я читал статью Клингера, но, будучи простодушным инженером по аппаратному обеспечению, я не могу разобраться в представленном коде. Мне была полезна ссылка на алгоритм Стила, как он описан в тексте Кнута. И ввод, и вывод проблематичны.

Все вышеупомянутые ссылки на различные статьи превосходны.

Мне еще предстоит зарегистрироваться здесь, но когда я это сделаю, при условии, что логин не занят, это будет бро. (брох-точка).

Клайд