Каков хороший способ округлить значения с двойной точностью до (несколько) более низкой точности?

Моя проблема в том, что я должен использовать стороннюю функцию / алгоритм, который принимает в качестве входных данных массив значений двойной -точности, но, по-видимому, может быть чувствителен к очень небольшим изменениям входных данных. Однако для моего приложения я должен получить идентичные результаты для (почти) идентичных входов! В частности, у меня есть два тестовых входных массива, которые идентичны до 5-й позиции после десятичной точки, и все же я получаю разные результаты. Итак, что вызывает «проблему», должно быть после 5-й позиции после десятичной точки.

Теперь моя идея заключалась в том, чтобы округлить ввод до немного меньшей точности, чтобы получить идентичные результаты от ввода, которые очень похожи, но не на 100% идентичны. Поэтому я ищу хороший / эффективный способ округления значений double -precision до немного более низкой точности. Пока я использую этот код для округления до 9-й позиции после десятичной точки:

double x = original_input();
x = double(qRound(x * 1000000000.0)) / 1000000000.0;

Здесь qRound () - это обычная функция округления двойного до целого числа из Qt. Этот код работает, и он действительно решил мою проблему с двумя «проблемными» наборами тестов. Но: есть ли более эффективный способ сделать это?

Также меня беспокоит: округление до 9-й позиции после десятичной точки может быть разумным для входных данных, которые находятся в диапазоне от -100,0 до 100,0 (как в случае с моими текущими входными данными). Но это может быть слишком много (т.е. слишком большая потеря точности) для входных данных, например, в диапазоне от -0,001 до 0,001. К сожалению, я не знаю, в каком диапазоне будут мои входные значения в других случаях ...

В конце концов, я думаю, что мне понадобится что-то вроде функции, которая выполняет следующие действия: Отсекает путем правильного округления заданное значение двойной -точности X до не более чем LN позиций после десятичная точка, где L - количество позиций после десятичной точки, которое double -precision может сохранить (представить) для данного значения; и N фиксировано, например 3. Это означает, что для «маленьких» значений мы разрешили бы больше позиций после десятичной точки, чем для «больших» значений. Другими словами, я хотел бы округлить 64-битное значение с плавающей запятой до (несколько) меньшей точности, например 60-битной или 56-битной, а затем сохранить его обратно до 64-битного значения двойной точности.

Это имеет для вас смысл? И если да, то можете ли вы предложить способ сделать это (эффективно) на C ++ ???

Заранее спасибо!


c++ rounding floating-point-precision
person MuldeR    schedule 04.01.2013    source источник
comment
Вы хотите округлить его по основанию 10 или по основанию 2 тоже подойдет?   -  person    schedule 04.01.2013
comment
Привет, я думаю, что base-2 тоже подойдет, если он адаптируется к вводу.   -  person MuldeR    schedule 04.01.2013
comment
Идея в корне ошибочна. Все числа почти идентичны в том смысле, что 1.00 почти идентична 1.01, а 1.01 почти идентична 1.02 и т. Д. Таким образом, если f(1.00) == f(1.01) и f(1.01)==f(1.02), то также f(1.00)==f(1.02), а также f(1.00)==f(1E7)   -  person MSalters    schedule 04.01.2013
comment
MSalters, я понимаю о чем вы. Конечно, на самом деле то, что я делаю, - это квантование входных значений в несколько ячеек, где каждая ячейка охватывает определенный диапазон входных значений (с ячейками, расширяющимися для больших значений). Наконец, я заменяю значение средним значением его корзины. По-прежнему может случиться так, что два значения очень близки, но одно значение оказывается слева от границы, а другое - справа от границы. Наверное, дело, с которым мне нужно жить. Или у вас есть лучшие предложения, как с этим справиться?   -  person MuldeR    schedule 04.01.2013
comment
Округление не решает описанной вами проблемы. Я буду использовать десятичную дробь для упрощения иллюстрации. Предположим, у вас есть два результата, которые, как вы ожидаете, будут идентичными, 10,22 и 10,24, и вы округлите их до трех цифр, получив 10,2 и 10,2. Они идентичны, и все в порядке. Однако, если результаты были 10,24 и 10,26, то их округление дает 10,2 и 10,3, и они не идентичны. Округление не приведет к тому, что близкие, но неидентичные результаты будут идентичными при отсутствии какой-либо другой спецификации, например, если все результаты находятся рядом с центрами интервалов округления, а не рядом с границами.   -  person Eric Postpischil    schedule 12.01.2013
comment
Тем не менее, если вы хотите округлить, я покажу эффективный способ сделать это, алгоритм Деккера, в этом ответе.   -  person Eric Postpischil    schedule 12.01.2013

Ответы (4)


arrow_upward
1
arrow_downward

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

SEEEEEEEEEEEFFFFFFFFFFF.......FFFFFFFFFF

где S - знаковый бит, E - это биты экспоненты, а F - дробные биты. Вы можете сделать такую ​​битовую маску:

11111111111111111111111.......1111000000

и побитовое - и (&) два вместе. Результатом является округленная версия исходного ввода:

SEEEEEEEEEEEFFFFFFFFFFF.......FFFF000000

И вы можете контролировать, сколько данных обрезается, изменяя количество нулей в конце. Больше нулей = больше округлений; меньше = меньше. Вы также получаете другой эффект, который вам нужен: на малые входные значения влияют пропорционально меньше, чем на большие входные значения, так как «место», которому соответствует каждый бит, определяется показателем степени.

Надеюсь, это поможет!

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

person Xavier Holt    schedule 04.01.2013
comment
Спасибо, Ксавьер. Это могло бы быть решением. Но как именно выполнить эту битовую операцию в коде C ++? Преобразовать двойное значение в беззнаковый указатель char *? Мне нужно заботиться о порядке байтов? - person MuldeR; 04.01.2013
comment
@MuldeR - Вероятно, это лучший способ сделать это. Я немного огляделся, и нет ничего особенно удобного ... Есть еще хак Union - люди здесь любят указывать, что это технически неопределенное поведение, но оно должно работать на всех основных компиляторах. - person Xavier Holt; 04.01.2013
comment
Единственный законный способ выполнить приведение - выполнить memcpy от двойного к целому (и обратно). Наблюдение за типом и хакерство с объединением - это неопределенное поведение. Версия memcpy может быть обернута в шаблон byte_cast ‹› - person Joe; 07.06.2013

arrow_upward
1
arrow_downward

Спасибо за ваш вклад.

Однако после еще нескольких поисков я наткнулся на функции frexp () и ldexp ()! Эти функции предоставляют мне доступ к «мантиссе» и «экспоненте» данного двойного значения, а также могут преобразовывать обратно из мантиссы + экспоненты в двойной. Теперь мне просто нужно округлить мантиссу.

double value = original_input();
static const double FACTOR = 32.0;
int exponent;
double temp = double(round(frexp(value, &exponent) * FACTOR));
value = ldexp(temp / FACTOR, exponent);

Не знаю, насколько это эффективно, но дает разумные результаты:

0.000010000000000   0.000009765625000
0.000010100000000   0.000010375976563
0.000010200000000   0.000010375976563
0.000010300000000   0.000010375976563
0.000010400000000   0.000010375976563
0.000010500000000   0.000010375976563
0.000010600000000   0.000010375976563
0.000010700000000   0.000010986328125
0.000010800000000   0.000010986328125
0.000010900000000   0.000010986328125
0.000011000000000   0.000010986328125
0.000011100000000   0.000010986328125
0.000011200000000   0.000010986328125
0.000011300000000   0.000011596679688
0.000011400000000   0.000011596679688
0.000011500000000   0.000011596679688
0.000011600000000   0.000011596679688
0.000011700000000   0.000011596679688
0.000011800000000   0.000011596679688
0.000011900000000   0.000011596679688
0.000012000000000   0.000012207031250
0.000012100000000   0.000012207031250
0.000012200000000   0.000012207031250
0.000012300000000   0.000012207031250
0.000012400000000   0.000012207031250
0.000012500000000   0.000012207031250
0.000012600000000   0.000012817382813
0.000012700000000   0.000012817382813
0.000012800000000   0.000012817382813
0.000012900000000   0.000012817382813
0.000013000000000   0.000012817382813
0.000013100000000   0.000012817382813
0.000013200000000   0.000013427734375
0.000013300000000   0.000013427734375
0.000013400000000   0.000013427734375
0.000013500000000   0.000013427734375
0.000013600000000   0.000013427734375
0.000013700000000   0.000013427734375
0.000013800000000   0.000014038085938
0.000013900000000   0.000014038085938
0.000014000000000   0.000014038085938
0.000014100000000   0.000014038085938
0.000014200000000   0.000014038085938
0.000014300000000   0.000014038085938
0.000014400000000   0.000014648437500
0.000014500000000   0.000014648437500
0.000014600000000   0.000014648437500
0.000014700000000   0.000014648437500
0.000014800000000   0.000014648437500
0.000014900000000   0.000014648437500
0.000015000000000   0.000015258789063
0.000015100000000   0.000015258789063
0.000015200000000   0.000015258789063
0.000015300000000   0.000015869140625
0.000015400000000   0.000015869140625
0.000015500000000   0.000015869140625
0.000015600000000   0.000015869140625
0.000015700000000   0.000015869140625
0.000015800000000   0.000015869140625
0.000015900000000   0.000015869140625
0.000016000000000   0.000015869140625
0.000016100000000   0.000015869140625
0.000016200000000   0.000015869140625
0.000016300000000   0.000015869140625
0.000016400000000   0.000015869140625
0.000016500000000   0.000017089843750
0.000016600000000   0.000017089843750
0.000016700000000   0.000017089843750
0.000016800000000   0.000017089843750
0.000016900000000   0.000017089843750
0.000017000000000   0.000017089843750
0.000017100000000   0.000017089843750
0.000017200000000   0.000017089843750
0.000017300000000   0.000017089843750
0.000017400000000   0.000017089843750
0.000017500000000   0.000017089843750
0.000017600000000   0.000017089843750
0.000017700000000   0.000017089843750
0.000017800000000   0.000018310546875
0.000017900000000   0.000018310546875
0.000018000000000   0.000018310546875
0.000018100000000   0.000018310546875
0.000018200000000   0.000018310546875
0.000018300000000   0.000018310546875
0.000018400000000   0.000018310546875
0.000018500000000   0.000018310546875
0.000018600000000   0.000018310546875
0.000018700000000   0.000018310546875
0.000018800000000   0.000018310546875
0.000018900000000   0.000018310546875
0.000019000000000   0.000019531250000
0.000019100000000   0.000019531250000
0.000019200000000   0.000019531250000
0.000019300000000   0.000019531250000
0.000019400000000   0.000019531250000
0.000019500000000   0.000019531250000
0.000019600000000   0.000019531250000
0.000019700000000   0.000019531250000
0.000019800000000   0.000019531250000
0.000019900000000   0.000019531250000
0.000020000000000   0.000019531250000
0.000020100000000   0.000019531250000

Кажется, мне все-таки понравилось то, что я искал:

http://img833.imageshack.us/img833/9055/clipboard09.png

Теперь мне просто нужно найти подходящее значение ФАКТОРА для моей функции ....

Есть комментарии или предложения?

person MuldeR    schedule 04.01.2013
comment
Мне нужно точно так же, тоже в базе 2, но на C #. Надеюсь, я смогу найти аналогичные способы возиться с битами двойной точности в C #, как и в C ++. - person Paul Chernoch; 11.01.2013

arrow_upward
1
arrow_downward

Бизнес-сценарий не очевиден из вопроса; тем не менее, я чувствую, что вы пытаетесь увидеть, что значения находятся в приемлемом диапазоне. Вместо == вы можете проверить, находится ли второе значение в определенном процентном диапазоне (скажем, +/- 0,001%)

Если процент диапазона не может быть зафиксирован (среднее значение зависит от длины точности; скажем, для 2 десятичных знаков 0,001 процента подходит, но для 4 десятичных знаков требуется 0,000001 процента), вы можете получить его с точностью 1 / мантисса.

person abygm    schedule 07.06.2013

arrow_upward
0
arrow_downward

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

Представьте себе число с плавающей запятой в двоичном представлении. Например 1101.101. Биты 1101 представляют собой неотъемлемую часть числа и взвешиваются по 2^3, 2^2, 2^1, 2^0 слева направо. Биты 101 дробной части имеют весовые коэффициенты 2^-1, 2^-2, 2^-3, что равняется 1/2, 1/4, 1/8.

Так что же такое десятичная ошибка, которую вы производите, когда отрезаете свое число на два бита после десятичной точки? В этом примере это 0.125, поскольку бит установлен. Если бит не будет установлен, ошибка будет 0. Итак, ошибка <= 0.125.

Теперь подумайте в более общем плане: если бы у вас была бесконечно длинная мантисса, дробная часть сходится к 1 (см. Здесь). На самом деле у вас всего 52 бита (см. здесь), поэтому сумма будет" почти "1. Таким образом, отключение всех дробных битов вызовет ошибку <= 1, что на самом деле не является сюрпризом! (Имейте в виду, что ваша составная часть также занимает пространство мантиссы! Но если вы предположите число, подобное 1.5, которое равно 1.1 в двоичном представлении, ваша мантисса сохранит только часть после десятичной точки.)

Поскольку отсечение всех дробных битов вызывает ошибку <= 1, отсечение всех, кроме первого бита справа от десятичной точки, вызывает ошибку <= 1/2, потому что этот бит имеет весовой коэффициент 2^-1. Если вы сохраните еще один бит, ваша ошибка уменьшится до <= 1/4.

Это можно описать функцией f(x) = 1/2^(52-x), где x - это количество отсеченных битов, отсчитываемых с правой стороны, а y = f(x) - это верхняя граница вашей результирующей ошибки.

Округление на два знака после десятичной точки означает «группировку» чисел по общим сотым. Это можно сделать с помощью указанной выше функции: 1/100 >= 1/2^(52-x). Это означает, что ваша результирующая ошибка ограничена сотой долей при отсечении x бит. Решение этого неравенства по x дает: 52-log2(100) >= x, где 52-log2(100) равно 45.36. Это означает, что отсечение не более чем 45 битов обеспечивает "точность" двух десятичных (!) Позиций после числа с плавающей запятой.

В общем, ваша мантисса состоит из целой и дробной части. Назовем их длины i и f. Положительные показатели описывают i. Тем более что 52=f+i держится. Решение приведенного выше неравенства меняется на: 52-i-log2(10^n) >= x, потому что после того, как ваша дробная часть закончилась, вы должны перестать обрезать мантиссу! (n - это десятичная точность здесь.)

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

x = f - (uint16_t) ceil(n / 0.3010299956639812);, где константа представляет log10(2). Затем можно выполнить усечение с помощью:

mantissa >>= x; mantissa <<= x;

Если x больше f, не забудьте сдвигать только на f. В противном случае вы повлияете на составную часть своей мантиссы.

person lukasl1991    schedule 15.05.2019