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:  sage7.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 )
Sage says that the Boolean lattice of 2^3=8
elements is not [meetjoin]semidistributive. This is due to comparison in logarithm of Sage Integer
.
Change History (28)
comment:1 Changed 3 years ago by
 Branch set to u/jmantysalo/latticeposet__bug_in_testing_semidistributivity
comment:2 Changed 3 years ago by
 Commit set to 1a727401edf30b7217771de99acef212703eca83
 Description modified (diff)
comment:3 Changed 3 years ago by
 Commit changed from 1a727401edf30b7217771de99acef212703eca83 to 9edd77b37e3570fdae8d77b5344678f4b6f0cf9a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9edd77b  Workaround for logarithm bug.

comment:4 Changed 3 years ago by
 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
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
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 nonsemidistributivity then? Won't make much difference.
comment:7 followup: ↓ 8 Changed 3 years ago by
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
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 sagedevel:
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
(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.)
comment:10 Changed 3 years ago by
Maybe I just wrote the log_2
myself:
def _log_2(n): """ Return the 2based 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 followup: ↓ 12 Changed 3 years ago by
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 & ~(n1) == 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 ; followup: ↓ 13 Changed 3 years ago by
Replying to leif:
You could likewise use Python's
math.log(int(n), 2)
, or various functions from GMP (since Sage Integers are based onmpz_t
).
Isn't there the same rounding problem with math.log
?
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 3 years ago by
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 onmpz_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 4
^{s}> n
^{n}, where the righthand 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 bikeshedding.
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
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
, orlog(n, 2)
, practically get?)
It should be safe up to at least 2^{52}+ (maybe even up to 2^{1022}+) because Python's float
s (returned by math.log()
) are actually double
s AFAIK.
comment:15 followup: ↓ 16 Changed 3 years ago by
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 ; followup: ↓ 20 Changed 3 years ago by
Replying to leif:
Distantly related:
While we (you?) are at it,
HasseDiagram
has a couple of.is_...()
methods which do not returnTrue
orFalse
, but eitherNone
or some sample. Shouldn't these return the former unless a keyword argumentcertificate
:) (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
 Commit changed from 9edd77b37e3570fdae8d77b5344678f4b6f0cf9a to 68419a4806a5674caa0ea535577ef9a6eea1a5c5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
68419a4  Logarithm in semidistributive.

comment:18 followup: ↓ 19 Changed 3 years ago by
OK, should work now. Also function name changed.
comment:19 in reply to: ↑ 18 ; followup: ↓ 22 Changed 3 years ago by
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 ; followup: ↓ 23 Changed 3 years ago by
Replying to jmantysalo:
Replying to leif:
Distantly related:
While we (you?) are at it,
HasseDiagram
has a couple of.is_...()
methods which do not returnTrue
orFalse
, but eitherNone
or some sample. Shouldn't these return the former unless a keyword argumentcertificate
:) (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_(truefalse)]
, [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
Perhaps a bit late, but did you look at Integer.{log,exact_log}()
?
comment:22 in reply to: ↑ 19 Changed 3 years ago by
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 ; followup: ↓ 25 Changed 3 years ago by
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
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
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 followup: ↓ 27 Changed 3 years ago by
 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
comment:28 Changed 3 years ago by
 Branch changed from u/jmantysalo/latticeposet__bug_in_testing_semidistributivity to 68419a4806a5674caa0ea535577ef9a6eea1a5c5
 Resolution set to fixed
 Status changed from positive_review to closed
Ready for review, but let's first wait if discussion at https://groups.google.com/forum/#!topic/sagedevel/ZtwUc5c4Js0 founds better solution.
New commits:
Workaround for log bug.