代码之家 › 专栏 › 技术社区 › mat kelcey

使用对数避免数值下溢的算法问题(以2为例)

numerical-methods logarithm

6

mat kelcey · 技术社区 · 16 年前

说 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' / (A'+B') 和 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], ... ]

欢迎有任何想法!

(附:我问了一个问题。) similar question 24小时前关于比率 A'/B' 但实际上是 错误的 A'/(A'+B') . 对不起,我错了。)

4 回复 | 直到 9 年前

1

5

vava 16 年前

我看这里没什么办法

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')

或者,因为您很可能使用一些流行的脚本语言,所以大多数脚本语言都内置了rational算术类,Python和Ruby肯定有。

2

1

Anon. 16 年前

到目前为止,我最好的办法是将数字表示形式保留为分数,并实现我自己的算法,但它越来越笨拙

Fraction 在任何地方都可以当作数字的类。

例如,确定 A / B C / D 基本上是比较 A * D 大于 B * C .

3

1

Glorfindel Doug L. 7 年前

如果你这样做,你会遇到相反的问题:分子溢出。您知道它不能小于max(X)^n,其中max(X)是分子中的最大值,n是列表中的项数。如果你能计算出来,你就能知道你的电脑是否有问题。你不能把10磅的东西放在5磅的袋子里。

不幸的是,对数的属性将您限制为以下简化:

和

所以你被困住了:

4

0

Hamish Grubijan 16 年前

好。。。如果你知道 A'(A'+B') ,那么 B'(A'+B') 应该是1减去那个。我个人不会用对数。我会用实际分数。我还将使用某种BigInt类来表示分子和分母。你用哪种语言?Python很适合。