Как конвертировать строки в плавающие с идеальной точностью

Question

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

Код интересующей части алгоритма приведен ниже, и я вижу, откуда берется потеря точности, но я не знаю, как от нее избавиться. (Я пропустил много частей кода, которые не относились к основному алгоритму, чтобы спасти людей, читающих.) Какой алгоритм «строка-в-число» гарантирует, что результат будет максимально приближен к числу IEEE строка значения, представленного строкой.

real currentPlace = 10.0L ^^ (pointPos - ePos + 1 + expon);

real ans = 0;
for(int index = ePos - 1; index > -1; index--) {
    if(str[index] == '.') {
        continue;
    }

    if(str[index] < '0' || str[index] > '9') {
        err();
    }

    auto digit = cast(int) str[index] - cast(int) '0';
    ans += digit * currentPlace;
    currentPlace *= 10;
}

return ans * sign;

Кроме того, я использую юнит-тесты для старой версии, которые делали что-то вроде:

assert(to!(real)("0.456") == 0.456L);

Возможно ли, что ответы, выдаваемые моей функцией, на самом деле более точны, чем представление, которое компилятор создает при разборе литерала с плавающей запятой, но компилятор (который написан на C ++) всегда точно соответствует strtold, потому что он использует strtold внутренне для разбора литералов с плавающей точкой?

Answer 1

Clinger и Steele & White разработали прекрасные алгоритмы для чтения и записи чисел с плавающей запятой.

Здесь есть ретроспектива с некоторыми ссылками на реализации.

Бумага Дэвида Гея , улучшающая работу Клингера, и реализация Гей 1013 * в C великолепны. Я использовал их во встраиваемых системах, и я считаю, что dtoa гея вошел во многие libc.

Answer 2

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

Тем не менее, если вы действительно намерены написать свою собственную реализацию, лучшим справочным материалом для правильности являются «Правильно округленные двоичные и десятичные двоичные числа» ( postscript version ). Вам также следует изучить его справочные реализации (в C), которые доступны на Netlib .

Answer 3

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

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

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

Answer 4

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

Примером может быть 0.1 + 0.02, который не равен 0.12, если представлен как число с плавающей запятой. (Чтобы убедиться в этом, попробуйте сравнить их на своем любимом языке программирования)

Answer 5

Вы не можете хранить большинство поплавков с идеальной точностью на цифровом компьютере