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

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

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

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

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

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

Ответы

Ответ 1

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

Верно, что на первый взгляд требуется O (e ²) работать только для записи 2 ^e в десятичной форме и еще больше времени для мантиссы. Но, благодаря волшебству алгоритма быстрого умножения Schonhage-Strassen, вы можете сделать это в течение Õ (e), где тильда означает "до коэффициентов журнала". Если вы рассматриваете Шонхаге-Штрассена как волшебство, тогда не так уж сложно думать о том, что делать. Если 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-битные числа с плавающей запятой уже позволяют достаточно крупным экспонентам звонить в задайте как таблицы поиска, так и стандартное длинное умножение. В практическом плане длительное умножение является самым быстрым до нескольких цифр, тогда в значительном среднем диапазоне можно использовать умножение Карацубы или Умножение Toom-Cook, а затем после этого вариация Schonhage-Strassen лучше не только в теории, но и на практике.

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

Ответ 2

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

Функция David Gay dtoa() в dtoa.c (http://www.netlib.org/fp/dtoa.c).
Функция ___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/).

Ответ 3

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

Ответ 4

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

С быстрым взглядом, кажется, не слишком сложно переносить на C, а еще проще писать на С++.

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

Ответ 5

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

GNU MPFR является хорошим.

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

Ответ 6

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

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

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

выводит 0.1000000000000000055511151231257827021181583404541015625.

Ответ 7

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

Ответ 8

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

т.е.

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

Тогда сумма:

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

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

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

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

Ответ 9

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

номера печати в bin или hex

Это самый точный способ. Я предпочитаю hex, потому что он больше похож на базу 10 для чтения/ощущения, например, F.8h = 15.5 без потери точности здесь.
печать 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 бита!!! а также ошибка объявления большего количества бит в нем

P.S. дальнейший анализ двоичного представления декадических чисел
```
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, чем вы должны перейти к предыдущей цифре и т.д....

напечатать точное значение

Чтобы напечатать точное значение дробного двоичного числа , просто напечатайте дробные n цифры, где n - количество дробных битов, потому что представленное значение представляет собой сумму этих значений, поэтому число > дробные десятичные знаки не могут быть больше num дробных цифр LSB. Вещественное значение (bullet # 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

Нет. Самое близкое, что вы можете придумать, это сброс байтов.