Как вы печатаете точное значение числа с плавающей запятой?

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

Тем не менее, каждое возможное значение с плавающей запятой в точности соответствует диадическому рациональному числу p/q где q является степенью 2), которая в свою очередь имеет точное десятичное представление.

Мой вопрос: как вы находите это точное десятичное представление эффективно? sprintf и подобные функции обычно указываются с точностью до числа значащих цифр, чтобы однозначно определить исходное значение с плавающей запятой; они не обязательно печатают точное десятичное представление. Я знаю один алгоритм, который я использовал, но он очень медленный, O(e^2) где e это показатель. Вот схема:

  1. Преобразуйте мантиссу в десятичное целое число. Вы можете сделать это, разделив биты для непосредственного чтения мантиссы, или вы можете написать грязный цикл с плавающей запятой, который сначала умножает значение на степень два, чтобы поместить его в диапазон 1<=x<10, а затем вытягивает от цифры за раз, приведение к int, вычитание и умножение на 10.
  2. Примените показатель степени, многократно умножив или разделив на 2. Это операция над строкой десятичных цифр, которую вы сгенерировали. Каждое ~3 умножения добавит дополнительную цифру слева. Каждое отдельное деление добавит дополнительную цифру справа.

Это действительно лучшее из возможных? Я сомневаюсь в этом, но я не эксперт с плавающей запятой, и я не могу найти способ выполнить вычисления base-10 для представления числа с плавающей запятой, не столкнувшись с возможностью получения неточных результатов (умножение или деление на все, кроме степени 2, является операцией с потерями для чисел с плавающей запятой, если только вы не знаете, что у вас есть свободные биты для работы).

Источник

10 ответов

Решение

Этот вопрос имеет бюрократическую и алгоритмическую части. Число с плавающей запятой хранится внутри как (2 e × m), где e - показатель степени (сам в двоичном виде), а m - мантисса. Бюрократическая часть вопроса заключается в том, как получить доступ к этим данным, но Р., похоже, больше интересует алгоритмическая часть вопроса, а именно преобразование (2 e × m) в дробь (a/b) в десятичной форме. Ответ на бюрократический вопрос на нескольких языках - "frexp" (интересная деталь, которую я не знал до сегодняшнего дня).

Это правда, что на первый взгляд требуется O (e 2), чтобы написать 2 e в десятичном виде, и еще больше времени для мантиссы. Но, благодаря волшебству алгоритма быстрого умножения Шонхаге-Штрассена, вы можете сделать это за Õ(e) времени, где тильда означает "до логарифмических факторов". Если вы рассматриваете Schonhage-Strassen как магию, то не так сложно думать о том, что делать. Если e чётно, вы можете рекурсивно вычислить 2 e / 2, а затем возвести его в квадрат, используя быстрое умножение. С другой стороны, если e нечетно, вы можете рекурсивно вычислить 2 e-1 и затем удвоить его. Вы должны быть осторожны, чтобы проверить, есть ли версия Schonhage-Strassen в базе 10. Хотя это не широко задокументировано, это может быть сделано в любой базе.

Преобразование очень длинной мантиссы из двоичной в основание 10 - это не совсем тот же вопрос, но на него есть аналогичный ответ. Вы можете разделить мантиссу на две половины, m = a 2 k + b. Затем рекурсивно преобразуйте a и b в основание 10, преобразовайте 2^k в основание 10 и выполните другое быстрое умножение для вычисления m в основании 10.

Абстрактный результат всего этого заключается в том, что вы можете конвертировать целые числа из одной базы в другую за время Õ(N).

Если вопрос касается стандартных 64-битных чисел с плавающей запятой, то он слишком мал для причудливого алгоритма Шонхаге-Штрассена. В этом диапазоне вы можете вместо этого сохранить работу с различными трюками. Один из подходов состоит в том, чтобы сохранить все 2048 значений 2 e в справочной таблице, а затем работать в мантиссе с асимметричным умножением (между длинным умножением и коротким умножением). Другой трюк заключается в работе на базе 10000 (или более высокой степени 10, в зависимости от архитектуры) вместо базы 10. Но, как указывает Р. в комментариях, 128-битные числа с плавающей запятой уже позволяют достаточно большим показателям вызывать вопрос и таблицы поиска и стандартное длинное умножение. На практике длинное умножение является самым быстрым, вплоть до нескольких цифр, затем в значительном среднем диапазоне можно использовать умножение Карацубы или умножение Тоом-Кука, и после этого вариация Шонхаге-Штрассена лучше не только теоретически. но и на практике.

На самом деле, большой целочисленный пакет GMP уже имеет radi (N) преобразование радиуса времени, а также хорошую эвристику, для которой выбирается алгоритм умножения. Единственное различие между их решением и моим состоит в том, что вместо выполнения какой-либо большой арифметики в базе 10 они вычисляют большие степени 10 в базе 2. В этом решении им также необходимо быстрое деление, но это можно получить из быстрого умножения в любом из нескольких способов.

Источник

Я вижу, что вы уже приняли ответ, но вот пара реализаций этого преобразования с открытым исходным кодом, на которые вы можете посмотреть:

  1. Дэвид Гэй dtoa() функция в dtoa.c ( http://www.netlib.org/fp/dtoa.c).

  2. Функция ___printf_fp() в файле /stdio-common/printf_fp.c в glibc (например, http://ftp.gnu.org/gnu/glibc/glibc-2.11.2.tar.gz).

Оба будут печатать столько цифр, сколько вы просите в %f тип printf (как я уже писал здесь: http://www.exploringbinary.com/print-precision-of-dyadic-fractions-varies-by-language/ и http://www.exploringbinary.com/print-precision-of-floating-point-integers-varies-too/).

Источник

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

Источник

Хотя это C# и ваш вопрос помечен C, у Джона Скита есть код для преобразования double его точное представление в виде строки: http://www.yoda.arachsys.com/csharp/DoubleConverter.cs

На первый взгляд кажется, что портирование на C не так уж сложно, и даже легче писать на C++.

При дальнейшем размышлении выясняется, что алгоритм Джона также является O(e^2), поскольку он также проходит по показателю степени. Однако это означает, что алгоритм равен O(log(n)^2) (где n - число с плавающей запятой), и я не уверен, что вы можете преобразовать из базы 2 в базу 10 быстрее, чем время в квадрате логарифма.

Источник

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

GNU MPFR - хороший вариант.

Библиотека MPFR - это библиотека C для вычислений с плавающей точкой с множественной точностью и правильным округлением. Основная цель MPFR - предоставить библиотеку для вычислений с плавающей точкой с множественной точностью, которая является одновременно эффективной и имеет четко определенную семантику.

Источник

sprintf и подобные функции обычно указываются с точностью до числа значащих цифр, чтобы однозначно определить исходное значение с плавающей запятой; они не обязательно печатают точное десятичное представление.

Вы можете запросить более значимые цифры, чем по умолчанию:

printf("%.100g\n", 0.1);

печать 0.1000000000000000055511151231257827021181583404541015625,

Источник

Есть 3 способа

  1. печать номеров в bin или же hex

    Это самый точный способ. я предпочитаю hex потому что это больше похоже на базу 10 для чтения / чувствую, например, F.8h = 15.5 Здесь нет потери точности.

  2. печать в dec но только соответствующие цифры

    Я имею в виду только те цифры, которые могут иметь 1 в вашем номере представлены как можно ближе.

    num из целых чисел легко и точно (без потери точности):

    // n10 - base 10 integer digits
// n2  - base 2 integer digits
n10=log10(2^n2)
n10=log2(2^n2)/log2(10)
n10=n2/log2(10)
n10=ceil(n2*0.30102999566398119521373889472449)
// if fist digit is 0 and n10 > 1 then n10--

    num дробные цифры более хитры и эмпирически я нашел это:

    // n10 - base 10 fract. digits
// n2  - base 2 fract. digits >= 8
n10=0; if (n02==8) n10=1;
else if (n02==9) n10=2;
else if (n02> 9)
    {
    n10=((n02-9)%10);
         if (n10>=6) n10=2;
    else if (n10>=1) n10=1;
    n10+=2+(((n02-9)/10)*3);
    }

    если вы делаете таблицу зависимостей n02 <-> n10 тогда вы видите эту константу 0.30102999566398119521373889472449 все еще присутствует, но при запуске из 8 бит, потому что меньше не может представлять 0.1 с удовлетворительной точностью (0.85 - 1.15). из-за отрицательных показателей базы 2 зависимость не линейная, а паттерны. Этот код работает для небольшого количества бит (<=52) но при большем количестве бит может быть ошибка, потому что используемый шаблон не подходит log10(2) или же 1/log2(10) именно так.

    для большего количества битов я использую это:

    n10=7.810+(9.6366363636363636363636*((n02>>5)-1.0));

    но эта формула выровнена на 32 бита!!! а также большая ошибка объявления количества битов к нему

    PS дальнейший анализ двоичного представления десятичных чисел

    0.1
0.01
0.001
0.0001
...

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

    для ясности:

    8 bin digits -> 1 dec digits
9 bin digits -> 2 dec digits
10 bin digits -> 3 dec digits
11 bin digits -> 3 dec digits
12 bin digits -> 3 dec digits
13 bin digits -> 3 dec digits
14 bin digits -> 3 dec digits
15 bin digits -> 4 dec digits
16 bin digits -> 4 dec digits
17 bin digits -> 4 dec digits
18 bin digits -> 4 dec digits
19 bin digits -> 5 dec digits
20 bin digits -> 6 dec digits
21 bin digits -> 6 dec digits
22 bin digits -> 6 dec digits
23 bin digits -> 6 dec digits
24 bin digits -> 6 dec digits
25 bin digits -> 7 dec digits
26 bin digits -> 7 dec digits
27 bin digits -> 7 dec digits
28 bin digits -> 7 dec digits
29 bin digits -> 8 dec digits
30 bin digits -> 9 dec digits
31 bin digits -> 9 dec digits
32 bin digits -> 9 dec digits
33 bin digits -> 9 dec digits
34 bin digits -> 9 dec digits
35 bin digits -> 10 dec digits
36 bin digits -> 10 dec digits
37 bin digits -> 10 dec digits
38 bin digits -> 10 dec digits
39 bin digits -> 11 dec digits
40 bin digits -> 12 dec digits
41 bin digits -> 12 dec digits
42 bin digits -> 12 dec digits
43 bin digits -> 12 dec digits
44 bin digits -> 12 dec digits
45 bin digits -> 13 dec digits
46 bin digits -> 13 dec digits
47 bin digits -> 13 dec digits
48 bin digits -> 13 dec digits
49 bin digits -> 14 dec digits
50 bin digits -> 15 dec digits
51 bin digits -> 15 dec digits
52 bin digits -> 15 dec digits
53 bin digits -> 15 dec digits
54 bin digits -> 15 dec digits
55 bin digits -> 16 dec digits
56 bin digits -> 16 dec digits
57 bin digits -> 16 dec digits
58 bin digits -> 16 dec digits
59 bin digits -> 17 dec digits
60 bin digits -> 18 dec digits
61 bin digits -> 18 dec digits
62 bin digits -> 18 dec digits
63 bin digits -> 18 dec digits
64 bin digits -> 18 dec digits

    И наконец не забудьте округлить срезанные цифры!!! Это означает, что цифра после последней соответствующей цифры >=5 в декабре, чем последняя соответствующая цифра должна быть +1... и если это уже 9 чем вы должны перейти к предыдущей цифре и так далее...

  3. вывести точное значение

    Чтобы вывести точное значение дробного двоичного числа, просто выведите дробное n цифры где n является числом дробных битов, потому что представленное значение является суммой этих значений, поэтому число дробных десятичных знаков не может быть больше, чем num дробных цифр LSB. Материал выше (пункт 2) имеет отношение к сохранению десятичного числа в float (или печать только соответствующих десятичных знаков).

    отрицательные степени двух точных значений...

    2^- 1 = 0.5
2^- 2 = 0.25
2^- 3 = 0.125
2^- 4 = 0.0625
2^- 5 = 0.03125
2^- 6 = 0.015625
2^- 7 = 0.0078125
2^- 8 = 0.00390625
2^- 9 = 0.001953125
2^-10 = 0.0009765625
2^-11 = 0.00048828125
2^-12 = 0.000244140625
2^-13 = 0.0001220703125
2^-14 = 0.00006103515625
2^-15 = 0.000030517578125
2^-16 = 0.0000152587890625
2^-17 = 0.00000762939453125
2^-18 = 0.000003814697265625
2^-19 = 0.0000019073486328125
2^-20 = 0.00000095367431640625

    теперь отрицательные силы 10 печатается с точным значением стиля для 64 бит doubles:

    10^+ -1 = 0.1000000000000000055511151231257827021181583404541015625
        = 0.0001100110011001100110011001100110011001100110011001101b
10^+ -2 = 0.01000000000000000020816681711721685132943093776702880859375
        = 0.00000010100011110101110000101000111101011100001010001111011b
10^+ -3 = 0.001000000000000000020816681711721685132943093776702880859375
        = 0.000000000100000110001001001101110100101111000110101001111111b
10^+ -4 = 0.000100000000000000004792173602385929598312941379845142364501953125
        = 0.000000000000011010001101101110001011101011000111000100001100101101b
10^+ -5 = 0.000010000000000000000818030539140313095458623138256371021270751953125
        = 0.000000000000000010100111110001011010110001000111000110110100011110001b
10^+ -6 = 0.000000999999999999999954748111825886258685613938723690807819366455078125
        = 0.000000000000000000010000110001101111011110100000101101011110110110001101b
10^+ -7 = 0.0000000999999999999999954748111825886258685613938723690807819366455078125
        = 0.0000000000000000000000011010110101111111001010011010101111001010111101001b
10^+ -8 = 0.000000010000000000000000209225608301284726753266340892878361046314239501953125
        = 0.000000000000000000000000001010101111001100011101110001000110000100011000011101b
10^+ -9 = 0.0000000010000000000000000622815914577798564188970686927859787829220294952392578125
        = 0.0000000000000000000000000000010001001011100000101111101000001001101101011010010101b
10^+-10 = 0.00000000010000000000000000364321973154977415791655470655996396089904010295867919921875
        = 0.00000000000000000000000000000000011011011111001101111111011001110101111011110110111011b
10^+-11 = 0.00000000000999999999999999939496969281939810930172340963650867706746794283390045166015625
        = 0.00000000000000000000000000000000000010101111111010111111111100001011110010110010010010101b
10^+-12 = 0.00000000000099999999999999997988664762925561536725284350612952266601496376097202301025390625
        = 0.00000000000000000000000000000000000000010001100101111001100110000001001011011110101000010001b
10^+-13 = 0.00000000000010000000000000000303737455634003709136034716842278413651001756079494953155517578125
        = 0.00000000000000000000000000000000000000000001110000100101110000100110100001001001011101101000001b
10^+-14 = 0.000000000000009999999999999999988193093545598986971343290729163921781719182035885751247406005859375
        = 0.000000000000000000000000000000000000000000000010110100001001001101110000110101000010010101110011011b
10^+-15 = 0.00000000000000100000000000000007770539987666107923830718560119501514549256171449087560176849365234375
        = 0.00000000000000000000000000000000000000000000000001001000000011101011111001111011100111010101100001011b
10^+-16 = 0.00000000000000009999999999999999790977867240346035618411149408467364363417573258630000054836273193359375
        = 0.00000000000000000000000000000000000000000000000000000111001101001010110010100101111101100010001001101111b
10^+-17 = 0.0000000000000000100000000000000007154242405462192450852805618492324772617063644020163337700068950653076171875
        = 0.0000000000000000000000000000000000000000000000000000000010111000011101111010101000110010001101101010010010111b
10^+-18 = 0.00000000000000000100000000000000007154242405462192450852805618492324772617063644020163337700068950653076171875
        = 0.00000000000000000000000000000000000000000000000000000000000100100111001001011101110100011101001001000011101011b
10^+-19 = 0.000000000000000000099999999999999997524592683526013185572915905567688179926555402943222361500374972820281982421875
        = 0.000000000000000000000000000000000000000000000000000000000000000111011000001111001001010011111011011011010010101011b
10^+-20 = 0.00000000000000000000999999999999999945153271454209571651729503702787392447107715776066783064379706047475337982177734375
        = 0.00000000000000000000000000000000000000000000000000000000000000000010111100111001010000100001100100100100100001000100011b

    теперь отрицательные степени 10 печатаются только в стиле десятичных цифр (я к этому привык) для 64-битных doubles:

    10^+ -1 = 0.1
10^+ -2 = 0.01
10^+ -3 = 0.001
10^+ -4 = 0.0001
10^+ -5 = 0.00001
10^+ -6 = 0.000001
10^+ -7 = 0.0000001
10^+ -8 = 0.00000001
10^+ -9 = 0.000000001
10^+-10 = 0.0000000001
10^+-11 = 0.00000000001
10^+-12 = 0.000000000001
10^+-13 = 0.0000000000001
10^+-14 = 0.00000000000001
10^+-15 = 0.000000000000001
10^+-16 = 0.0000000000000001
10^+-17 = 0.00000000000000001
10^+-18 = 0.000000000000000001
10^+-19 = 0.0000000000000000001
10^+-20 = 0.00000000000000000001

    Надеюсь, поможет:)

Источник

Если вы хотите получить более точные результаты, почему бы не использовать математику с фиксированной точкой? Конверсии быстрые. Ошибка известна и может быть исправлена. Не точный ответ на ваш вопрос, но другая идея для вас.

Источник

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

Т.е.

10^2 = 2^6 + 2^5 + 2^2

Тогда сумма:

mantissa<<6 + mantissa<<5 + mantissa<<2

Я думаю, что разбить его будет на O(n) на количество цифр, сдвиг O(1), а сумма будет O (N) цифр...

Конечно, у вас должен быть достаточно большой целочисленный класс для хранения результатов...

Дайте мне знать - мне интересно об этом, это действительно заставило меня задуматься.:-)

Источник

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

Источник
Другие вопросы по тегам