Как обойти ограничение точности типа double в C#?

Question

[Сергей Виноградов]

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

x1 = 0.00000000000000030426102110965129;
x2 = 0.00000000000000030426102110965134;
Получаем x = 0.00000000000000030426102110965134

x1 = -0.000000000000000070906981940269862;
x2 = -0.000000000000000070906981940269849;
Получаем x = -0.000000000000000070906981940269862

Пытался преобразовывать значащие цифры в long получить (x1+x2) / 2 и преобразовывать обратно в double. Однако такой способ тоже в какие-то определенные моменты приводит к ошибкам + медленный (за счет вычисление степени числа). Может быть кто-нибудь знает как это проще выполнить?

2. Производится вычисление массива чисел. Каждый последующий элемент массива определенным образом зависит от всех предыдущих. В результате значения растут достаточно быстро с увеличением длины массива, и выходит за рамки ±1.7×10E308. В дальнейшем производится нормировка данного массива, т.е. A[i] / summa (A[i]^2, i=0..N-1) . Результирующий массив в рамки double, вообще говоря, помещается.
Есть какие-нибудь простые способы решения данной проблемы? Пока приходится использовать собственную структуру, представляющую из себя два числа int (степень) и double (значение от ~0.99 до ~9.99). Однако это очень пагубно влияет на общую производительность и, к тому же, крайне не удобно.
Так же быть может, кто-то знает простой способ получения значащих цифр и степени double? Ибо приходится либо циклом уменьшать/увеличивать число десятками и считать степень, либо использовать преобразование числа в строку, с последующим разбиением ее по 'E' и парсингом, что при этом, не исключает надобности первого варианта.

UPD:
В результате тестирования и обсуждения выяснилось следующее:
2. Решается только через созданный новый тип.
1. Собственный тип не поможет. При обратной конвертации все вернется назад. Но откуда растут ноги проблемы выяснить удалось.
Дело в том, что эти числа в двоичной записи различаются всего на 1 бит. И хоть ты тресни, но среднего значения никогда не получишь.
Пример:

x1 = 0.00000000000000030426102110965129;
Получив массив байт значения имеем:
119 95 82 12 160 236 181 60
x2 = 0.00000000000000030426102110965134;
Аналогично:
120 95 82 12 160 236 181 60

Что делать в такой ситуации абсолютно не понятно.

Answer 1

[Deerenaros]

Так. Стойте.

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

Как вариант, можно использовать BigInteger и хранить запятую отдельным числом, можно тоже BigInteger. По сути - запятая это показатель степени при основании системы исчисления, то есть 10. Арифметика элементарная.

Есть тысячи реализаций (включая BigRational в C# F#).

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

Comments

[Сергей Виноградов]

Спасибо за ссылки! Буду искать наилучший результат.

Answer 2

[Алексей Кулаков]

1) Есть тип Decimal. Можете попробовать его. У него точность побольше будет чем у double. Если нужно еще больше, то вам уже нужно реализовывать математику больших чисел.

Comments

[Сергей Виноградов]

decimal использовать пытался. Но при преобразовании из double замечена пропажа нескольких последних цифр.
Может быть Вы знаете, где посмотреть подобную реализацию или описание? И как сильно это сказывается на производительности?

[aush]

В decimal точность не теряется, в дабле - теряется. У вас входные данные - не дабл, вот и не используется его, а сразу работаейте с decimal.

[Сергей Виноградов]

@aush decimal (От -7,9 x 10Е28 до 7,9 x 10Е28) / (10Е(0–28)) Так что вполне себе теряется.
Пример:
в double 0.000000000000000070906981940269849
в decimal 0.0000000000000000709069819403

К тому же переходить на decimal достаточно проблематично из-за совместимости и большим объемом занимаемой памяти.

[Алексей Кулаков]

@genl3 с дробными числами там все как-то хитро в компьютерах.была статья на хабре про это.

Про реализацию не знаю. в .Net есть только реализация целых чисел достаточно больших. класс BigInteger называется. а вот дробные придется реализовывать вручную. По моему правильно это называется "Длинная арифметика". Гугл вам подскажет думаю.

[Сергей Виноградов]

@carbon88 То-то и оно, что все хитро. А доступа к ASMу или к битам памяти в C# нет (или я чего-то не знаю?).
Спасибо, поищу.

[Алексей Кулаков]

@genI3 можно задать через конструстор с 3-мя int параметрами, парметром знака и параметром степени 10. а еще можно вписать через литерал как decimal dec = 0.99999999999999999999999999999m

[Алексей Кулаков]

@genI3 так доступа и не надо, decimal внутри тоже на встроенных типах работает.

[Сергей Виноградов]

@carbon88 Сейчас у меня почти так же и реализовано с двумя параметрами (int и double). По поводу "вписать через литерал как decimal" не понял.

[Алексей Кулаков]

вы надеюсь знаете что можно определять тип числа с помощью суффиксов. например, 100f это float, 100d это double, а вот 100m это будет decimal.

[Сергей Виноградов]

@carbon88 я имел в виду получение битового представления числа в памяти для вытаскивания значения и степени.

[Сергей Виноградов]

@carbon88 Безусловно ) Но смысл фразы все равно не доходит.

[Алексей Кулаков]

ладно, проехали с литералами. ) вам не нужно иметь доступ к памяти. вам нужно подобно decimal сделать. там внутри есть 3 32-битных числа и смещение дробной части, ну еще и знак. вот вам нужно просто так же сделать только взять не 3 32-битных числа, а сколько угодно и точность какую угодно можно взять. в исходники decimal можно подглядеть с помощью определенных средств.

[Сергей Виноградов]

@carbon88 Мда. Видимо иначе не выйдет, а я надеялся. Так-то написана уже структура мной, которая решает эту проблему. Я надеялся на более простой случай. Т.к. производительность сильно падает в этом случае..
В вот с этого по подробнее, пожалуйста. Как посмотреть исходники decimal? И можно ли таким же способом посмотреть исходники других типов (их методов), в частности, интересует Double.ToString().

[Сергей Виноградов]

@carbon88 Мда.. Судя по тому, что я разглядел в сорцах. Наилучший выход создавать внешнюю dll на C. Бида, пичаль.

Answer 3

[Denis Morozov]

создайте свой тип данных комплексный

пусть хранит два числа double(число например 1.5) и int(число 9 например, что означает 1.5/(10^9))

т.е. что (1.5, 9) == 0.0000000015

делите, складывайте и т.д. их

Comments

[Сергей Виноградов]

Читайте внимательнее. На данный момент так и реализовано.

Answer 4

[Killy]

2) ideone.com/YjX5k6 или stackoverflow.com/questions/389993/extracting-mant...

1) Можно ли модифицировать алгоритм так, чтобы вычисления проводились в условных координатах от 0.0 до 1.0 (например), вместо реальных x1 .. x2, и затем вычислить реальное x любым медленным способом?

Comments

[Сергей Виноградов]

1) К сожалению такая модификация не возможна.
2) Спасибо, учту. Нужно посмотреть будет ли это быстрее обработки строки в моем варианте:

string[] str = ((-2.0786).ToString()).Split(new char[] {'E'});
double mant = double.Parse(str[0]);
int ord = int.Parse(str[1]);

Что все равно решает только часть проблемы.

Answer 5

[BigObfuscator]

Что делать в такой ситуации абсолютно не понятно.

А вы преобразуйте уравнение так, что бы плохо обусловленный участок стал хорошо обусловленным (кстати это называется регуляризацией).
Например по формуле x' = 1/(x - x1)