1
$\begingroup$

I'm doing work in computational geometry where the robustness of the algorithm is important. On two separate occasions now have I come across a scenario where I compare the numerical size of two expressions where the final inequality ends up looking something like this:

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

where $A$, $B$ and $C$ are integers. I only care about the value of the predicate. Instinctively I tried squaring both sides but of course that doesn't rid of the square root term.

My question. Is there a way to determine the truth value of predicates like this using only integer (computer) arithmetic?

$\endgroup$
  • $\begingroup$ Are there any special properties of your data that you can leverage? You could perhaps come up with an adaptive precision algorithm to evaluate your predicate similar to the methods used in Shewchuk's fast, robust predicates for computational geometry. If you don't want to emulate floating point arithmetic with integers, you could derive a couple valid integer inequalities, but they rely on bounding the square root by its floor and ceiling, and they won't be robust. $\endgroup$ – Geoff Oxberry Aug 20 '14 at 18:57
2
$\begingroup$

Assume $a,b,c>0$ (otherwise it's easy). Check that $c-\sqrt{b}>0$, then square $\sqrt{a}<c-\sqrt{b}$ once to get $$ c^2+b-a>2c\sqrt{b}. $$ So check that $c^2+b-a>0$ (if not then it's false because rhs is positive, so lhs must be as well), then check that $$ (c^2+b-a)^2>4bc^2. $$

But there is an important issue with this: with integer arithmetic you must guard against overflow. For example, when computing $c^4$ with $32$-bit integers, this will overflow for $c\geq 256$.

By the way, you can arrive at the last inequality with just one line of Mathematica:

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

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

And here is the same in sage:

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

Output

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
$\endgroup$
  • $\begingroup$ I don't see how you got the first inequality by squaring. If you square both sides and rearrange, shouldn't you get a $2\sqrt{ab}$ term somewhere? $\endgroup$ – Geoff Oxberry Aug 20 '14 at 20:24
  • 1
    $\begingroup$ @GeoffOxberry I squared $\sqrt{a} < c - \sqrt{b}$. $\endgroup$ – Kirill Aug 20 '14 at 21:22
  • $\begingroup$ Of course! I can't believe I didn't arrive at that even with my naive methods. Checking that first term is not an option however, with my required restrictions. Edit: Or I suppose it could be possible since I know that C is an integer. $\endgroup$ – John Bananas Aug 21 '14 at 9:46
  • $\begingroup$ @JohnBananas $c-\sqrt{b}>0 \Leftrightarrow c^2>b$ with $b,c>0$. $\endgroup$ – Kirill Aug 21 '14 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.