Inconsistency in root finding
Nick Alexander
should return [(1.0000..., 1), (1.0000...., 1)] and be documented as
such.
sage: (CC(1)*(x-1)**2).roots()
[1.00000000000000, 1.00000000000000]
sage: ((x-1)**2).roots()
[(1, 2)]
Nick
didier deshommes
2 here refers to multiplicity. The result of roots() are fine, it's
the behavior accross fields that is inconsistent.
The docs for roots() over QQ say:
{{{
Return all roots of this polynomial.
INPUT:
multiplicities -- bool (default: True, except over RR
or CC)
if True return list of pairs (r, n),
where r is
the root and n is the multiplicity.
}}}
HTH,
didier
didier deshommes
On Mar 16, 2:37 am, "didier deshommes" <dfdes...@gmail.com> wrote:
> On Mar 16, 2:23 am, "Nick Alexander" <ncalexan...@gmail.com> wrote:
>
> > Is this because of precision issues? In that case, I still think this
> > should return [(1.0000..., 1), (1.0000...., 1)] and be documented as
> > such.
>
> > sage: (CC(1)*(x-1)**2).roots()
> > [1.00000000000000, 1.00000000000000]
>
> > sage: ((x-1)**2).roots()
> > [(1, 2)]
>
> 2 here refers to multiplicity. The result of roots() are fine, it's
> the behavior accross fields that is inconsistent.
In other words, I am agreeing with you :)
didier
Nick Alexander
Do you agree that the current behaviour is brain-dead? 'cuz I'll
patch it!
Nick
didier deshommes
> Do you agree that the current behaviour is brain-dead? 'cuz I'll
> patch it!
Agreed! roots() should always return multiplicity when asked to.
didier
>
> Nick
William Stein
>
> On Mar 16, 2:23 pm, "Nick Alexander" <ncalexan...@gmail.com> wrote:
> > Do you agree that the current behaviour is brain-dead? 'cuz I'll
> > patch it!
Please send me a patch, so that it returns multiplicities in all cases.
-- William
Nick Alexander
don't want to fix.
sage: D = {} ; D[CC(0)] = 1
---------------------------------------------------------------------------
<type 'exceptions.TypeError'> Traceback (most recent call
last)
/Users/nalexand/emacs/sage/<ipython console> in <module>()
<type 'exceptions.TypeError'>: unhashable type:
'sage.rings.complex_number.ComplexNumber'
Could someone in the know address this and send me a _TEXT_ patch (the
hg bundles aren't so good when you're in the middle of changes).
Also, if anyone knows how to do the equivalent of sorted(list,
key=func) in sagex, I'd be much obliged. What I want to do is sort
the roots in order of increasing absolute value, but how do you sort a
list of pairs in sagex without using the Schwartzian transform
(decorate-sort-undecorate) or something similar?
Nick
On Mar 16, 12:11 pm, "William Stein" <wst...@gmail.com> wrote:
Mike Hansen
> don't want to fix.
>
> sage: D = {} ; D[CC(0)] = 1
> ---------------------------------------------------------------------------
> <type 'exceptions.TypeError'> Traceback (most recent call
> last)
>
> /Users/nalexand/emacs/sage/<ipython console> in <module>()
>
> <type 'exceptions.TypeError'>: unhashable type:
> 'sage.rings.complex_number.ComplexNumber'
You should be able to just add the following to the ComplexNumber class:
def __hash__(self):
return str(self).__hash__()
That should work so long as the complex number is completely
determined by its __str__. I'm not sure if ComplexNumbers are mutable
or immutable, but if they are mutable, you need to make sure not to
change them while they are dictionary keys; otherwise, bad things will
happen.
I'm not sure about the sort under sagex which reminds me that I should
get a better understanding of pyrex.
--Mike
William Stein
> > <type 'exceptions.TypeError'>: unhashable type:
> > 'sage.rings.complex_number.ComplexNumber'
>
> You should be able to just add the following to the ComplexNumber class:
>
> def __hash__(self):
> return str(self).__hash__()
>
> That should work so long as the complex number is completely
> determined by its __str__. I'm not sure if ComplexNumbers are mutable
> or immutable, but if they are mutable, you need to make sure not to
> change them while they are dictionary keys; otherwise, bad things will
> happen.
Complex numbers are immutable. All numeric types in SAGE
are immutable, including polynomials. The only elements
that are not immutable are matrices (which can be set immutable), and
vectors (which will soon have an immutability flag too).
I've attached a patch for some numerical hashing to this email.
> I'm not sure about the sort under sagex which reminds me that I should
> get a better understanding of pyrex.
Sorting under sagex is exactly the same as under Python,
unless you want to something new at the C level. E.g.,
you can use L.sort(cmp=...) if L is a list.
Nick Alexander
converting to string is not a good idea. Better to hash a tuple of
real, imag I think. (Maybe you did this already?)
I don't seem able to send in a key function sorted; I'll try
sort(cmp=) in a moment. I wonder if I hit a Pyrex bug?
Thanks for the reply.
Nick
On Mar 19, 8:06 am, "William Stein" <wst...@gmail.com> wrote:
> 3490.patch
> 1KDownload
William Stein
> For some reason, google won't let me grab your patch. Anyway,
> converting to string is not a good idea. Better to hash a tuple of
> real, imag I think. (Maybe you did this already?)
You have to be really careful, since if a == b,
then one should strive very hard to have hash(a) == hash(b). Thus, e.g.,
if a is a real and b is a complex number with real part a and imaginary
part 0, if you hash the strings then you get equality of the hashes, but
if you hash the tuple you don't.
That said, I don't think hashing the strings it the right approach,
since it is slow and requires converting to base 10, which sucks. In
real_mpfi.pyx, Carl Witty did this, which is better than hash(str(self)):
def __hash__(self):
return hash(self.str(16))
> I don't seem able to send in a key function sorted; I'll try
> sort(cmp=) in a moment. I wonder if I hit a Pyrex bug?
Possibly. You might have to move the relevant code snippet
to Python or use eval, or at least post a minimal example to
this list.
William
Nick Alexander
On Mar 20, 4:12 pm, William Stein <wst...@gmail.com> wrote:
> On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote:
>
> > For some reason, google won't let me grab your patch. Anyway,
> > converting to string is not a good idea. Better to hash a tuple of
> > real, imag I think. (Maybe you did this already?)
>
> You have to be really careful, since if a == b,
> then one should strive very hard to have hash(a) == hash(b). Thus, e.g.,
> if a is a real and b is a complex number with real part a and imaginary
> part 0, if you hash the strings then you get equality of the hashes, but
> if you hash the tuple you don't.
Hmm, it seems to me that this has deep implications. When hashing,
one really needs to find the 'minimal representation' of the element.
Suppose I want to hash QQ['x'](1), a constant polynomial. This should
hash to the same thing as QQ(1) and ZZ(1), right? Same with (QQ['x'])
['y'](1), etc. And it gets more convoluted when you have more
interesting extension fields.
And what about quotients -- should Mod(1, 3) hash to the same thing as
ZZ(1)? Should (QQ['x']/x^2+1)(1) hash to the hash of ZZ(1)? Should
(QQ['x']/x^2+1)(x) has to the same thing as CC(I)? (For the record, I
think the last one shouldn't happen, but for no strong reason.)
In some sense, we've worked out the general case with the canonical
coercion code. But this is not the same case: here, we want CC(1) to
hash to RR(1), whereas there is no canonical coercion C to R. There
are some conventions around __call__, maybe those hold the correct
answer.
Before I think more about this, do people agree that there are
problems with the current situation? I am interested to know what
will happen when hashing various elements of finite fields, extensions
of finite fields, padic extensions, etc. Same with lattices of number
fields over QQ and ZZ, and embeddings into CC.
Nick
David Harvey
Oh boy I really really don't like where this is going. Insisting on
"a == b" => "hash(a) == hash(b)" with sage's canonical coercion model
seems really really bad.
For example
sage: Integers(123818273)(2394) == Integers(1)(0)
True
So then all integers mod n (for all n) have to hash to the same thing.
Please let's not go there.
David
Robert Bradshaw
There's also the issue of precision, e.g. RDF(0) == RealField(10000)
(1), but
sage: R = RealField(10000)
sage: a = R(1) + R(10)^-100
sage: a == RDF(1)
but I don't think hash(a) should equal (necessarily) hash(1).
If it seems natural (e.g. in this case where the coercion is R -> C),
however, I think it would be nice. One could also force all keys of a
hashtable to live in a given ring.
- Robert
William Stein
> On Mar 21, 2007, at 1:19 AM, Nick Alexander wrote:
> > On Mar 20, 4:12 pm, William Stein <wst...@gmail.com> wrote:
> >> On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote:
> >>> For some reason, google won't let me grab your patch. Anyway,
> >>> converting to string is not a good idea. Better to hash a tuple of
> >>> real, imag I think. (Maybe you did this already?)
> >>
> >> You have to be really careful, since if a == b,
> >> then one should strive very hard to have hash(a) == hash(b).
> >> Thus, e.g.,
> >> if a is a real and b is a complex number with real part a and
> >> imaginary
> >> part 0, if you hash the strings then you get equality of the
> >> hashes, but
> >> if you hash the tuple you don't.
> > Hmm, it seems to me that this has deep implications. When hashing,
> > one really needs to find the 'minimal representation' of the element.
> > Suppose I want to hash QQ['x'](1), a constant polynomial. This should
[...]
> Oh boy I really really don't like where this is going. Insisting on
> "a == b" => "hash(a) == hash(b)" with sage's canonical coercion model
> seems really really bad.
>
> For example
>
> sage: Integers(123818273)(2394) == Integers(1)(0)
> True
>
> So then all integers mod n (for all n) have to hash to the same thing.
>
> Please let's not go there.
Sorry, but we have to go there, again. This has been discussed
before more than once on this list. Here's the definition of __hash__
in the Python reference manual [1]
"__hash__(self)
Called for the key object for dictionary operations, and by the
built-in function hash(). Should return a 32-bit integer usable as a
hash value for dictionary operations. The only required property is
that objects which compare equal have the same hash value; it is
advised to somehow mix together (e.g., using exclusive or) the hash
values for the components of the object that also play a part in
comparison of objects. If a class does not define a __cmp__() method
it should not define a __hash__() operation either; if it defines
__cmp__() or __eq__() but not __hash__(), its instances will not be
usable as dictionary keys. If a class defines mutable objects and
implements a __cmp__() or __eq__() method, it should not implement
__hash__(), since the dictionary implementation requires that a key's
hash value is immutable (if the object's hash value changes, it will
be in the wrong hash bucket)."
Notice the "The only required property is that objects which compare
equal have the same hash value". This is an assumption made by the
Python language, and violating has consequences. Fortunately, the
consequences are pretty clearly
defined and reasonably easy to understand, so if you know about them
they don't cause you trouble. I think the following example
illustrates them pretty well:
sage: v = [Mod(2,7)]
sage: 9 in v
True
sage: v = set([Mod(2,7)])
sage: 9 in v
False
sage: 2 in v
True
sage: w = {Mod(2,7):'a'}
sage: w[2]
'a'
sage: w[9]
Traceback (most recent call last):
...
KeyError: 9
---
That said, we simply can't require
(*) "a == b ==> hash(a) == hash(b)"
in SAGE, because mathematics is simply too complicated for this sort
of rule. So what is done in SAGE is to _attempt_ to satisfy (*) when it
is reasonably easy to do so, but use judgment and not go overboard.
E.g.,
sage: hash(Mod(2,7))
2
I.e., we get 2. That's better than some weird random hash that also
involves the moduli, but it's of course not right from the Python point
of view, since 9 == Mod(2,7). Long ago before we ever had this
discussion about hashing, I think Mod(2,7) was the hash of some
combination of 2 and 7.
Anyway, I hope this clarifies things for people.
David Harvey
On Mar 21, 2007, at 1:37 AM, Robert Bradshaw wrote:
> One could also force all keys of a
> hashtable to live in a given ring.
I don't think you'd want to do that. First, it wouldn't even solve
the problem (e.g. because of the precision issues you raised before
-- you can have two elements of the same ring with different
precision and hence presumably different hashes, which still compare
equal). Second, I can't even see technically how you would do that
without modifying python in some horrible way.
David
David Harvey
On Mar 21, 2007, at 1:38 AM, William Stein wrote:
> That said, we simply can't require
> (*) "a == b ==> hash(a) == hash(b)"
> in SAGE, because mathematics is simply too complicated for this sort
> of rule. So what is done in SAGE is to _attempt_ to satisfy (*)
> when it
> is reasonably easy to do so, but use judgment and not go overboard.
> E.g.,
> sage: hash(Mod(2,7))
> 2
> I.e., we get 2. That's better than some weird random hash that also
> involves the moduli, but it's of course not right from the Python
> point
> of view, since 9 == Mod(2,7). Long ago before we ever had this
> discussion about hashing, I think Mod(2,7) was the hash of some
> combination of 2 and 7.
The only way we could "fix" this problem for good is to abandon using
the "==" operator for "SAGE equality", and implement SAGE equality as
a new method attached to each object. Then we could follow python
rules for "==" and our rules for everything else, and all SAGE code
would become completely unreadable (and for that matter unwriteable).
So I think what you've said above is perfectly reasonable, and we
just have to live with it.
David
Nick Alexander
Are RealField(100) and RealField(200) the same ring? To me, they
aren't, but there is a canonical coercion in one direction. And you
can expect __call__ to map between both.
Is that right?
Nick
Robert Bradshaw
I was thinking manually, say if you wanted to store information
relative to the roots of some polynomial and some were real and
others were complex, or they were given to you with different
precisions.
Robert Bradshaw
> Are RealField(100) and RealField(200) the same ring? To me, they
> aren't, but there is a canonical coercion in one direction. And you
> can expect __call__ to map between both.
>
> Is that right?
> Nick
No, they are not the same ring. Everything else you are saying here
is correct.
Nick Alexander
happen next. Can someone sketch how algebraic extensions (say L/K/Q)
should hash? I suggest:
Q.__hash__ tries to __call__ to Z, and if that fails, hashes how it
does now.
K.__hash__ tries to __call__ to Q, and if that fails, hashes based on
coefficients.
L.__hash__ tries to __call__ to K, and if that fails, hashes based on
coefficients OVER Q.
That does what I think is the right thing. But what if we have L1,L2/
K2/K1/Q, but L1 and L2 are extensions of K1 (so they don't know about
K2). Then an element of L1 that's really in K2 and the same element
of L2 that's really in K2 are supposed to hash the same?
Aside 1: none of the canonical coercions are in place yet, AFAICT.
Aside 2: maybe these issues are easier over GF(p^k), since there is a
standard choice for field representation?
It's making my head spin.
Nick
Robert Bradshaw
operation. Also, it's not possible to have x == y => hash(x) == hash
(y) for a useful hash function. (For example, the equalities z == mod
(z, 2) and z == mod(z, 3) would force hash() to be constant on the
integers.) I think the goal is to make a hash function that is fast
but within reason respects any obvious, natural inclusions (e.g.
given K/F, it shouldn't be hard to make hash(K(a)) = hash(a) for a in
F).
- Robert
William Stein
guide for the next version of SAGE:
> \section{The {\tt \_\_hash\_\_} Special Method}
> Here's the definition of \code{__hash__}
> from the Python reference manual.
>
> \begin{quote}
> Called for the key object for dictionary operations, and by the
> built-in function \code{hash()}. Should return a 32-bit integer
> usable as a hash value for dictionary operations. The only required
> property is that objects which compare equal have the same hash
> value; it is advised to somehow mix together (e.g., using exclusive
> or) the hash values for the components of the object that also play
> a part in comparison of objects. If a class does not define a
> \code{__cmp__()} method it should not define a \code{__hash__()}
> operation either; if it defines \code{__cmp__()} or \code{__eq__()}
> but not \code{__hash__()}, its instances will not be usable as
> dictionary keys. If a class defines mutable objects and implements a
> \code{__cmp__()} or \code{__eq__()} method, it should not implement
> \code{__hash__()}, since the dictionary implementation requires that
> a key's hash value is immutable (if the object's hash value changes,
> it will be in the wrong hash bucket).
> \end{quote}
>
> Notice that ``The only required property is that objects which compare
> equal have the same hash value.'' This is an assumption made by the
> Python language, {\em which in \sage we simply cannot make} (!), and
> violating it has consequences. Fortunately, the consequences are pretty
> clearly defined and reasonably easy to understand, so if you know
> about them they don't cause you trouble. I think the following
> example illustrates them pretty well:
> \begin{verbatim}
> sage: v = [Mod(2,7)]
> sage: 9 in v
> True
> sage: v = set([Mod(2,7)])
> sage: 9 in v
> False
> sage: 2 in v
> True
> sage: w = {Mod(2,7):'a'}
> sage: w[2]
> 'a'
> sage: w[9]
> Traceback (most recent call last):
> ...
> KeyError: 9
> \end{verbatim}
>
> Here's another example,
> \begin{verbatim}
> sage: R = RealField(10000)
> sage: a = R(1) + R(10)^-100
> sage: a == RDF(1)
> \end{verbatim}
> but \code{hash(a)} should not equal \code{hash(1)}.
>
> Unfortunately, in \SAGE we simply can't require:
> \begin{verbatim}
> (*) "a == b ==> hash(a) == hash(b)"
> \end{verbatim}
> because serious mathematics is simply too complicated for this
> rule. For example, the equalities
> \code{z == Mod(z, 2)} and \code{z == Mod(z, 3)}
> would force \code{hash()} to be constant on the
> integers.
>
> The only way we could ``fix'' this problem for good would be to
> abandon using the "==" operator for "\SAGE equality", and implement
> \SAGE equality as a new method attached to each object. Then we could
> follow Python rules for "==" and our rules for everything else, and
> all \SAGE code would become completely unreadable (and for that matter
> unwriteable). So we just have to live with it.
>
> So what is done in \sage is to {\em attempt} to satisfy (*) when it
> is reasonably easy to do so, but use judgment and not go overboard.
> For example,
> \begin{verbatim}
> sage: hash(Mod(2,7))
> 2
> \end{verbatim}
> I.e., we get 2. That's better than some weird random hash that also
> involves the moduli, but it's of course not right from the Python point
> of view, since \code{9 == Mod(2,7)}.
>
> The goal is to make a hash function that is fast but within reason
> respects any obvious, natural inclusions and coercions.
>
>
Nick Alexander
output of "a == RDF(1)" is needed, because I don't know what is
supposed to happen.
Nick
True? Output needed here!
Robert Bradshaw
in RDF (real double field = 53 bits of precision) they are equal.)