Opened 9 years ago

Closed 5 years ago

#11895 closed defect (invalid)

Make p-adic numbers unhashable

Reported by: mmasdeu Owned by: roed
Priority: critical Milestone: sage-duplicate/invalid/wontfix
Component: padics Keywords: p-adic, hash, days71
Cc: roed, SimonKing Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues: one pickle from the pickle jar does not unpickle correctly
Branch: u/saraedum/ticket/11895 (Commits) Commit: 42afa4d47da18d38095cd54313731f856ae5f083
Dependencies: #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341, #16342 Stopgaps: todo

Description (last modified by saraedum)

Only fixed modulus p-adic numbers should be hashable, all others can not implement a reasonable hash function. Currently some of them do which can cause horrible bugs:

sage: @cached_function
....: def is_one(x):
....:     return x==1

sage: R = Zp(3, 70)
sage: is_one(R(1,1))
True
sage: is_one(R(2^64))
True
sage: R(2^64)
1 + 2*3 + 2*3^2 + 3^3 + 3^4 + 2*3^5 + 3^7 + 2*3^8 + 3^10 + 2*3^11 + 2*3^13 + 3^14 + 2*3^16 + 3^18 + 3^19 + 2*3^20 + 3^21 + 3^23 + 2*3^25 + 3^26 + 2*3^27 + 2*3^28 + 3^29 + 2*3^30 + 2*3^31 + 2*3^34 + 2*3^35 + 2*3^36 + 3^37 + 3^38 + 3^39 + 3^40 + O(3^70)

The problem here is that == has been changed so that two numbers are equal if they are equal to the least common precision. In this example, the two elements are equal to precision one and they have the same hash value (at least on my machine).

The proposal of this ticket is to make p-adics unhashable (but cacheable through #16316). The modifications required for this to work are almost always related to functions which implemented manual caching through dictionaries. The long list of dependencies is mostly about rewriting constructor functions to go through UniqueFactory or CachedRepresentation which gets unhashable elements right as of #16317. (I believe that these changes are valuable refactorings anyway.)

I can imagine that some people will not like such a change. What are the alternatives?

  • Keep it the way it is. (I do not think that this is a good idea. If you do intensive p-adic computations then the birthday paradox will eventually hit you.)
  • Mark p-adics in a special way so their == is not used by cached_method and friends. (Not an option, because p-adics may be wrapped inside other objects which will still use their operator ==.)
  • Change == for p-adics to say whether two numbers are "really" equal. (Bad idea. Say you are in a p-adic field. Some algorithm wants to know whether x is invertible and says x==0. Now this will be false for most p-adic zeros.)
  • Make __hash__ return a constant. (This would work but will give horrible performance.)
  • …?

Attachments (2)

11895.patch (13.1 KB) - added by roed 9 years ago.
Creates a hash function for extension elements
cache.patch (24.6 KB) - added by saraedum 8 years ago.
experimental patch to disable caching for padics

Download all attachments as: .zip

Change History (51)

comment:1 Changed 9 years ago by roed

Apply 11895.patch

Changed 9 years ago by roed

Creates a hash function for extension elements

comment:2 Changed 9 years ago by roed

  • Status changed from new to needs_review

comment:3 Changed 9 years ago by davidloeffler

Can you clean up the formatting of the docstrings a bit? There's a general convention that long lines in docstrings (except doctests!) should be wrapped at 80 columns and trailing whitespace removed. Other than that this looks fine to me.

comment:4 Changed 9 years ago by davidloeffler

  • Authors set to David Roe
  • Reviewers set to David Loeffler
  • Status changed from needs_review to needs_work
  • Work issues set to whitespace, line wrapping in docstrings

comment:5 Changed 8 years ago by mmasdeu

When trying the input:

sage: R.<x> = PolynomialRing(QQ)
sage: Cp.<g> = Qp(7,100).extension(x^2-17)
sage: ECp = EllipticCurve('14a1').change_ring(Cp)
sage: xx = (6*g + 6) + 5*7 + (g + 3)*7^2 + (4*g + 1)*7^3 + (g + 5)*7^4 + (3*g + 3)*7^5 + 3*7^6 + (5*g + 2)*7^7 + (5*g + 6)*7^8 + 2*7^9 + 7^10 + 7^11 + 6*g*7^12 + (3*g + 2)*7^13 + (3*g + 2)*7^14 + 3*g*7^15 + 5*7^16 + (6*g + 3)*7^17 + 2*g*7^18 + (g + 6)*7^19 + 6*7^20 + (g + 6)*7^21 + 4*7^22 + (6*g + 6)*7^23 + (2*g + 4)*7^24 + (2*g + 6)*7^25 + 5*g*7^26 + (4*g + 1)*7^27 + (3*g + 1)*7^28 + (6*g + 4)*7^29 + (5*g + 5)*7^30 + (3*g + 6)*7^31 + 7^32 + (2*g + 3)*7^33 + (3*g + 5)*7^34 + (3*g + 2)*7^35 + (2*g + 1)*7^36 + g*7^37 + 6*g*7^38 + (5*g + 1)*7^39 + (2*g + 1)*7^40 + (3*g + 6)*7^41 + (4*g + 1)*7^42 + (3*g + 5)*7^43 + (5*g + 4)*7^44 + (4*g + 1)*7^45 + 3*7^46 + (2*g + 3)*7^47 + (5*g + 6)*7^48 + (5*g + 2)*7^49 + (g + 1)*7^50 + 5*g*7^51 + 3*7^52 + 2*7^53 + (5*g + 4)*7^54 + (3*g + 2)*7^55 + (4*g + 1)*7^56 + (6*g + 2)*7^57 + (6*g + 3)*7^58 + (3*g + 4)*7^60 + (4*g + 1)*7^61 + (2*g + 6)*7^63 + (3*g + 2)*7^64 + (4*g + 3)*7^65 + (g + 1)*7^66 + (2*g + 4)*7^68 + (2*g + 4)*7^69 + (5*g + 5)*7^70 + (5*g + 5)*7^71 + (3*g + 1)*7^72 + (3*g + 6)*7^73 + (2*g + 6)*7^74 + (4*g + 1)*7^75 + 5*7^76 + 2*g*7^77 + 3*g*7^78 + (5*g + 2)*7^79 + (5*g + 3)*7^80 + (2*g + 6)*7^81 + (3*g + 4)*7^82 + (5*g + 5)*7^83 + (2*g + 2)*7^84 + (g + 2)*7^85 + 6*7^86 + (2*g + 6)*7^87 + (2*g + 6)*7^88 + 3*g*7^89 + (5*g + 2)*7^90 + 3*g*7^91 + (2*g + 6)*7^92 + 7^93 + (2*g + 6)*7^94 + (4*g + 4)*7^95 + (4*g + 3)*7^96 + 3*7^97 + (g + 5)*7^98 + (5*g + 5)*7^99 + O(7^100)
sage: yy = (5*g + 2) + (3*g + 1)*7 + (6*g + 1)*7^2 + 2*g*7^3 + 7^4 + (3*g + 6)*7^5 + 6*g*7^6 + (3*g + 4)*7^7 + (4*g + 4)*7^8 + 2*g*7^9 + (g + 1)*7^10 + (4*g + 2)*7^11 + (g + 4)*7^12 + (5*g + 2)*7^13 + (5*g + 3)*7^14 + (3*g + 6)*7^15 + (g + 1)*7^16 + (4*g + 3)*7^17 + (4*g + 2)*7^19 + (4*g + 5)*7^20 + (6*g + 4)*7^21 + (6*g + 1)*7^22 + (3*g + 1)*7^23 + 7^24 + (4*g + 2)*7^25 + (g + 6)*7^26 + (3*g + 3)*7^27 + 5*7^28 + (6*g + 6)*7^30 + (4*g + 4)*7^31 + (g + 4)*7^32 + (2*g + 2)*7^33 + (3*g + 6)*7^34 + (5*g + 4)*7^35 + (3*g + 5)*7^36 + (2*g + 6)*7^37 + (4*g + 5)*7^38 + 4*g*7^40 + (g + 5)*7^41 + (5*g + 2)*7^42 + (3*g + 1)*7^43 + 5*g*7^44 + (4*g + 6)*7^45 + (2*g + 2)*7^46 + (2*g + 3)*7^47 + (3*g + 5)*7^48 + 5*7^49 + (4*g + 2)*7^50 + (g + 6)*7^51 + (4*g + 6)*7^52 + (4*g + 1)*7^53 + 2*g*7^54 + (3*g + 1)*7^56 + (5*g + 6)*7^58 + (2*g + 2)*7^59 + 2*7^60 + 3*7^61 + (6*g + 6)*7^62 + (6*g + 4)*7^63 + (4*g + 3)*7^64 + (6*g + 3)*7^65 + (2*g + 6)*7^66 + (g + 2)*7^67 + 4*7^68 + (3*g + 2)*7^69 + (2*g + 3)*7^70 + (2*g + 2)*7^71 + (5*g + 5)*7^72 + (6*g + 3)*7^73 + 3*g*7^74 + 4*7^75 + (g + 5)*7^76 + (g + 3)*7^77 + (5*g + 4)*7^78 + 5*7^79 + 2*g*7^80 + 3*7^81 + 6*g*7^82 + (4*g + 2)*7^83 + (3*g + 5)*7^84 + (2*g + 4)*7^85 + 2*g*7^86 + (g + 2)*7^87 + (3*g + 4)*7^88 + (g + 4)*7^89 + 6*g*7^90 + 2*g*7^92 + (2*g + 1)*7^93 + (5*g + 3)*7^94 + (4*g + 3)*7^95 + (5*g + 3)*7^96 + (3*g + 1)*7^97 + (4*g + 4)*7^98 + 2*7^99 + O(7^100)
sage: P = ECp([xx,yy])
sage: print 2*P

I get the following error:

/data/sage-5.3.rc1/local/lib/python2.7/site-packages/sage/rings/padics/padic_ZZ_pX_CR_element.so in sage.rings.padics.padic_ZZ_pX_CR_element.pAdicZZpXCRElement.__hash__ (sage/rings/padics/padic_ZZ_pX_CR_element.cpp:16654)()

OverflowError: Python int too large to convert to C long

comment:6 Changed 8 years ago by nbruin

Three remarks:

  • It looks like the hash maximally only contain about 3 decimal digits of information. That's way too small! Hash table lookups are based on having O(1) elements in the bins. To give you an idea of how small the constant in the O(1) should be: Python's dictionaries make sure that the average bin size in 0.7 (smaller than 1). You're fighting the birthday paradox here, so don't underestimate the likelyhood of collisions. Anyway, when using more than 1000 elements in a dictionary, the proposed hash will let dictionaries just degrade to a linear search, but with way larger memory overhead.
  • It may seem that having hashes depend on precision (which isn't taken into account in equality testing!) is a mild condition, but it's not. If you have a large matrix or other aggregate element, you can easily end up with some small precision elements in there. This will lead to very confusing situation where a dict lookup doesn't find your key, but you know you have a key that's equal to a stored one. Of course, if you're relying on equality in p-adic computations you've already lost ...
  • Caching functions on equality of arguments is a very bad idea with the p-adics. If I construct a known invertible matrix to too low a precision, I'll get determinant 0. If subsequently I construct the same matrix to higher precision, a cached determinant function would recognize the argument as equal to one he'd seem before (because equality is only to lowest common precision) and would just give me the 0 back.

Properties 2 and 3 conspire to hide the problem a bit:

sage: @cached_function
....: def DISC(f):
....:         return discriminant(f)
....: 
sage: K=Qp(2,500)
sage: P.<x>=K[]
sage: f=(1+O(2^200))*x^2-(2^200+O(2^200))
sage: DISC(f)
0
sage: g=(1+O(2^300))*x^2-(2^200+O(2^300))
sage: DISC(g)
2^202 + O(2^302)
sage: 
sage: hash(f), hash(g)
(15360174650385708, 15377766836429868)
sage: f == g
True

so the entry under f isn't found when looking up g because they end up being stored in different bins, so the difference in hash is enough to distinguish them. As soon as the dictionary gets resized in a way that lets those two hashes end up in the same bin, it'll be a toss-up which answer you get back from either DISC(f) or DISC(g). Oh course, by then it will be very painful to track down what happened.

To show that functions that depend on more of their arguments than just equality should not be cached:

sage: a=3
sage: b=GF(5)(3)
sage: @cached_function
....: def test(a):
....:         return a^2
....: 
sage: [test(a),test(b)]
[9, 9]
sage: test.clear_cache()
sage: [test(b),test(a)]
[4, 4]

comment:7 Changed 8 years ago by roed

Nils, I agree that there are some horrible compromises to be had on this issue. I would like to make p-adic elements unhashable, but there are some nasty consequences of doing so. We can't add points on elliptic curves over p-adic fields. We can't print matrices. Out of curiousity I tried changing the hash methods on elements of Zp and Qp to raise a TypeError. Hundreds of doctest failures. There's an assumption that elements are hashable throughout Sage.

I don't know what the answer is. If we can come to a consensus on this I'm happy to fix the whitespace issues. :-)

comment:8 Changed 8 years ago by saraedum

I had a look into this. Except for one place (which could certainly be worked around somehow), the doctests seem to fail because caching doesn't work anymore. Would there be something wrong with adding a _cache_key() to SageObject which per default returns self. Only if the element is not hashable (but should be cacheable) it could return something that is actually a unique key for this element — something like self.dumps() maybe.

I gave it a try (see attached patch). The only doctests that fail seem to be a few places where self.dumps() doesn't work and one problem in sage/modular/overconvergent/weightspace.py.

Last edited 8 years ago by saraedum (previous) (diff)

Changed 8 years ago by saraedum

experimental patch to disable caching for padics

comment:9 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 7 years ago by saraedum

  • Dependencies set to #15897

comment:12 Changed 7 years ago by saraedum

  • Branch set to u/saraedum/ticket/11895
  • Modified changed from 03/06/14 13:44:35 to 03/06/14 13:44:35

comment:13 Changed 7 years ago by saraedum

  • Branch u/saraedum/ticket/11895 deleted
  • Dependencies changed from #15897 to #15897, #15898

comment:14 Changed 7 years ago by saraedum

  • Branch set to u/saraedum/ticket/11895
  • Modified changed from 03/06/14 15:45:34 to 03/06/14 15:45:34

comment:15 Changed 7 years ago by git

  • Commit set to eb811aa1e013eb31560e4c10b961f3633248f0ec

Branch pushed to git repo; I updated commit sha1. New commits:

eb811aaIntroduced _cache_key for sage objects

comment:16 Changed 7 years ago by git

  • Commit changed from eb811aa1e013eb31560e4c10b961f3633248f0ec to ab5ef13ff20bf2e128b76826606950d2a9b1cf45

Branch pushed to git repo; I updated commit sha1. New commits:

ab5ef13Enable caching for non-hashable objects

comment:17 Changed 7 years ago by saraedum

  • Dependencies changed from #15897, #15898 to #15897, #15898, #15956

comment:18 Changed 7 years ago by git

  • Commit changed from ab5ef13ff20bf2e128b76826606950d2a9b1cf45 to aed468f0fcfe1a6c492b579f75d5d9db5db1917d

Branch pushed to git repo; I updated commit sha1. New commits:

4f376cfFixed _test_one and _test_zero for unhashable elements of monoids
927c2baMade polynomials with unhashable coefficients unhashable
aed468fEnabled caching for unhashable objects in factories

comment:19 Changed 7 years ago by git

  • Commit changed from aed468f0fcfe1a6c492b579f75d5d9db5db1917d to 39c9c5f1cd76344db0727bcffaab6ad3b9ef1b94

Branch pushed to git repo; I updated commit sha1. New commits:

dba5677Use a UniqueFactory to cache instances of QuaternionAlgebra
2453e37Merge branch 'u/saraedum/ticket/15897' of git://trac.sagemath.org/sage into ticket/11895
55bf7beUse a UniqueFactory to cache instances of DirichletGroup
40786c9Merge branch 'u/saraedum/ticket/15898' of git://trac.sagemath.org/sage into ticket/11895
3a05a1aImproved handling of unhashable keys in weak dictionary
468b5ccMerge branch 'u/saraedum/ticket/15956' of git://trac.sagemath.org/sage into ticket/11895
d79e9ceImplemented _cache_key() for polynomials
a3a192cfixed a typo in CA_template.pxi
39c9c5ffixed a hashing doctest for fixed modulus p-adic elements

comment:20 Changed 7 years ago by saraedum

  • Dependencies changed from #15897, #15898, #15956 to #15897, #15898, #15956, #10448, #11670

It seems that only two doctests fail now. Both are related to manually implemented caches. One for number fields the other one for division polynomials for elliptic curves.

comment:21 Changed 7 years ago by git

  • Commit changed from 39c9c5f1cd76344db0727bcffaab6ad3b9ef1b94 to 454727a95a28b9df29f08a8bb58760d9630854ec

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

bdaaaffFixed a pickling doctest for QuaternionAlgebras
67ed0b7Merge branch 'u/saraedum/ticket/15897' of git://trac.sagemath.org/sage into ticket/11895
ebe6a39Doctest to illustrate that caching of DirichletGroups works
0521e97Doctest to illustrate that base_ring must be a part of the cache key created by the DirichletGroup factory
3d01887cleaned up docstring of DirichletGroup
5210dd9Merge branch 'u/saraedum/ticket/15898' of git://trac.sagemath.org/sage into ticket/11895
22e0a10Handle already merged tickets correctly when merging dependencies in the dev scripts.
898294fMerge branch 'u/saraedum/ticket/16124' of git://trac.sagemath.org/sage into ticket/11895
d178cfbProperly escape {} in sagedev.push()
454727aMerge branch 'u/saraedum/ticket/16122' of git://trac.sagemath.org/sage into ticket/11895

comment:22 Changed 7 years ago by saraedum

  • Dependencies changed from #15897, #15898, #15956, #10448, #11670 to #15897, #15898, #15956, #16122, #16124
  • Modified changed from 04/10/14 17:13:16 to 04/10/14 17:13:16

comment:23 Changed 7 years ago by saraedum

  • Dependencies changed from #15897, #15898, #15956, #16122, #16124 to #15897, #15898, #15956, #16122, #16124, #16129

comment:24 Changed 7 years ago by git

  • Commit changed from 454727a95a28b9df29f08a8bb58760d9630854ec to 35894b53ce04d0ca8aa541ba2906b2bfb7837aec

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

f1cbe03Merge branch 'develop' into ticket/11670
8e96824Raise an error if the generator of a number field has not been specified.
9b4deffTrac #11670: reviewer patch
28890acMerge branch 'u/pbruin/11670-NumberField_unique' of git://trac.sagemath.org/sage into ticket/11895
53e1915recursively unpack tuples in cachefung._cache_key
ba6db3dMade multivariate polynomials with unhashable coefficients unhashable
07e77d2Implemented _cache_key for elliptic curves defined with (unhashable) p-adic coefficients
ccd475ause proper @cached_function in monsky_washnitzer
7cf0eb4Rewrote part of ProjectiveSpace.resultant() to avoid a problem with unhashable p-adics
35894b5Fixed EltPair.__hash__ to make discover_action work for unhashable parents.

comment:25 Changed 7 years ago by saraedum

  • Dependencies changed from #15897, #15898, #15956, #16122, #16124, #16129 to #11670, #15897, #15898, #15956, #16122, #16124, #16129
  • Modified changed from 04/12/14 00:08:01 to 04/12/14 00:08:01

comment:26 Changed 7 years ago by git

  • Commit changed from 35894b53ce04d0ca8aa541ba2906b2bfb7837aec to d2cff6e0d937f0238fb7a2694608782dcf1f432c

Branch pushed to git repo; I updated commit sha1. New commits:

1934ffaFixed test cases for @weak_cached_function
c26938cFixed the doctest for EltPair's __hash__() to reflect the new behaviour.
d2cff6eSome random changes to fix the remaining doctest bugs. Will start a new branch which contains some of these.

comment:27 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250

comment:28 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251

comment:29 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:30 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316

comment:31 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #163177

comment:32 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #163177 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317

comment:33 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318

comment:34 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321

comment:35 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339

comment:36 Changed 7 years ago by git

  • Commit changed from d2cff6e0d937f0238fb7a2694608782dcf1f432c to 42afa4d47da18d38095cd54313731f856ae5f083

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

94fcddbMerge branch 'u/saraedum/ticket/16337' of git://trac.sagemath.org/sage into ticket/15692
72fce8bAdded a pickle parameter for @cached_method
0717849Enable pickling of the cache for groebner_basis()
561072fMerge branch 'u/saraedum/ticket/15692' of git://trac.sagemath.org/sage into ticket/16321
c74f601Fix incorrect usage of key parameter of @cached_method for ambient spaces of modular forms
8f7ec6fMerge branch 'u/saraedum/ticket/16321' of git://trac.sagemath.org/sage into ticket/11895
034ea7aHeckeAlgebra and HeckeAlgebra_anemic inherit from CachedRepresentation
fe5ad0aHeckeAlgebra uses @cached_method where possible
fddc853Fixed the expected output of an unstable eigenvalue test.
42afa4dMerge branch 'u/saraedum/ticket/16339' of git://trac.sagemath.org/sage into ticket/11895

comment:37 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341

comment:38 Changed 7 years ago by saraedum

  • Dependencies changed from #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341 to #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341, #16342

comment:39 Changed 7 years ago by jdemeyer

Please update the ticket description to reflect what this ticket is now really about.

comment:40 Changed 7 years ago by saraedum

  • Authors David Roe deleted
  • Description modified (diff)
  • Reviewers David Loeffler deleted
  • Summary changed from padic_ZZ_pX_CR_element is unhashable to Make p-adic numbers unhashable
  • Work issues changed from whitespace, line wrapping in docstrings to one pickle from the pickle jar does not unpickle correctly

comment:41 Changed 7 years ago by saraedum

  • Cc SimonKing added

Added Simon since we talked about this in Bad Boll a while ago.

comment:42 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:43 follow-up: Changed 6 years ago by vbraun

The ticket description mentions a problem when comparing x==0, but that is incorrect. Comparison first coerces both sides to a common parent, and if the rhs is a Python int then this will be the same padic ring as x. So if == were to compare both sides including the precision we'd still be fine. Of course when comparing two padics you coerce to the lower precision, so the main issue remains.

Just making elements not hashable is also terrible, many algorithms use sets and dicts. E.g. if the coefficient field is not hashable then you can't compute groebner bases in polynomial rings, rendering it essentially useless.

comment:44 in reply to: ↑ 43 ; follow-up: Changed 6 years ago by saraedum

Replying to vbraun:

The ticket description mentions a problem when comparing x==0, but that is incorrect. Comparison first coerces both sides to a common parent, and if the rhs is a Python int then this will be the same padic ring as x. So if == were to compare both sides including the precision we'd still be fine. Of course when comparing two padics you coerce to the lower precision, so the main issue remains.

I'm not sure I understand. Say you are in Qp with 2 digits of precision. Then 0 coerces to O(p^2). Setting x=O(p) gives x != 0 when including precisions in the comparison.

Just making elements not hashable is also terrible, many algorithms use sets and dicts. E.g. if the coefficient field is not hashable then you can't compute groebner bases in polynomial rings, rendering it essentially useless.

I agree that disabling hashing has its drawbacks but I do not see an alternative. Judging from the doctests, not that many things break, actually. But I guess that some algorithms have to be modified to support unhashable elements if we want to use them with p-adic numbers.

comment:45 in reply to: ↑ 44 ; follow-up: Changed 6 years ago by vbraun

Replying to saraedum:

I'm not sure I understand. Say you are in Qp with 2 digits of precision. Then 0 coerces to O(p^2). Setting x=O(p) gives x != 0 when including precisions in the comparison.

Ok, I hadn't thought about that. But IMHO thats more of an issue with having two separate and competing ways of specifying precision, one in the parent and one in the element:

sage: O(3).parent()(3)
3 + O(3^21)

I agree that disabling hashing has its drawbacks but I do not see an alternative.

I don't have a good answer right now either, but it once again shows the importance of this issue. We need to fix our failure to adhere to Python's convention about comparison and hashes.

comment:46 Changed 5 years ago by jakobkroeker

  • Stopgaps set to todo

comment:47 in reply to: ↑ 45 Changed 5 years ago by saraedum

Replying to vbraun:

But IMHO thats more of an issue with having two separate and competing ways of specifying precision, one in the parent and one in the element

Is it really about competing ways? I guess this happens because it is possible to specify precision in the element at all.

Replying to saraedum:

I agree that disabling hashing has its drawbacks but I do not see an alternative.

I don't have a good answer right now either, but it once again shows the importance of this issue. We need to fix our failure to adhere to Python's convention about comparison and hashes.

The problem is that sometimes you want a==b to mean, a is essentially the same as b, say in an algorithm that doese while(x!=0), and sometimes to you want it to mean a is indistinguishable from b. The latter is maybe what you want in dictionary lookups. But not always, for example if you have a dict which maps powers of x, the variable in a polynomial ring, to whatever, then you probably do not care about the precision of the 1 coefficient. So what I'm trying to say is that precision is tricky. Sure, many algorithms might just throw an exception if we disable hashing. But would they really work correctly otherwise? Whenever we make a dictionary lookup with elements with precision, it seems that we need to decide on a case by case basis which version of == would produce the right result. Throwing an exception and requiring people to explicitly specify what they want to happen seems to be a better solution IMO.

comment:48 Changed 5 years ago by saraedum

  • Keywords days71 added
  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to positive_review

We are abandoning this in favor of #20246.

comment:49 Changed 5 years ago by vbraun

  • Resolution set to invalid
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.