Opened 11 years ago
Closed 7 years ago
#11895 closed defect (invalid)
Make padic numbers unhashable
Reported by:  Marc Masdeu  Owned by:  David Roe 

Priority:  critical  Milestone:  sageduplicate/invalid/wontfix 
Component:  padics  Keywords:  padic, hash, days71 
Cc:  David Roe, Simon King  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 padic 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 padics 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 padic computations then the birthday paradox will eventually hit you.)
 Mark padics in a special way so their
==
is not used bycached_method
and friends. (Not an option, because padics may be wrapped inside other objects which will still use their operator==
.)  Change
==
for padics to say whether two numbers are "really" equal. (Bad idea. Say you are in a padic 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 11 years ago by
Changed 11 years ago by
Attachment:  11895.patch added 

Creates a hash function for extension elements
comment:2 Changed 11 years ago by
Status:  new → needs_review 

comment:3 Changed 11 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 11 years ago by
Authors:  → David Roe 

Reviewers:  → David Loeffler 
Status:  needs_review → needs_work 
Work issues:  → whitespace, line wrapping in docstrings 
comment:5 Changed 10 years ago by
When trying the input:
sage: R.<x> = PolynomialRing(QQ) sage: Cp.<g> = Qp(7,100).extension(x^217) 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/sage5.3.rc1/local/lib/python2.7/sitepackages/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 10 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 padic computations you've already lost ...
 Caching functions on equality of arguments is a very bad idea with the padics. 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 tossup 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 10 years ago by
Nils, I agree that there are some horrible compromises to be had on this issue. I would like to make padic elements unhashable, but there are some nasty consequences of doing so. We can't add points on elliptic curves over padic 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 10 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
.
Changed 10 years ago by
Attachment:  cache.patch added 

experimental patch to disable caching for padics
comment:9 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:10 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:11 Changed 9 years ago by
Dependencies:  → #15897 

comment:12 Changed 9 years ago by
Branch:  → u/saraedum/ticket/11895 

Modified:  Mar 6, 2014, 1:44:35 PM → Mar 6, 2014, 1:44:35 PM 
comment:13 Changed 9 years ago by
Branch:  u/saraedum/ticket/11895 

Dependencies:  #15897 → #15897, #15898 
comment:14 Changed 9 years ago by
Branch:  → u/saraedum/ticket/11895 

Modified:  Mar 6, 2014, 3:45:34 PM → Mar 6, 2014, 3:45:34 PM 
comment:15 Changed 9 years ago by
Commit:  → eb811aa1e013eb31560e4c10b961f3633248f0ec 

Branch pushed to git repo; I updated commit sha1. New commits:
eb811aa  Introduced _cache_key for sage objects

comment:16 Changed 9 years ago by
Commit:  eb811aa1e013eb31560e4c10b961f3633248f0ec → ab5ef13ff20bf2e128b76826606950d2a9b1cf45 

Branch pushed to git repo; I updated commit sha1. New commits:
ab5ef13  Enable caching for nonhashable objects

comment:17 Changed 9 years ago by
Dependencies:  #15897, #15898 → #15897, #15898, #15956 

comment:18 Changed 9 years ago by
Commit:  ab5ef13ff20bf2e128b76826606950d2a9b1cf45 → aed468f0fcfe1a6c492b579f75d5d9db5db1917d 

comment:19 Changed 9 years ago by
Commit:  aed468f0fcfe1a6c492b579f75d5d9db5db1917d → 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 padic elements

comment:20 Changed 9 years ago by
Dependencies:  #15897, #15898, #15956 → #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 9 years ago by
Commit:  39c9c5f1cd76344db0727bcffaab6ad3b9ef1b94 → 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 9 years ago by
Dependencies:  #15897, #15898, #15956, #10448, #11670 → #15897, #15898, #15956, #16122, #16124 

Modified:  Apr 10, 2014, 5:13:16 PM → Apr 10, 2014, 5:13:16 PM 
comment:23 Changed 9 years ago by
Dependencies:  #15897, #15898, #15956, #16122, #16124 → #15897, #15898, #15956, #16122, #16124, #16129 

comment:24 Changed 9 years ago by
Commit:  454727a95a28b9df29f08a8bb58760d9630854ec → 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/11670NumberField_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) padic coefficients

ccd475a  use proper @cached_function in monsky_washnitzer

7cf0eb4  Rewrote part of ProjectiveSpace.resultant() to avoid a problem with unhashable padics

35894b5  Fixed EltPair.__hash__ to make discover_action work for unhashable parents.

comment:25 Changed 9 years ago by
Dependencies:  #15897, #15898, #15956, #16122, #16124, #16129 → #11670, #15897, #15898, #15956, #16122, #16124, #16129 

Modified:  Apr 12, 2014, 12:08:01 AM → Apr 12, 2014, 12:08:01 AM 
comment:26 Changed 9 years ago by
Commit:  35894b53ce04d0ca8aa541ba2906b2bfb7837aec → 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 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250 

comment:28 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251 

comment:29 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:30 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316 

comment:31 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #163177 

comment:32 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #163177 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317 

comment:33 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318 

comment:34 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321 

comment:35 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339 

comment:36 Changed 9 years ago by
Commit:  d2cff6e0d937f0238fb7a2694608782dcf1f432c → 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 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341 

comment:38 Changed 9 years ago by
Dependencies:  #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341 → #11670, #15897, #15898, #15956, #16122, #16124, #16129, #16250, #16251, #16316, #16317, #16318, #16321, #16339, #16341, #16342 

comment:39 Changed 9 years ago by
Please update the ticket description to reflect what this ticket is now really about.
comment:40 Changed 9 years ago by
Authors:  David Roe 

Description:  modified (diff) 
Reviewers:  David Loeffler 
Summary:  padic_ZZ_pX_CR_element is unhashable → Make padic numbers unhashable 
Work issues:  whitespace, line wrapping in docstrings → one pickle from the pickle jar does not unpickle correctly 
comment:41 Changed 9 years ago by
Cc:  Simon King added 

Added Simon since we talked about this in Bad Boll a while ago.
comment:42 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:43 followup: 44 Changed 8 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 followup: 45 Changed 8 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 padic numbers.
comment:45 followup: 47 Changed 8 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 7 years ago by
Stopgaps:  → todo 

comment:47 Changed 7 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 7 years ago by
Keywords:  days71 added 

Milestone:  sage6.4 → sageduplicate/invalid/wontfix 
Status:  needs_work → positive_review 
We are abandoning this in favor of #20246.
comment:49 Changed 7 years ago by
Resolution:  → invalid 

Status:  positive_review → closed 
Apply 11895.patch