#20246: Use `with strict_equality(True)` to work around hashing of p-adics
----------------------------------+------------------------
Reporter: saraedum | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-7.2
Component: padics | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #16342, #16339 | Stopgaps:
----------------------------------+------------------------
Changes (by saraedum):
* branch:
u/saraedum/use__with_strict_equality_true___to_work_around_hashing_of_p_adics
=>
Old description:
> TODO: Explain what happens here.
>
> Here are some timings. In all these examples, `X = toric_varieties.dP8()`
> and we consider `%timeit [X.cohomology_basis(1) for i in range(1000)]`.
>
> The current `cachefunc.pyx` (using `_cache_key` in a try-finally-block):
> {{{
> 1000 loops, best of 3: 419 µs per loop
> }}}
> The old version which does not handle unhashable objects at all:
> {{{
> 1000 loops, best of 3: 387 µs per loop
> }}}
> The proposed implementation:
> {{{
> 1000 loops, best of 3: 395 µs per loop
> }}}
New description:
Only fixed modulus p-adic numbers can implement an obvious hash functions.
Currently some other p-adic elements do which causes 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 a global state which indicates whether
we are currently using "strict precision", i.e., only considering elements
as equal if they are indistinguishable in computations. This is set by
wrapping code in `with strict_precision(True):` and should be used when
caching takes place. If this is not set, p-adics are unhashable.
Here are some alternatives that we're discussed as part of #11895:
* 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.)
* Make p-adics entirely unhashable but add a special `_cache_key` which
the caching framework is aware of. (This is how it is currently
implemented for p-adics in unramified extensions.) The problem with this
solution is that you have to add these `_cache_key` methods to all classes
whose `__hash__` might rely on a `p`-adic number somehow (matrices,
polynomials, ...) which is ugly.
Here are some timings. In all these examples, `X = toric_varieties.dP8()`
and we consider `%timeit [X.cohomology_basis(1) for i in range(1000)]`.
The current `cachefunc.pyx` (using `_cache_key` in a try-finally-block):
{{{
1000 loops, best of 3: 419 µs per loop
}}}
The old version which does not handle unhashable objects at all:
{{{
1000 loops, best of 3: 387 µs per loop
}}}
The proposed implementation:
{{{
1000 loops, best of 3: 395 µs per loop
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/20246#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
