Задача с арифметикой с использованием логарифмов, чтобы избежать числового занижения (дубль 2)

Question

У меня есть два списка фракций;

скажем 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] * ...

Я хочу вычислить нормализованное значение A 'и B'

то есть конкретно значения A' / (A'+B') и B' / (A'+B')

Моя проблема в том, что A и B оба довольно длинные, и каждое значение мало, поэтому вычисление продукта очень быстро приводит к уменьшению численности ...

Я понимаю, что преобразование продукта в сумму с помощью логарифмов может помочь мне определить, какой из A 'или 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') Извините, моя ошибка.

Answer 1

Я вижу несколько способов здесь

Прежде всего вы можете заметить, что

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'), что тоже легко. Самым сложным здесь является нормализация результирующего значения, которое выполняется по модулю и является тривиальным.

В качестве альтернативы, поскольку вы, скорее всего, используете какой-то популярный язык сценариев, большинство из них имеют встроенные классы для рациональной арифметики, в Python и Ruby они точно есть.

Answer 2

И А, и В имеют одинаковый знаменатель в каждой упомянутой вами фракции. Это верно для каждого термина в списке? Если это так, почему бы вам не учесть это при расчете продукта? Знаменатель будет просто X ^ n, когда X - это значение, а n - это число терминов в списке.

Если вы сделаете это, у вас возникнет обратная проблема: переполнение в числителе. Вы знаете, что оно не может быть меньше max (X) ^ n, где max (X) - максимальное значение в числителе, а n - количество членов в списке. Если вы можете рассчитать это, вы можете увидеть, если ваш компьютер будет иметь проблемы. Вы не можете положить 10 фунтов чего-либо в сумку 5 фунтов.

К сожалению, свойства логарифмов ограничивают вас следующими упрощениями:

_{(источник: rulesheet.com )}

и

_{(источник: rulesheet.com )}

Итак, вы застряли с:

_{(источник: rulesheet.com )}

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

Answer 3

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

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

В качестве примера, определение того, является ли дробь A / B больше C / D, в основном сравнивает, является ли A * D больше B * C.

Answer 4

Ну ... если вы знаете A'(A'+B'), тогда B'(A'+B') должен быть один минус. Я лично не использовал бы логарифмы. Я бы использовал фактические дроби. Я бы также использовал какой-то класс BigInt для представления числителя и знаменателя. Какой язык вы используете? Python может хорошо подойти.