Opened 6 years ago

Closed 6 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.

  1. Allow shared members of ZZ and ZZ[x] to be used interchangeably in a dictionary.
  2. Replace ZZ in #1 by QQ, IntegerModRing?(p) and probably a bunch of other things.
  3. Replace ZZ[x] in #1 by ZZ[x,y,...]
  4. Allow shared members of FractionFields? and their base rings to be used interchangeably in a dictionary.
  5. 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)

hash-patch-2_8_12.hg (5.4 KB) - added by jbmohler 6 years ago.
the patch

Download all attachments as: .zip

Change History (5)

comment:1 Changed 6 years ago by jbmohler

Some benchmarks:

Original:

sage: R.<x>=ZZ[]
sage: one=R(1)
sage: f=x^2+2*x+1
sage: timeit hash(one)
1000000 loops, best of 3: 1.03 µs per loop
sage: timeit hash(f)
100000 loops, best of 3: 3.53 µs per loop
sage: timeit hash(x)
100000 loops, best of 3: 2.91 µs per loop
sage: R.<x,y>=QQ[]
sage: one=R(1)
sage: f=x^2+2*y+1
sage: timeit hash(one)
1000000 loops, best of 3: 931 ns per loop
sage: timeit hash(f)
1000000 loops, best of 3: 1.86 µs per loop
sage: timeit hash(x)
1000000 loops, best of 3: 486 ns per loop

Patched:

sage: # first the success
sage: R.<x>=ZZ[]
sage: one=R(1)
sage: f=x^2+2*x+1
sage: timeit hash(one)
1000000 loops, best of 3: 1.04 µs per loop
sage: timeit hash(f)
1000000 loops, best of 3: 1.98 µs per loop
sage: timeit hash(x)
1000000 loops, best of 3: 1.4 µs per loop
sage: # second: the huge slowdown
sage: R.<x,y>=QQ[]
sage: one=R(1)
sage: f=x^2+2*y+1
sage: timeit hash(one)
100000 loops, best of 3: 2.88 µs per loop
sage: timeit hash(f)
100000 loops, best of 3: 6.31 µs per loop
sage: timeit hash(x)
100000 loops, best of 3: 3.18 µs per loop

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.

Changed 6 years ago by jbmohler

the patch

comment:2 Changed 6 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 6 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 6 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in 2.8.15.rc0.

Note: See TracTickets for help on using tickets.