wrong result for bool(a <= b)

[zimmermann6]

Consider the following with Sage 9.0:

sage: k=26
sage: bool(2/(2*pi)^(2*k) <= abs(bernoulli(2*k)/factorial(2*k)))
False

This result is wrong:

sage: R = RealBallField(100)
sage: 2/R(2*pi)^(2*k) - abs(bernoulli(2*k))/factorial(2*k)
[-1.387129688041e-57 +/- 3.98e-70]

Component: basic arithmetic

Author: Michael Orlitzky

Branch/Commit: fc8801c

Reviewer: Paul Zimmermann

Issue created by migration from https://trac.sagemath.org/ticket/31424

[zimmermann6]

comment:1

it seems the decision is taken according to floating-point arithmetic, but as we know, we cannot decide whether an expression is positive from its evaluation in floating-point arithmetic, due to rounding errors and cancellations:

sage: n(2/(2*pi)^(2*k) - abs(bernoulli(2*k)/factorial(2*k)), 53)
1.14702617601537e-56
sage: n(2/(2*pi)^(2*k) - abs(bernoulli(2*k)/factorial(2*k)), 100)
-1.3871296880407980731315151264e-57

The proper solution would be to evaluate the expression with either RealIntervalField or RealBallField.

[zimmermann6]

comment:2

cf #31665

[mkoeppe]

comment:3

Moving to 9.4, as 9.3 has been released.

[orlitzky]

Author: Michael Orlitzky

[orlitzky]

comment:6

It's already using intervals, but without enough precision, so the answer you get back is "I don't know." The bool() then converts "I don't know" into False. We'll never add enough precision to solve every problem, so ultimately the best practice is to use expr.test_relation() instead of bool(expr) for this purpose. That said, everyone uses bool(expr). So I've roughly doubled the precision used by default. Your two examples should be handled correctly now.

[orlitzky]

Branch: u/mjo/ticket/31424

[orlitzky]

Commit: fc8801c

[yyyyx4]

comment:8

I'm not very familiar with this subsystem of Sage, but it strikes me as wrong to return False for bool(unknown). Shouldn't this throw an exception?

[zimmermann6]

comment:9

thank you Michael, your patch seems good to me. However test_relation does not seem to work on this example:

sage: eq = 2/(2*pi)^(2*k) <= abs(bernoulli(2*k)/factorial(2*k))
sage: eq.test_relation()
NotImplemented

[zimmermann6]

Reviewer: Paul Zimmermann

[orlitzky]

comment:11

Replying to @zimmermann6:

thank you Michael, your patch seems good to me. However test_relation does not seem to work on this example:

sage: eq = 2/(2*pi)^(2*k) <= abs(bernoulli(2*k)/factorial(2*k))
sage: eq.test_relation()
NotImplemented

The user interface could use some work, but NotImplemented means "I don't know." If a lack of precision is the problem, you can pass in a different domain over which to evaluate the relation:

sage: k = 26
sage: eq = 2/(2*pi)^(2*k) <= abs(bernoulli(2*k)/factorial(2*k))
sage: eq.test_relation()
NotImplemented
sage: eq.test_relation(domain=RealIntervalField(200))
True
sage: eq.test_relation(domain=RealBallField(200))
True

However the real benefit is in knowing that the answer was undetermined, rather than determined to be false.

[orlitzky]

comment:12

Replying to @yyyyx4:

I'm not very familiar with this subsystem of Sage, but it strikes me as wrong to return False for bool(unknown). Shouldn't this throw an exception?

Yes, arguably. This problem comes up frequently, and there has been a lot of discussion about it in the past. If I recall correctly, the argument against an exception is that the python data model defines how __bool__() and __nonzero()__ should behave, and as a result, exceptions are not allowed in bool(expr).

[yyyyx4]

comment:13

I can't find a statement anywhere that __bool__ can't throw. What's true (and very reasonable) is that if it returns, it must return either True or False, but the official documentation says nothing about exceptions.

Indeed, throwing exceptions in __bool__ not only works, but it's actually already happening in a few more or less standard situations: https://stackoverflow.com/a/52862551

Silently returning mathematically wrong results is always worse than anything that produces
a correct result or visibly fails if it can't. This remains true even if the solution is considered hackish by some.

[orlitzky]

comment:14

Replying to @yyyyx4:

Silently returning mathematically wrong results is always worse than anything that produces
a correct result or visibly fails if it can't. This remains true even if the solution is considered hackish by some.

We're in agreement. This is the best ticket I was able to dig up with a quick search:

• wrong symbolic results in case the answer is not known #17700: wrong symbolic results in case the answer is not known

Apparently a further issue is that maxima also does not distinguish between "known to be false" and "unknown," and we use maxima in some cases to obtain an answer.

[vbraun]

Changed branch from u/mjo/ticket/31424 to fc8801c