Opened 3 years ago

Closed 3 years ago

#21340 closed defect (fixed)

LatticePoset: bug in testing semidistributivity

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.4
Component: combinatorics Keywords:
Cc: leif Merged in:
Authors: Jori Mäntysalo Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 68419a4 (Commits) Commit: 68419a4806a5674caa0ea535577ef9a6eea1a5c5
Dependencies: Stopgaps:

Description (last modified by jmantysalo)

Sage says that the Boolean lattice of 2^3=8 elements is not [meet|join]-semidistributive. This is due to comparison in logarithm of Sage Integer.

Change History (28)

comment:1 Changed 3 years ago by jmantysalo

  • Branch set to u/jmantysalo/latticeposet__bug_in_testing_semidistributivity

comment:2 Changed 3 years ago by jmantysalo

  • Commit set to 1a727401edf30b7217771de99acef212703eca83
  • Description modified (diff)

Ready for review, but let's first wait if discussion at https://groups.google.com/forum/#!topic/sage-devel/ZtwUc5c4Js0 founds better solution.


New commits:

1a72740Workaround for log bug.

comment:3 Changed 3 years ago by git

  • Commit changed from 1a727401edf30b7217771de99acef212703eca83 to 9edd77b37e3570fdae8d77b5344678f4b6f0cf9a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9edd77bWorkaround for logarithm bug.

comment:4 Changed 3 years ago by jmantysalo

  • Cc leif added
  • Description modified (diff)
  • Status changed from new to needs_review

Leif, can you check this basically one line patch?

comment:5 Changed 3 years ago by tscrim

This is a massive hack solution that comes from this behavior:

sage: log(8, 2)
3
sage: log(8, int(2))
log(8)/log(2)
sage: log(int(8), int(2))
log(8)/log(2)

If we are to accept this hack, we should well document it as such.

comment:6 Changed 3 years ago by jmantysalo

Well, of course right solution would be correcting log. For example output type should depend on input type, not on input value. But

sage: type(log(8, 2))
<type 'sage.rings.integer.Integer'>
sage: type(log(9, 2))
<type 'sage.symbolic.expression.Expression'>

Should I just remove the quick test of non-semidistributivity then? Won't make much difference.

comment:7 follow-up: Changed 3 years ago by tscrim

The biggest thing is just documenting why we are doing certain things, so when we go back and look again or someone else comes and looks at it, it is clear why things were done this way.

One option would be wrapping the inequality test in bool(...). This evaluates the symbolic expression to a boolean and doesn't affect boolean values:

sage: bool(13 > 8 * log(8, 2) / 2)
True
sage: bool(12 > 8 * log(8, 2) / 2)
False
sage: bool(True)
True
sage: bool(False)
False

Again, there should be a comment. Another option would be to do log(8,2).n(), which could introduce some numerical noise. Or just force both values to ZZ.

comment:8 in reply to: ↑ 7 Changed 3 years ago by leif

Replying to tscrim:

One option would be wrapping the inequality test in bool(...). This evaluates the symbolic expression to a boolean and doesn't affect boolean values:

sage: bool(13 > 8 * log(8, 2) / 2)
True
sage: bool(12 > 8 * log(8, 2) / 2)
False
sage: bool(True)
True
sage: bool(False)
False

Quoting from sage-devel:

Ralf Stephan wrote:
> On Saturday, August 27, 2016 at 7:05:28 AM UTC+2, Jori Mäntysalo wrote:
>
>     But shouldn't it work in any case? I.e. comparison of
>     log(a+b*c^2...) to
>     some number should work when a,b,c... are sage Integers.
>
>
> log(integer) will not be expanded numerically except for log(0) and log(1).
> If you want it expanded, either give a float argument, eg log(2.), or
> append n().

N() wasn't the problem, but (also) rounding:

(s is 12 here.)

sage: n*log(n, 2)
24
sage: n*log(n, 2r)
8*log(8)/log(2)
sage: N(n*log(n, 2r))
24.0000000000000
sage: 2*s < n*log(n, 2)
False
sage: 2*s > n*log(n, 2)
False
sage: 2*s > n*log(n, 2r)
24 > 8*log(8)/log(2)
sage: bool(2*s > n*log(n, 2r))
True
sage: bool(2r*s > n*log(n, 2r))
True
sage: bool(2r*s > n*log(n, 2))
False
sage: 24 > N(n*log(n, 2r))
True

So I'd suggest to rewrite the code, and/or call the proper log(), or (first) check whether n is a power of 2.

comment:9 Changed 3 years ago by leif

(The left side of the comparison doesn't matter here, but note that bool(2*s > n*log(n, 2r)) and bool(2*s > n*log(n, 2)) give different results due to the behaviour of log() and rounding issues.)

Version 0, edited 3 years ago by leif (next)

comment:10 Changed 3 years ago by jmantysalo

Maybe I just wrote the log_2 myself:

def _log_2(n):
    """
    Return the 2-based logarithm of `n` rounded up.
    
    `n` is assumed to be a positive integer.
    
    EXAMPLES::
        
        sage: sage.combinat.poset.lattices._log_2(10)
        4
    """
    bits = -1
    i = n
    while i:
        i = i >> 1
        bits += 1
    if 1 << bits == n:
        return bits
    return bits+1

(On x86 one could use LZCNT and POPCNT. :=))

comment:11 follow-up: Changed 3 years ago by leif

See also the ffs() family, [__builtin_]clz(), ... (also on ARM etc.)

If you just want to know whether n is an exact power of two (<=> n==0 or popcnt(n)==1), you can use n & ~(n-1) == n.

You could likewise use Python's math.log(int(n), 2), or various functions from GMP (since Sage Integers are based on mpz_t).

comment:12 in reply to: ↑ 11 ; follow-up: Changed 3 years ago by jmantysalo

Replying to leif:

You could likewise use Python's math.log(int(n), 2), or various functions from GMP (since Sage Integers are based on mpz_t).

Isn't there the same rounding problem with math.log?

comment:13 in reply to: ↑ 12 ; follow-up: Changed 3 years ago by leif

Replying to jmantysalo:

Replying to leif:

You could likewise use Python's math.log(int(n), 2), or various functions from GMP (since Sage Integers are based on mpz_t).

Isn't there the same rounding problem with math.log?

Probably not for true powers of 2; don't know why Sage's log() is so bad in that regard. (How large does n, or log(n, 2), practically get?)

FWIW, if you want to stay in the integer domain, you could as well use 4s> nn, where the right-hand side is as cheap as the left if (n is sufficiently small or ctz(n) is relatively large or) n is a power of 2.

But that's perhaps already towards bike-shedding.


Especially if you know n is a power of 2, you could do appropriate rounding as well, but I'd rather fix log() or use a different one.

But doesn't already using sage.misc.functional.log(n, Integer(2)) solve (or, more precisely, work around) the main problem here?

comment:14 in reply to: ↑ 13 Changed 3 years ago by leif

Replying to leif:

Replying to jmantysalo:

Isn't there the same rounding problem with math.log?

Probably not for true powers of 2; don't know why Sage's log() is so bad in that regard. (How large does n, or log(n, 2), practically get?)

It should be safe up to at least 252+ (maybe even up to 21022+) because Python's floats (returned by math.log()) are actually doubles AFAIK.

comment:15 follow-up: Changed 3 years ago by leif

Distantly related:

While we (you?) are at it, HasseDiagram has a couple of .is_...() methods which do not return True or False, but either None or some sample. Shouldn't these return the former unless a keyword argument certificate :-) (which they currently don't have) is passed?

comment:16 in reply to: ↑ 15 ; follow-up: Changed 3 years ago by jmantysalo

Replying to leif:

Distantly related:

While we (you?) are at it, HasseDiagram has a couple of .is_...() methods which do not return True or False, but either None or some sample. Shouldn't these return the former unless a keyword argument certificate :-) (which they currently don't have) is passed?

Other than is_semidistributive?

But yes, you are right. Kevin said the same at #21002. Suggestion for better name?

comment:17 Changed 3 years ago by git

  • Commit changed from 9edd77b37e3570fdae8d77b5344678f4b6f0cf9a to 68419a4806a5674caa0ea535577ef9a6eea1a5c5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

68419a4Logarithm in semidistributive.

comment:18 follow-up: Changed 3 years ago by jmantysalo

OK, should work now. Also function name changed.

comment:19 in reply to: ↑ 18 ; follow-up: Changed 3 years ago by leif

Replying to jmantysalo:

OK, should work now. Also function name changed.

Doesn't the latter require a deprecation of the old function first?

comment:20 in reply to: ↑ 16 ; follow-up: Changed 3 years ago by leif

Replying to jmantysalo:

Replying to leif:

Distantly related:

While we (you?) are at it, HasseDiagram has a couple of .is_...() methods which do not return True or False, but either None or some sample. Shouldn't these return the former unless a keyword argument certificate :-) (which they currently don't have) is passed?

Other than is_semidistributive?

Yes. The first (I think) being .is_complemented(self), but there are more IIRC.


But yes, you are right. Kevin said the same at #21002. Suggestion for better name?

certify, prove[_if_(true|false)], [return_]witness[_if_false]? ;-)

(I guess you were referring to is_...(), not the keyword argument, though.)

I'd rather keep the is_...(), but add (a) keyword or boolean argument(s), and only change the return type(s).

But then you'd have to first make the old behaviour the default, for backwards compatibility.

comment:21 Changed 3 years ago by leif

Perhaps a bit late, but did you look at Integer.{log,exact_log}()?

comment:22 in reply to: ↑ 19 Changed 3 years ago by jmantysalo

Replying to leif:

OK, should work now. Also function name changed.

Doesn't the latter require a deprecation of the old function first?

I have thinked that hasse_diagram.py is an internal implementation file that can be changed. And the function is one release old only.

comment:23 in reply to: ↑ 20 ; follow-up: Changed 3 years ago by jmantysalo

Replying to leif:

(I guess you were referring to is_...(), not the keyword argument, though.)

I'd rather keep the is_...(), but add (a) keyword or boolean argument(s), and only change the return type(s).

I can think those later in another ticket. Actually there is more to think about in splitting code in posets.py and lattices.py vs. hasse_diagram.py.

But is there more to do for this ticket?

exact_log rounds down, my helper function rounds up. Of course I could use it, but the code would not be much simpler. Waiting for Python 3 and log_2...

comment:24 Changed 3 years ago by jmantysalo

Assuming that #21419 get accepted it offers a faster way to chech if a lattice is semidistributive.

comment:25 in reply to: ↑ 23 Changed 3 years ago by jmantysalo

Just a ping... Currently Sage says that a distributive lattice is not semidistributive, which is bad. There are more to add, but IMO bugs should be corrected first.

Replying to jmantysalo:

But is there more to do for this ticket?

comment:26 follow-up: Changed 3 years ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, ok. It would have been better to put this log2 in some other place.

comment:27 in reply to: ↑ 26 Changed 3 years ago by jmantysalo

Replying to chapoton:

It would have been better to put this log2 in some other place.

But I think that someone, "Frédéric" if I remember the name correctly, is converting SageMath to Python 3. :=) Then we will have math.log2().

comment:28 Changed 3 years ago by vbraun

  • Branch changed from u/jmantysalo/latticeposet__bug_in_testing_semidistributivity to 68419a4806a5674caa0ea535577ef9a6eea1a5c5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.