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, GitHub, GitLab) | 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 )
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 bycached_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 whetherx
is invertible and saysx==0
. Now this will be false for mostp
-adic zeros.) - Make
__hash__
return a constant. (This would work but will give horrible performance.) - …?
Attachments (2)
Change History (51)
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
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
- 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
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
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 theO(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
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
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
.
comment:9 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:10 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:11 Changed 7 years ago by
- Dependencies set to #15897
comment:12 Changed 7 years ago by
- 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
- Branch u/saraedum/ticket/11895 deleted
- Dependencies changed from #15897 to #15897, #15898
comment:14 Changed 7 years ago by
- 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
- 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 7 years ago by
- 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 7 years ago by
- Dependencies changed from #15897, #15898 to #15897, #15898, #15956
comment:18 Changed 7 years ago by
- Commit changed from ab5ef13ff20bf2e128b76826606950d2a9b1cf45 to aed468f0fcfe1a6c492b579f75d5d9db5db1917d
comment:19 Changed 7 years ago by
- 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 7 years ago by
- 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
- 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
- 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
- Dependencies changed from #15897, #15898, #15956, #16122, #16124 to #15897, #15898, #15956, #16122, #16124, #16129
comment:24 Changed 7 years ago by
- 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
- 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
- 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
- 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
- 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
- Milestone changed from sage-6.2 to sage-6.3
comment:30 Changed 7 years ago by
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
Please update the ticket description to reflect what this ticket is now really about.
comment:40 Changed 7 years ago by
- 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
- Cc SimonKing added
Added Simon since we talked about this in Bad Boll a while ago.
comment:42 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:43 follow-up: ↓ 44 Changed 6 years ago by
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 6 years ago by
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 asx
. 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 6 years ago by
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)
. Settingx=O(p)
givesx != 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
- Stopgaps set to todo
comment:47 in reply to: ↑ 45 Changed 6 years ago by
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
- 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
- Resolution set to invalid
- Status changed from positive_review to closed
Apply 11895.patch