计算科学 - 非理性不平等的整数化简 - 吾爱随笔录

计算科学计算几何

2021-12-01 06:05:31

我正在从事计算几何的工作，其中算法的鲁棒性很重要。在两个不同的场合，我遇到了一个场景，我比较了两个表达式的数值大小，最终的不等式最终看起来像这样：

\sqrt{A} + \sqrt{B} < C

$\sqrt{A} + \sqrt{B} < C$

在哪里 $A$ , $B$ 和 $C$ 是整数。我只关心谓词的值。本能地，我尝试对双方进行平方，但当然这并没有消除平方根项。

我的问题。有没有办法只使用整数（计算机）算术来确定这样的谓词的真值？

1个回答

认为 $a,b,c>0$ （否则很容易）。检查 $c-\sqrt{b}>0$ , 然后平方 $\sqrt{a}<c-\sqrt{b}$ 一次得到

c^{2} + b - a > 2 c \sqrt{b} .

$c^2+b-a>2c\sqrt{b}.$ 所以检查一下

c^{2} + b - a > 0

$c^2+b-a>0$ （如果不是，那么它是错误的，因为 rhs 是正的，所以 lhs 也必须是这样），然后检查

(c^{2} + b - a)^{2} > 4 b c^{2} .

$(c^2+b-a)^2>4bc^2.$

但是这有一个重要的问题：使用整数运算，您必须防止溢出。例如，当计算 $c^4$ 和 $32$ -bit 整数，这将溢出 $c\geq 256$ .

顺便说一句，您只需一行 Mathematica 就可以得出最后一个不等式：

GroebnerBasis[{c - u - v, u^2 - a, v^2 - b}, {a, b, c}, {u, v}]

这使：

{a^{2} - 2 a b + b^{2} - 2 a c^{2} - 2 b c^{2} + c^{4}}

$\left\{a^2-2 a b+b^2-2 a c^2-2 b c^2+c^4\right\}$

在圣人中也是如此：

R.<a,b,c,u,v> = PolynomialRing(QQ, 'a b c u v')
I = R.ideal([c-u-v, u**2-a, v**2-b])
I.elimination_ideal([u,v])

输出

Ideal (c^4 - 2*a*c^2 - 2*b*c^2 + a^2 - 2*a*b + b^2) of \
   Multivariate Polynomial Ring in a, b, c, u, v over Rational Field

其它你可能感兴趣的问题