6

分数のリストが 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' のどちらが大きいかを判断するのに役立つことを理解しています

すなわち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 の分子は数列に由来しません。この質問の目的のために、それらはランダムである可能性もあります。B のすべての分母と同様に、A のすべての値の分母が同じになるのに役立つ場合。

どんなアイデアでも大歓迎です！

( ps. 24 時間前に比率に関して同様の質問A'/B'をしましたが、実際には間違った質問でした。実際には の後A'/(A'+B')です。申し訳ありませんが、私の間違いです。)

4

4 に答える 4

5

ここにはいくつかの方法があります

まず気付くことができるのは、

A' / (A'+B') = 1 / (1 + B'/A')

B'/A'対数で計算する方法を知っています。

もう 1 つの方法は、独自の有理数演算を実装することですが、それについてはそれほど難しくはありません。分母は配列全体で同じであることがわかっているので、すぐに

numerator(A') = numerator(a[0]) * numerator(a[1]) ...
denumerator(A') = denumerator(a[0]) ^ A.length

今あなたがしなければならないことは、A' と B' を合計することです。これは簡単で、それから掛け算A'する1/(A'+B')ことも簡単です。ここで最も難しい部分は、結果の値を正規化することです。これはモジュロ演算で行われ、自明です。

あるいは、一般的なスクリプト言語を使用している可能性が高いため、それらのほとんどには有理演算用のクラスが組み込まれています。Python と Ruby には確かにそれらがあります。

于 2010-02-19T02:56:35.680 に答える
1

これまでの私の最善の策は、数値表現を分数として保持し、独自の算術演算を実装することですが、それは不器用になっています

どの言語を使用していますか? Fraction演算子をオーバーロードできれば、どこでも数値として扱えるクラスを簡単に作成できるはずです。

例として、分数A / Bが よりも大きいかどうかを判断することC / Dは、基本的にA * Dが よりも大きいかどうかを比較することB * Cです。

于 2010-02-19T02:57:08.703 に答える
1

A と B は、あなたが言及した各分数の分母が同じです。それはリストのすべての用語に当てはまりますか? もしそうなら、積を計算するときにそれを考慮に入れてみませんか? X が値で、n がリスト内の用語の数である場合、分母は単純に X^n になります。

これを行うと、分子のオーバーフローという逆の問題が発生します。max(X)^n よりも小さくすることはできません。ここで、max(X) は分子の最大値で、n はリスト内の用語の数です。それを計算できれば、コンピュータに問題があるかどうかがわかります。5 ポンドのバッグに 10 ポンドの物を入れることはできません。

残念ながら、対数の性質により、次の単純化に制限されます。

代替テキスト
（出典：equationsheet.com）

と

代替テキスト
（出典：equationsheet.com）

だからあなたは立ち往生しています：

代替テキスト
（出典：equationsheet.com）

無限精度数をサポートする言語 (Java BigDecimal など) を使用している場合は、作業が少し楽になるかもしれません。しかし、計算する前にいくつかのことを考えるべき良い議論がまだあります。エレガントになれるのに、なぜブルートフォースを使うのでしょうか?

于 2010-02-19T02:59:09.590 に答える
0

ええと...あなたが知っているなら、1からA'(A'+B')それB'(A'+B')を引いたものでなければなりません。個人的には対数は使いません。実際の分数を使用します。また、ある種の BigInt クラスを使用して、分子と分母を表します。どの言語を使用していますか? Python が適している場合があります。

于 2010-02-19T03:01:03.780 に答える