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

StackOverflow https://stackoverflow.com/questions/85223

Вопрос

Конечно, в большинстве языков есть библиотечные функции для этого, но предположим, я хочу сделать это сам.

Предположим, что значение с плавающей точкой задано как в программе на C или Java (за исключением суффикса 'f' или 'd'), например "4.2e1", ".42e2" или просто "42".В общем случае у нас есть "целая часть" перед десятичной точкой, "дробная часть" после десятичной точки и "показатель степени".Все три являются целыми числами.

Легко найти и обработать отдельные цифры, но как вы объединяете их в значение типа float или double без потери точности?

Я подумываю о том, чтобы умножить целую часть на 10 ^n, где n является количеством цифр в дробной части, а затем добавляется дробная часть к целой части и вычитается n из экспоненты.Это эффективно превращает 4.2e1 в 42e0, например.Тогда я мог бы воспользоваться pow функция для вычисления 10^показатель степени и умножьте результат на новую целую часть.Вопрос в том, гарантирует ли этот метод максимальную точность во всем?

Есть какие-нибудь мысли по этому поводу?

Это было полезно?

Решение

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

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

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

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

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

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

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

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

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

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

Другие советы

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

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

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

/* use this to start your atof implementation */

/* atoi - christopher.watford@gmail.com */
/* 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);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

существует риск превысить точность как при суммировании integerMantissa, если оно содержит много цифр, так и при возведении 10 в степень biasedExponent...

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

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

10^8 > 2^24 > 10^7

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

5^11 > 2^24 > 5^10

Тем не менее, вы можете позволить себе 7 цифр точности в integerMantissa и biasedExponent в диапазоне от -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/clarifying-and-optimizing.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 и infinity.Я не думал о денормализованных числах или режимах округления.

Для этого вы должны понимать стандарт IEEE 754, чтобы обеспечить правильное двоичное представление.После этого вы можете использовать Float.intBitsToFloat или Удваивается.Лонгбиты удваиваются.

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

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

Невозможно преобразовать любую произвольную строку, представляющую число, в double или float без потери точности.Существует много дробных чисел, которые могут быть представлены точно в десятичной форме (например"0.1"), который может быть аппроксимирован только в двоичном формате с плавающей запятой или double.Это похоже на то, как дробь 1/3 не может быть представлена точно в десятичной системе счисления, вы можете написать только 0.3333333...

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

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

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

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

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

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

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

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

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

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

Клайд

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top