Opened 8 years ago
Closed 8 years ago
#1181 closed defect (fixed)
[with patch+review] polynomial/fraction field __hash__ re-write
Reported by: | jbmohler | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | sage-2.8.15 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The attached patch has a number of goals.
- Allow shared members of ZZ and ZZ[x] to be used interchangeably in a dictionary.
- Replace ZZ in #1 by QQ, IntegerModRing?(p) and probably a bunch of other things.
- Replace ZZ[x] in #1 by ZZ[x,y,...]
- Allow shared members of FractionFields? and their base rings to be used interchangeably in a dictionary.
- Make the hash function faster in polynomial rings
Goal #5 was achieved very nicely for univariate poly rings, but hash in QQ[x,y] was extremely fast in the original code. Unfortunately, that very fast hash violated all good things of the goals above. It also wasn't asymptotically fast (think huge numerical coefficients).
The goals 1-4 above result in a fix for the subs method:
sage: R.<x,y>=ZZ[] sage: (x/y).subs({x:1}) 1/y # produced x/y in the old version
A bad thing about this patch is that the results of hash(x) changing reorders the output of things that come from a dictionary. There is a number of doc-tests output changes which are only a matter of order in the list. I think this is probably bad style in doc-tests and in real life. At least some of those outputs have a very natural order (to the human mind if not mathematically).
The attached patch entirely supersedes #1075 and I'm going to go close it right now.
Attachments (1)
Change History (5)
comment:1 Changed 8 years ago by jbmohler
comment:2 Changed 8 years ago by jbmohler
- Summary changed from polynomial/fraction field __hash__ re-write to [with patch] polynomial/fraction field __hash__ re-write
comment:3 Changed 8 years ago by robertwb
- Summary changed from [with patch] polynomial/fraction field __hash__ re-write to [with patch+review] polynomial/fraction field __hash__ re-write
I've looked at the code and tried it out and it is a great idea that works well. Despite multivariate hashes slowing down, they are still really quite fast, and the properties listed are much more important.
comment:4 Changed 8 years ago by mabshoff
- Resolution set to fixed
- Status changed from new to closed
Merged in 2.8.15.rc0.
Some benchmarks:
Original:
Patched:
I believe (but haven't verified too much) that the big problem is converting coefficients to the base ring from the singular poly. This should probably be optimized for a whole bunch of reasons other than hashing, which will carry over to hashing.