Почему dtoa.c содержит так много кода?

Я буду первым, кто признает, что мои общие знания о низкоуровневом программировании немного скудны. Я понимаю многие основные концепции, но не использую их на регулярной основе. При этом я был совершенно поражен тем, сколько кода потребовалось для 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# был настолько продуктивнее.


person ChaosPandion    schedule 03.07.2010    source источник
comment
Почему ты не можешь себе этого представить? Именно из-за такого дифференциала такие языки, как C#, так популярны.   -  person    schedule 04.07.2010
comment
@ Нил - думаю, это не так уж сложно представить. Я должен был понять, сколько труда уходит на то, чтобы сделать нативный код кроссплатформенным.   -  person ChaosPandion    schedule 04.07.2010
comment
Вы тестировали этот код с отрицательными входными данными?   -  person Mark Dickinson    schedule 04.07.2010
comment
@Mark - Ну, будь я проклят, была ошибка с отрицательными числами. Хорошо поймал.   -  person ChaosPandion    schedule 04.07.2010
comment
Это работает с небольшими числами, такими как 1e-20?   -  person sth    schedule 04.07.2010
comment
@sth - Теперь так, большое спасибо. Вы молодцы, должен сказать.   -  person ChaosPandion    schedule 04.07.2010
comment
Я также подозреваю, что (1.3333333333333333).toString(3) не дает 1.1 с вашей реализацией...   -  person sth    schedule 04.07.2010
comment
@sth - Это то, что я искал. Большое спасибо.   -  person ChaosPandion    schedule 04.07.2010


Ответы (5)


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

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

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

person Rick Regan    schedule 04.07.2010
comment
Очень интересно, мне нужно кое-что прочитать, и мне определенно нужно более подробно изучить этот код. - person ChaosPandion; 04.07.2010
comment
На самом деле нетрудно поверить, что я бы пропустил двустороннее преобразование, показанное в этом файле. Код действительно трудно для меня читать. - person ChaosPandion; 04.07.2010
comment
Как вы объясните тот факт, что число 1024.1 при преобразовании в основание 2 дает в Firefox тот же результат, что и в моей реализации? Может ли это быть очень специфичным, и неправильные результаты будут обнаружены только в результате обширных тестов? - person ChaosPandion; 04.07.2010
comment
Не каждое преобразование будет ошибочным. Попробуйте еще несколько, и вы обнаружите, что один Firefox работает правильно, а ваш нет. (Кстати: как вы проверяете, что они одинаковы? Вы печатаете все цифры двойного числа?) - person Rick Regan; 04.07.2010
comment
Случаи, когда он ошибается, будут довольно редкими, тем реже, чем лучше будет ваша реализация. Если ваша реализация действительно хороша, вы можете доказать, что она никогда не ошибается ни в одном из них. Если ваша реализация дерьмовая, она может вообще не работать. Например, если вы просто тестируете 1024.1, я могу пройти этот тест с return "1024.1";. :-) - person R.. GitHub STOP HELPING ICE; 04.07.2010
comment
+1. Не говоря уже о том, что функция dtoa Гея (которая является меньшей из двух частей функциональности в dtoa.c) также позволяет пользователю указать, сколько цифр выводить и какой метод округления использовать. Проще говоря, код C# в вопросе делает лишь небольшую часть того, что делает dtoa.c, и делает это неточно, медленно и с ошибками (например, попробуйте с отрицательными числами). - person Mark Dickinson; 04.07.2010
comment
Я просто хотел кое-что уточнить: вы сказали 1024.1 при преобразовании в base-2. Я предположил, что вы имели в виду преобразование в двоичную форму с плавающей запятой, а затем печать в десятичном формате (в конце концов, печать в десятичном формате усложняет проблему и почему существует dtoa.c). Но при втором прочтении вашего комментария я подумал, что, может быть, вы говорите, что устанавливаете систему счисления на 2 и печатаете в двоичном формате. Это будет работать (при условии, что в вашем коде нет ошибок - я его не запускал), как и для любой степени двойки - это, по сути, сдвиг битов. (Но тогда мне пришлось бы спросить — как вы заставили Firefox печатать в двоичном формате?) - person Rick Regan; 04.07.2010
comment
@Марк - Вау, успокойся. Я не утверждаю, что это код качества производства. Это простой побочный проект, который я делаю для удовольствия. Я просто любопытный кодер, пытающийся понять, как все это работает. Мне все равно, что мой медленнее. Я не думаю, что мой код настолько ошибочен, как вы утверждаете, поскольку отрицательные числа работают нормально. Что касается тестирования, я просто звонил (1024.1).toString(2); или (144.15).toString(36);. Очевидно, ничего формального, но вывод точно соответствует Firefox. - person ChaosPandion; 04.07.2010
comment
@Rick - Как вы думаете, что больше способствует количеству кода, кросс-платформенной совместимости или чрезвычайной точности, которую обеспечивает dtoa? - person ChaosPandion; 04.07.2010
comment
Вы пробовали просто старый toString() (база 10)? Это интересно - насколько мне известно, Javascript использует dtoa.c, но dtoa.c печатает только десятичные строки. Интересно, что используется для печати с недесятичными основаниями? Что касается объема кода, я бы сказал, что это требование предельной точности (но Марк более квалифицирован, чтобы ответить, так как много работал с dtoa.c). - person Rick Regan; 04.07.2010
comment
@Rick - интересно, поэтому он разрывает мой код на новый. :) - person ChaosPandion; 04.07.2010
comment
@Rick - Похоже, мне не нужно было проводить этот обширный тест, чтобы найти его. @sth обнаружил, что (1.3333333333333333).toString(3) является примером сбоя моего кода. - person ChaosPandion; 04.07.2010
comment
Две вещи: 1) dtoa.c работает только с основанием 10, поэтому мы больше не сравниваем ваш код с dtoa.c (если только кто-то в Javascript не модифицировал его для этого). 2) 1.33333333333333333 десятичное число концептуально ближе всего к 1.1 с основанием 3, но не забывайте, что сначала оно проходит через двоичную систему с плавающей запятой, а затем к основанию 3; Я думаю, что в этом случае разрешено не быть 1.1, если то, что он печатает, точно представляет значение в переменной с плавающей запятой. - person Rick Regan; 04.07.2010
comment
@Rick - Знаешь что? Мой вывод соответствует выводу IE. Я не могу не задаться вопросом, что именно делают эти два браузера. Немного утешительно, что мой вывод соответствует широко используемой реализации. - person ChaosPandion; 04.07.2010
comment
Не могли бы вы привести несколько примеров сопоставления вывода для преобразования в десятичные строки? Я хотел бы лучше понять, что именно вы сравниваете. (Кроме того, вы запускаете случайные тесты или просто выбираете примеры вручную? Я не думаю, что вы можете сказать, что результат будет таким же, если вы не запустите миллионы примеров). - person Rick Regan; 04.07.2010
comment
@Rick - я не настолько глуп, чтобы думать, что мой код работает на 100% правильно без формального теста. - person ChaosPandion; 04.07.2010
comment
Вы знаете, несмотря на то, что люди ломают мой код, я чувствую, что узнал в 100 раз больше, чем если бы я просто подключил нативную DLL и использовал dtoa.c. В любом случае, я ценю ваши ответы и спасибо за ссылку на блог. - person ChaosPandion; 05.07.2010
comment
Довольно неожиданно, что преобразование двойного числа в десятичное в вашей простой программе точно соответствует IE и Firefox. Если это так, то dtoa.c не нужен. Я просто предполагаю, что, возможно, в вашей методологии тестирования есть ошибка. Не могли бы вы дать мне хотя бы один пример двойного преобразования в десятичное, который соответствует, просто чтобы я мог видеть, что вы сравниваете? (И вы можете получить ссылку на блог!) - person Rick Regan; 05.07.2010
comment
@ChaosPandion: (1) Приносим извинения за тон предыдущего комментария. (2) Это требование «правильного округления» отвечает за большую часть размера dtoa.c: оно, по сути, содержит свою собственную маленькую целочисленную библиотеку произвольной точности, чтобы быть уверенным, что результаты вычислений правильно округлены. И точное определение всех угловых случаев (не говоря уже о тщательном тестировании) действительно на удивление сложно. - person Mark Dickinson; 05.07.2010
comment
@Chaos: В основе вашего вопроса лежит в основном; Мой код делает все, что делает dtoa, так почему же dtoa такой большой? Это неверно, ваш код вообще не делает того, что делает dtoa, так что не удивляйтесь, когда люди обратятся к вам. - person Ed S.; 18.08.2010
comment
Ничего себе, ПУТЬ слишком много разговоров здесь. Вы, ребята, должны были сделать это в чате. - person unixman83; 13.02.2012

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

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

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

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

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

person Matthew Slattery    schedule 03.07.2010
comment
Я хорошо осведомлен о проблемах, которые представляют собой операции с плавающей запятой. Мой вопрос больше связан с разницей в количестве кода. Когда я тестировал свой пример на Firefox, мой код дал идентичные результаты. Firefox использует dtoa.c. - person ChaosPandion; 04.07.2010

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

person dkackman    schedule 03.07.2010
comment
Я согласен. Я также бегло взглянул на код, мне стало тошно от той работы, которую он представляет для такой простой операции. С .NET я вижу, что эти времена, к счастью, остались позади для программирования приложений. - person jdehaan; 04.07.2010
comment
Не проще ли было бы иметь архив c-файлов, каждый из которых поддерживает отдельную платформу? Чтение всех этих #ifdef блоков вызвало у меня аневризму головного мозга... - person ChaosPandion; 04.07.2010
comment
Да, проблема не в языках, а в общем неуклюжем дизайне. Тот же эффект может быть достигнут с помощью лучшей модульности. - person Cogwheel; 04.07.2010
comment
@ChaosPandion: зависит от того, хотите ли вы, чтобы ваша конфигурация для конкретной платформы выполнялась в заголовочном файле C (установка определений) или в make-файле (выбор правильного файла .c для сборки). Кроме того, если имеется достаточно определений, чтобы дать вам аневризму, это может быть 2^отличных от аневризмы c-файла, если все возможности умножить. На практике, при написании такого ультрапортативного материала обычно требуется небольшое количество исходных файлов (в данном случае 1, но иногда и больше), управляемое большим количеством параметров конфигурации, а не наоборот. - person Steve Jessop; 04.07.2010
comment
... и причина, по которой вы можете захотеть написать код для поддержки платформ на основе их поведения/свойств, а не писать ровно одну реализацию dtoa для каждой платформы, заключается в том, что вы можете портировать на новые платформы, просто написав файл заголовка с правильная комбинация определений, а не переписывание всего stdlib каждый раз. Реализация с широкими возможностями настройки, подобная этой, не всегда является лучшей, но она может быть не так плоха, как кажется, если рассмотреть альтернативу. - person Steve Jessop; 04.07.2010
comment
@Steve - Вы знаете, я думаю, что, возможно, это был первоначальный шок от того, что я увидел так много кода. Глядя на это более подробно, на самом деле получается немного лучше. Я также нашел комментарий @Tyler в ответе @Lajnold немного поучительным по этому вопросу. - person ChaosPandion; 04.07.2010
comment
@dkackman - Как вы думаете, что больше способствует количеству кода, кросс-платформенной совместимости или исключительной точности, которую обеспечивает dtoa? - person ChaosPandion; 04.07.2010
comment
@ChaosPandion мне трудно судить, не вникая в него (приблизительно примерно 50/50). Один из способов отделить зёрна от плевел — просмотреть предварительно обработанный вывод для компиляции, в которой #define настроен так, как вы хотите поддерживать. Используя инструменты MS, вы можете сделать это примерно так: CL /E /C dtoa.c › dtoa.pre.c. Это покажет вам, что препроцессор на самом деле отправляет компилятору. - person dkackman; 04.07.2010

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

person Lajnold    schedule 03.07.2010
comment
Многие функции библиотеки C (и расширения библиотеки C) написаны таким образом. Это имеет смысл, потому что они, как правило, не обновляются, не редактируются и не поддерживаются иным образом очень часто, но они вызываются повсеместно из огромного количества программ. Только есть смысл сделать их максимально быстрыми даже за счет некоторой ремонтопригодности. - person Tyler McHenry; 04.07.2010

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

Именно в этом разница между хорошо отлаженным продуктом и прототипом NIH.

person Pavel Radzivilovsky    schedule 04.07.2010
comment
Здесь не придумано, как в пользовательском специальном коде, в качестве альтернативы популярному стороннему коду. - person Pavel Radzivilovsky; 04.07.2010
comment
Я имею в виду, что вы правы, но это ничего не объясняет, почему так много кода. Кто знает, может быть, кто-то другой написал реализацию, которая корректно преобразовывалась с вдвое меньшим количеством кода и вдвое большей функциональностью. - person ChaosPandion; 04.07.2010