Почему «dtoa.c» содержит так много кода? - PullRequest
19 голосов
/ 04 июля 2010

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

Последние пару месяцев я работал над реализацией ECMAScript в C # и былзамедление заполнения отверстий в моем двигателе.Прошлой ночью я начал работать над Number.prototype.toString , который описан в разделе 15.7.4.2 спецификации ECMAScript (pdf) ,В разделе 9.8.1 ПРИМЕЧАНИЕ 3 предлагает ссылку на dtoa.c , но я искал проблему, поэтому я ждал ее просмотра.Вот то, что я придумал.

private IDynamic ToString(Engine engine, Args args)
{
    var thisBinding = engine.Context.ThisBinding;
    if (!(thisBinding is NumberObject) && !(thisBinding is NumberPrimitive))
    {
        throw RuntimeError.TypeError("The current 'this' must be a number or a number object.");
    }

    var num = thisBinding.ToNumberPrimitive();

    if (double.IsNaN(num))
    {
        return new StringPrimitive("NaN");
    }
    else if (double.IsPositiveInfinity(num))
    {
        return new StringPrimitive("Infinity");
    }
    else if (double.IsNegativeInfinity(num))
    {
        return new StringPrimitive("-Infinity");
    }

    var radix = !args[0].IsUndefined ? args[0].ToNumberPrimitive().Value : 10D;

    if (radix < 2D || radix > 36D)
    {
        throw RuntimeError.RangeError("The parameter [radix] must be between 2 and 36.");
    }
    else if (radix == 10D)
    {
        return num.ToStringPrimitive();
    }

    var sb = new StringBuilder();
    var isNegative = false;

    if (num < 0D)
    {
        isNegative = true;
        num = -num;
    }

    var integralPart = Math.Truncate(num);
    var decimalPart = (double)((decimal)num.Value - (decimal)integralPart);
    var radixChars = RadixMap.GetArray((int)radix);

    if (integralPart == 0D)
    {
        sb.Append('0');
    }
    else
    {
        var integralTemp = integralPart;
        while (integralTemp > 0)
        {
            sb.Append(radixChars[(int)(integralTemp % radix)]);
            integralTemp = Math.Truncate(integralTemp / radix);
        }
    }

    var count = sb.Length - 1;
    for (int i = 0; i < count; i++)
    {
        var k = count - i;
        var swap = sb[i];
        sb[i] = sb[k];
        sb[k] = swap;
    }

    if (isNegative)
    {
        sb.Insert(0, '-');
    }

    if (decimalPart == 0D)
    {
        return new StringPrimitive(sb.ToString());
    }

    var runningValue = 0D;
    var decimalIndex = 1D;
    var decimalTemp = decimalPart;

    sb.Append('.');
    while (decimalIndex < 100 && decimalPart - runningValue > 1.0e-50)
    {
        var result = decimalTemp * radix;
        var integralResult = Math.Truncate(result);
        runningValue += integralResult / Math.Pow(radix, decimalIndex++);
        decimalTemp = result - integralResult;
        sb.Append(radixChars[(int)integralResult]);
    }

    return new StringPrimitive(sb.ToString());
}

Может кто-нибудь с большим опытом программирования низкого уровня объяснить, почему dtoa.c имеет примерно в 40 раз больше кода?Я просто не могу представить, чтобы C # был гораздо более продуктивным.

Ответы [ 5 ]

40 голосов
/ 04 июля 2010

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

Ваш код пытается реализовать только эквивалент dtoa (), и, поскольку он использует числа с плавающей запятой для своих преобразований, не всегда получает ихправо.(Обновление: подробности см. В моей статье http://www.exploringbinary.com/quick-and-dirty-floating-point-to-decimal-conversion/.)

(об этом я много писал в своем блоге, http://www.exploringbinary.com/. Шесть из моих последних семи статей былитолько о преобразованиях strtod (). Прочтите их, чтобы узнать, насколько сложно правильно делать округленные преобразования.)

8 голосов
/ 04 июля 2010

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

Основной источник трудностей заключается в том, что многие десятичные дроби, даже простые, не могут быть точно выраженными с использованием двоичной плавающей запятой - например, 0.5 может (очевидно), но 0.1 не может , И, идя другим путем (от двоичного к десятичному), вы, как правило, не хотите иметь абсолютно точный результат (например, точное десятичное значение ближайшего числа к 0.1, которое может быть представлено в IEEE-754-совместимом double на самом деле 0.1000000000000000055511151231257827021181583404541015625) так что вы обычно хотите некоторое округление.

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

Взгляните на статью, цитируемую в комментариях в верхней части реализации dtoa.c, Clinger's Как читать числа с плавающей запятой точно , для понимания проблемы; и, возможно, статья Дэвида М. Гея (автора), Правильно округленные двоично-десятичные и десятично-двоичные преобразования .

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

4 голосов
/ 04 июля 2010

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

4 голосов
/ 04 июля 2010

На основании быстрого взгляда на это, значительная часть версии C имеет дело с несколькими платформами, и похоже, что этот файл предназначен для общего использования в компиляторах (C & C ++), битности, реализации с плавающей запятой и платформы; с тоннами #define конфигурируемость.

2 голосов
/ 04 июля 2010

Краткий ответ: потому что dtoa.c работает.

В этом и заключается разница между хорошо отлаженным продуктом и прототипом NIH.

...