Opened 10 years ago

Closed 6 years ago

## #11895 closed defect (invalid)

Reported by: Owned by: mmasdeu roed critical sage-duplicate/invalid/wontfix padics p-adic, hash, days71 roed, SimonKing N/A one pickle from the pickle jar does not unpickle correctly u/saraedum/ticket/11895 42afa4d47da18d38095cd54313731f856ae5f083 #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341, #16342 todo

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.)
• …?

### comment:1 Changed 10 years ago by roed

Apply 11895.patch

### Changed 10 years ago by roed

Creates a hash function for extension elements

### comment:2 Changed 10 years ago by roed

• Status changed from new to needs_review

### comment:3 Changed 10 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 10 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 9 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 9 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 9 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 9 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 9 years ago by saraedum (previous) (diff)

### Changed 9 years ago by saraedum

experimental patch to disable caching for padics

### comment:9 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:10 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:11 Changed 8 years ago by saraedum

• Dependencies set to #15897

### comment:12 Changed 8 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 8 years ago by saraedum

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

### comment:14 Changed 8 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 8 years ago by git

• Commit set to eb811aa1e013eb31560e4c10b961f3633248f0ec

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

 ​eb811aa `Introduced _cache_key for sage objects`

### comment:16 Changed 8 years ago by git

• Commit changed from eb811aa1e013eb31560e4c10b961f3633248f0ec to ab5ef13ff20bf2e128b76826606950d2a9b1cf45

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

 ​ab5ef13 `Enable caching for non-hashable objects`

### comment:17 Changed 8 years ago by saraedum

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

### comment:18 Changed 8 years ago by git

• Commit changed from ab5ef13ff20bf2e128b76826606950d2a9b1cf45 to aed468f0fcfe1a6c492b579f75d5d9db5db1917d

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

 ​4f376cf `Fixed _test_one and _test_zero for unhashable elements of monoids` ​927c2ba `Made polynomials with unhashable coefficients unhashable` ​aed468f `Enabled caching for unhashable objects in factories`

### comment:19 Changed 8 years ago by git

• Commit changed from aed468f0fcfe1a6c492b579f75d5d9db5db1917d to 39c9c5f1cd76344db0727bcffaab6ad3b9ef1b94

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

 ​dba5677 `Use a UniqueFactory to cache instances of QuaternionAlgebra` ​2453e37 `Merge branch 'u/saraedum/ticket/15897' of git://trac.sagemath.org/sage into ticket/11895` ​55bf7be `Use a UniqueFactory to cache instances of DirichletGroup` ​40786c9 `Merge branch 'u/saraedum/ticket/15898' of git://trac.sagemath.org/sage into ticket/11895` ​3a05a1a `Improved handling of unhashable keys in weak dictionary` ​468b5cc `Merge branch 'u/saraedum/ticket/15956' of git://trac.sagemath.org/sage into ticket/11895` ​d79e9ce `Implemented _cache_key() for polynomials` ​a3a192c `fixed a typo in CA_template.pxi` ​39c9c5f `fixed a hashing doctest for fixed modulus p-adic elements`

### comment:20 Changed 8 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:

 ​bdaaaff `Fixed a pickling doctest for QuaternionAlgebras` ​67ed0b7 `Merge branch 'u/saraedum/ticket/15897' of git://trac.sagemath.org/sage into ticket/11895` ​ebe6a39 `Doctest to illustrate that caching of DirichletGroups works` ​0521e97 `Doctest to illustrate that base_ring must be a part of the cache key created by the DirichletGroup factory` ​3d01887 `cleaned up docstring of DirichletGroup` ​5210dd9 `Merge branch 'u/saraedum/ticket/15898' of git://trac.sagemath.org/sage into ticket/11895` ​22e0a10 `Handle already merged tickets correctly when merging dependencies in the dev scripts.` ​898294f `Merge branch 'u/saraedum/ticket/16124' of git://trac.sagemath.org/sage into ticket/11895` ​d178cfb `Properly escape {} in sagedev.push()` ​454727a `Merge 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:

 ​f1cbe03 `Merge branch 'develop' into ticket/11670` ​8e96824 `Raise an error if the generator of a number field has not been specified.` ​9b4deff `Trac #11670: reviewer patch` ​28890ac `Merge branch 'u/pbruin/11670-NumberField_unique' of git://trac.sagemath.org/sage into ticket/11895` ​53e1915 `recursively unpack tuples in cachefung._cache_key` ​ba6db3d `Made multivariate polynomials with unhashable coefficients unhashable` ​07e77d2 `Implemented _cache_key for elliptic curves defined with (unhashable) p-adic coefficients` ​ccd475a `use proper @cached_function in monsky_washnitzer` ​7cf0eb4 `Rewrote part of ProjectiveSpace.resultant() to avoid a problem with unhashable p-adics` ​35894b5 `Fixed 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:

 ​1934ffa `Fixed test cases for @weak_cached_function` ​c26938c `Fixed the doctest for EltPair's __hash__() to reflect the new behaviour.` ​d2cff6e `Some 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:

 ​94fcddb `Merge branch 'u/saraedum/ticket/16337' of git://trac.sagemath.org/sage into ticket/15692` ​72fce8b `Added a pickle parameter for @cached_method` ​0717849 `Enable pickling of the cache for groebner_basis()` ​561072f `Merge branch 'u/saraedum/ticket/15692' of git://trac.sagemath.org/sage into ticket/16321` ​c74f601 `Fix incorrect usage of key parameter of @cached_method for ambient spaces of modular forms` ​8f7ec6f `Merge branch 'u/saraedum/ticket/16321' of git://trac.sagemath.org/sage into ticket/11895` ​034ea7a `HeckeAlgebra and HeckeAlgebra_anemic inherit from CachedRepresentation` ​fe5ad0a `HeckeAlgebra uses @cached_method where possible` ​fddc853 `Fixed the expected output of an unstable eigenvalue test.` ​42afa4d `Merge 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:42 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:43 follow-up: ↓ 44 Changed 7 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: ↓ 45 Changed 7 years ago by saraedum

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: ↓ 47 Changed 7 years ago by vbraun

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 6 years ago by jakobkroeker

• Stopgaps set to todo

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

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.

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.