Как справиться с умножением чисел, близких к 1

Question

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

Проблема в том, что в то время как у парных символов Java нет проблем с таким числом, как:

0.0000000000000000000000000000000001 (1.0E-34)

они не могут представлять что-то вроде:

1.0000000000000000000000000000000001

Следовательно, из-за этого я быстро теряю точность (кажется, что для двойников Java предел составляет около 1,000000000000001).

Я рассмотрел просто сохранение чисел с вычитаемым 1, поэтому, например, 1,0001 будет сохранено как 0,0001 - но проблема в том, что для их умножения снова нужно добавить 1, и в этот момент я теряю точность.

Чтобы решить эту проблему, я мог бы использовать BigDecimals для выполнения вычислений (преобразовать в BigDecimal, добавить 1,0, затем умножить), а затем преобразовать обратно в удвоения, но у меня есть серьезные опасения по поводу последствий для производительности.

Может кто-нибудь увидеть способ сделать это, избегая использования BigDecimal?

Правка для ясности : Это для крупномасштабного совместного фильтра, который использует алгоритм оптимизации градиентного спуска. Точность является проблемой, потому что часто фильтр совместной работы имеет дело с очень маленькими числами (например, вероятность того, что человек нажмет на объявление для продукта, которое может быть 1 на 1000 или 1 на 10000).

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

Answer 1

Да: потому что

(1 + x) * (1 + y) = 1 + x + y + x*y

В вашем случае x и y очень малы, поэтому x*y будет далеко меньше - слишком мало, чтобы влиять на результаты ваших вычислений. Итак, что касается вас,

(1 + x) * (1 + y) = 1 + x + y

Это означает, что вы можете хранить числа с 1 вычтенным, и вместо умножения, просто сложите их. До тех пор, пока результаты всегда намного меньше 1, они будут достаточно близки к математически точным результатам, и вы не будете заботиться о разнице.

РЕДАКТИРОВАТЬ : Только что заметил: вы говорите, большинство из них очень близки к 1. Очевидно, этот метод не будет работать для чисел, которые не близки к 1 - то есть если x и y большие. Но если один большой, а другой маленький, он все равно может сработать; Вы заботитесь только о величине продукта x*y. (И если оба числа не близки к 1, вы можете просто использовать обычное умножение Java double ...)

Answer 2

Возможно, вы могли бы использовать логарифмы?

Логарифмы удобно уменьшают умножение до сложения.

Кроме того, чтобы позаботиться о начальной потере точности, есть функция log1p (по крайней мере, она существует в C / C ++), которая возвращает log (1 + x) без потери точности. (например, log1p (1e-30) возвращает мне 1e-30)

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

Answer 3

Разве это не та ситуация, для которой предназначен BigDecimal?

Отредактировано, чтобы добавить:

"В последнем абзаце я предпочел бы избегать BigDecimals, если это возможно по соображениям производительности." - здравомыслие

«Преждевременная оптимизация - корень всего зла» - Кнут

Существует простое решение, практически на заказ для вашей проблемы. Вы обеспокоены тем, что это может быть недостаточно быстро, поэтому вы хотите сделать что-то сложное, чтобы вы думали, что будет быстрее. Цитата Кнута иногда используется слишком часто, но именно об этом он и предупреждал. Напишите это простым способом. Попробуй это. Профиль это. Посмотри, не слишком ли это медленно. Если это , тогда начинают думать о том, как сделать это быстрее. Не добавляйте весь этот дополнительный сложный, подверженный ошибкам код, пока не узнаете, что это необходимо.

Answer 4

Как указывает Дэвид, вы можете просто добавить смещения вверх.

(1 + x) * (1 + y) = 1 + x + y + x * y

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

х = 1е-8 у = 2е-6 z = 3e-7 w = 4e-5

Что такое (1 + x) (1 + y) (1 + z) * (1 + w)? В двойной точности получаю:

(1 + х) (1 + у) (1 + Z) * ​​(1 + W)

и =

      1.00004231009302

Однако посмотрим, что произойдет, если мы просто выполним простое аддитивное приближение.

1 + (x + y + z + w)

ans =

            1.00004231

Мы потеряли младшие биты, которые могли быть важны. Это проблема, только если некоторые отличия от 1 в продукте составляют не менее sqrt (eps), где eps - это точность, с которой вы работаете.

Попробуйте вместо этого:

f = @ (u, v) u + v + u * v;

результат = f (x, y);

result = f (result, z);

result = f (result, w);

1 + результат

ans =

      1.00004231009302

Как видите, это возвращает нас к результату двойной точности. На самом деле, это немного точнее, поскольку внутреннее значение результата равно 4.23100930230249e-05.

Answer 5

Стоит отметить, что вы тестируете ограничения своего оборудования, а не Java. Java использует 64-битную плавающую точку в вашем процессоре.

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

Answer 6

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

Если рациональные числа не подходят, я бы одобрил логарифмический ответ.

Изменить в ответ на ваши изменения:

Если вы имеете дело с числами, представляющими низкий процент ответов, делайте то, что делают ученые:

• Представьте их как избыток / дефицит (нормализуйте часть 1.0)
• Масштабируйте их. Думайте в терминах «частей на миллион» или как угодно.

Это позволит вам иметь дело с разумными числами для расчетов.

Answer 7

Когда вы говорите «большинство из которых очень близко к 1», сколько именно?

Возможно, вы могли бы иметь неявное смещение 1 во всех ваших числах и просто работать с дробями.

Answer 8

Если вам действительно нужна точность, вам придется использовать что-то вроде BigDecimal, даже если это медленнее, чем Double.

Если вам действительно не нужна точность, возможно, вы могли бы пойти с ответом Дэвида. Но даже если вы часто используете умножения, это может быть преждевременной оптимизацией, поэтому BIgDecimal может быть в любом случае правильным способом