Почему Double.parseDouble (String) может быть легко вычислен до 1E22? - PullRequest
Новая
       9

Почему Double.parseDouble (String) может быть легко вычислен до 1E22?

4 голосов
/ 21 января 2020

Сегодня я погрузился в реализацию OpenJDK Double.parseDouble(String).

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

// possibly an easy case.
// We know that the digits can be represented
// exactly. And if the exponent isn't too outrageous,
// the whole thing can be done with one operation,
// thus one rounding error.
// isNegative indicates if the number being parsed is negative
// dValue is the mantissa
// exp is the exponent
if (exp >= 0) {
    if (exp <= MAX_SMALL_TEN) {
        //
        // Can get the answer with one operation,
        // thus one roundoff.
        //
        double rValue = dValue * SMALL_10_POW[exp];
        return (isNegative) ? -rValue : rValue;
    }
    int slop = MAX_DECIMAL_DIGITS - kDigits;
    if (exp <= MAX_SMALL_TEN + slop) {
        //
        // We can multiply dValue by 10^(slop)
        // and it is still "small" and exact.
        // Then we can multiply by 10^(exp-slop)
        // with one rounding.
        //
        dValue *= SMALL_10_POW[slop];
        double rValue = dValue * SMALL_10_POW[exp - slop];
        return (isNegative) ? -rValue : rValue;
    }
    //
    // Else we have a hard case with a positive exp.
    //
} else {
   //Deal with negative exp (omitted here)
}

Вот определения констант: 

static final int    MAX_DECIMAL_DIGITS = 15;
private static final double[] SMALL_10_POW = {
            1.0e0,
            1.0e1, 1.0e2, 1.0e3, 1.0e4, 1.0e5,
            1.0e6, 1.0e7, 1.0e8, 1.0e9, 1.0e10,
            1.0e11, 1.0e12, 1.0e13, 1.0e14, 1.0e15,
            1.0e16, 1.0e17, 1.0e18, 1.0e19, 1.0e20,
            1.0e21, 1.0e22
        };
private static final int MAX_SMALL_TEN = SMALL_10_POW.length-1;

Как мы видим из кода, в «простом случае» мы можем вычислить значение с помощью простого выражения: double rValue = dValue * SMALL_10_POW[exp], если exponent <= MAX_SMALL_TEN //=22. Если и только если экспонента больше 22, Double.parseDouble(String) go в ветку «сложный случай», где она делает первоначальное предположение и впоследствии играет с BigInteger ...

Что ввело это ограничение в 1.0E22? Дополнительный вопрос: Почему взлом с переменной slop приемлем, если есть ограничение в 1.0E22?

1 Ответ

2 голосов
/ 22 января 2020

Что ввело это ограничение в 1.0E22?

Тот факт, что 10 22 * ​​1006 * является наибольшей степенью 10, которая имеет точное представление как double .

A double (на x86) содержит 53 бита точности. 10 22 * ​​1012 * значительно больше, чем 2 53 - это чуть более 2 73 - но его последние 22 бита равны 0, поэтому только 52 бита мантиссы требуется представить это точно. Для 10 23 потребуется 54 бита, что больше, чем доступно. (10 N равно 5 N * 2 N , поэтому последний N биты равны 0. Поскольку 5 N нечетно, бит непосредственно перед конечными нулями N равен 1.)

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

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

Критерий "спада" - попытка консервативного оцените, насколько большим может быть «не слишком большой». (Я не знаю, насколько хорош критерий. Но это его цель.)

...