Проблема с арифметикой с использованием логарифмов, чтобы избежать числового недополнения (дубль 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] * ...

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

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

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

Я понимаю, что преобразование произведения в сумму с помощью логарифмов может помочь мне определить, какой из A' или B' больше

ie 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'). Извините, моя ошибка. )


numerical-methods logarithm
person mat kelcey    schedule 19.02.2010    source источник
comment
Извините, это означает A'/(A'+B') и B'/(A'+B')? Вам не хватает скобок?   -  person duffymo    schedule 19.02.2010
comment
ага, спасибо, поправил.   -  person mat kelcey    schedule 21.02.2010

Ответы (4)


arrow_upward
5
arrow_downward

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

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

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 они точно есть.

person vava    schedule 19.02.2010
comment
Python 3.x имеет встроенный bigint. Int — это bigint. Это помогает поддерживать высокую точность. - person Hamish Grubijan; 19.02.2010
comment
@ Хэмиш, он мог бы использовать double для счетчиков. У него проблемы с недостаточным переполнением, и я не думаю, что он хочет иметь сверхточные расчеты, достаточно точные. - person vava; 19.02.2010
comment
Ну... когда вы делите одно маленькое число на другое, вы можете сохранить хорошую точность для обоих. - person Hamish Grubijan; 19.02.2010
comment
что-то вроде A' / (A'+B') = 1 / (1 + B'/A') это то, что я искал, спасибо! это часть более крупной части, поэтому я стараюсь как можно больше использовать логарифмы, чтобы избежать больших переписываний. ваше здоровье! - person mat kelcey; 21.02.2010
comment
(дополнительно, хотя я пишу это на рубине, это прототип для свиньи Hadoop, поэтому я пытаюсь максимально игнорировать Rational) - person mat kelcey; 21.02.2010

arrow_upward
1
arrow_downward

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

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

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

person Anon.    schedule 19.02.2010

arrow_upward
1
arrow_downward

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

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

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

alt text
(источник: таблица уравнений .com)

а также

alt text
(источник: таблица уравнений .com)

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

alt text
(источник: таблица уравнений .com)

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

person duffymo    schedule 19.02.2010

arrow_upward
0
arrow_downward

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

person Hamish Grubijan    schedule 19.02.2010