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

Question

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

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

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

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

Есть мысли по этому поводу?

Answer 1

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

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

Мой лучший совет - начинать с работающей реализации 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);
}

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

Сохраните экспоненту в битах с 24 по 30 вашего числа.

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

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

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

Answer 4

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

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

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

Если вы тщательно восстановите поплавок так:

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 цифр точности в целочисленной Мантиссе и смещенном экспоненте между -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 более оптимизирован.

Answer 5

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

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

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

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

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

Answer 6

Моя первая мысль - разобрать строку в 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 и бесконечность. Я не думал о денормализованных числах или режимах округления.

Answer 7

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

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

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

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

, который на странице 18 дает несколько интересных тестовых случаев.

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

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

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

Клайд

Answer 8

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

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

Answer 9

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

Answer 10

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

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