Проблема с арифметикой с помощью логарифмов для предотвращения числовой потери значимости (берут 2),
У меня есть два списка частей;
сказать A = [ 1/212, 5/212, 3/212, ... ]
и B = [ 4/143, 7/143, 2/143, ... ].
Если мы определяем A' = a[0] * a[1] * a[2] * ... и B' = b[0] * b[1] * b[2] * ...
Я хочу вычислить нормализованное значение' и B'
т.е. конкретно значения A' / (A'+B') и B' / (A'+B')
Моя проблема является A, B, и довольно долго и каждое значение, является маленьким настолько вычисляющий, что продукт вызывает числовую потерю значимости очень быстро...
Я понимаю, что превращение продукта в сумму через логарифмы может помочь мне определить, который из' или B' больше
т.е. max( log(a[0])+log(a[1])+..., log(b[0])+log(b[1])+... )
и то использование регистрируется, я могу вычислить значение A' / B' но как я делаю A' / A'+B'
Мой лучший выбор до настоящего времени состоит в том, чтобы сохранить представления числа как части, т.е. A = [ [1,212], [5,212], [3,212], ... ] и реализуйте мою собственную арифметику, но это становится неуклюжим, и у меня есть чувство, что существует (простой) способ логарифмов, которые я просто пропускаю....
Числители для A и B не прибывают из последовательности. Они могли бы также быть случайными в целях этого вопроса. Если помогает, что знаменатели для всех значений в A являются тем же, как все знаменатели для B.
Любые приветствующиеся идеи!
(PS. Я задал подобный вопрос 24 часа назад относительно отношения A'/B' но это был на самом деле неправильный вопрос спросить. Я на самом деле после A'/(A'+B'). Извините, моя ошибка.)
4 ответа
Я вижу здесь несколько путей
Во-первых, вы можете заметить, что
A' / (A'+B') = 1 / (1 + B'/A')
и вы знаете, как вычислить B'/A' с помощью логарифмов.
Другой способ - реализовать собственную рациональную арифметику, но далеко ходить за этим не нужно. Так как вы знаете, что знаменатели одинаковы для всего массива, это сразу дает вам
numerator(A') = numerator(a[0]) * numerator(a[1]) ...
denumerator(A') = denumerator(a[0]) ^ A.length
Все, что вам теперь нужно сделать, это сложить A' и B', что легко, а затем перемножить A' и 1/(A'+B'), что также легко. Самое сложное здесь - нормализовать полученное значение, что делается с помощью операции modulo и является тривиальным.
В качестве альтернативы, поскольку вы, скорее всего, используете какой-нибудь популярный скриптовый язык, большинство из них имеют встроенные классы для рациональной арифметики, в Python и Ruby они точно есть.
Мой лучший вариант на сегодняшний день - сохранить представления чисел в виде дробей и реализовать собственную арифметику, но это становится неуклюжим
Какой язык вы используете? Если вы можете перегружать операторы, то должно быть очень легко создать класс Fraction, который вы можете рассматривать как число практически везде.
Например, определение того, больше ли дробь A / B, чем C / D, сводится к сравнению того, больше ли A * D, чем B * C.
И A, и B имеют одинаковый знаменатель в каждой указанной вами дроби. Это верно для каждого термина в списке? Если это так, почему вы не учитываете это при расчете продукта? Знаменатель будет просто X ^ n, когда X - значение, а n - количество терминов в списке.
Если вы это сделаете, у вас будет противоположная проблема: переполнение числителя. Вы знаете, что оно не может быть меньше max (X) ^ n, где max (X) - максимальное значение в числителе, а n - количество терминов в списке. Если вы можете рассчитать это, вы можете увидеть, возникнет ли проблема с вашим компьютером. Вы не можете положить 10 фунтов чего-либо в 5-фунтовый мешок.
К сожалению, свойства логарифмов ограничивают вас следующими упрощениями:
(источник: sizesheet.com )
и
(источник: Equationheet.com ])
Итак, вы застряли с:
(источник: sizesheet.com )
Если вы используете язык, поддерживающий числа с бесконечной точностью (например, Java BigDecimal), это может сделать вашу жизнь немного проще. Но все же есть хороший аргумент в пользу того, чтобы подумать, прежде чем приступить к вычислениям. Зачем использовать грубую силу, когда можно быть элегантным?
Ну ... если вы знаете A '(A' + B ') , тогда B '(A' + B ') должно быть на единицу минус это. Лично я бы не стал использовать логарифмы. Я бы использовал реальные дроби.Я бы также использовал какой-то класс BigInt для представления числителя и знаменателя. Какой язык вы используете? Python может хорошо подойти.