hashing polynomials

jocaps
Messages : 118
Inscription : lun. avr. 17, 2017 4:32 pm

hashing polynomials

Message par jocaps » ven. avr. 27, 2018 1:55 pm

Hi,

Maybe this is a giacpy tip of the day, or maybe this is a question...

In python it would sometimes be beneficial if you could put some giacpy gen types into a dictionary or a set. As a simple example, consider a polynomial x^2+1. The following code will fail

Code : Tout sélectionner

from giacpy import giac
f=giac("x^2+1")
hash(f) # fails, thus..
s=set()
s.add(f) # also fails... and
d={}
d[f]="some dict value" # also fails
There is a workaround maybe. One could convert the polynomial (for the time being I am assuming univariate, I do not want to know what happens if I have more variables) into a list uniquely represented in giac.
Continuing with the code ...

Code : Tout sélectionner

t = tuple(int(i) for i in f.e2r())
s=set.add(t)
d[t]="some dict value"
Notice the following:
I need to convert the values in f.e2r() into int (because they are still gen types which are unhashable)
I cannot use e.g. str(f) instead of f.e2r() because I might have different ordering of the monomials in strings representing the same polynomial.

Do you think this is the best way I am handling this. So far this is my only solution.

Jose

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re:

Message par frederic han » lun. avr. 30, 2018 7:39 am

Indeed I should have add a hash method but I don't know a hash function for a gen in giac.

Bernard, is there already some hash function in giac that I could use because I fear that:

Code : Tout sélectionner

    def __hash__(self):
        return hash(str(self))
would help but it could be very slow.

jocaps
Messages : 118
Inscription : lun. avr. 17, 2017 4:32 pm

Re:

Message par jocaps » lun. avr. 30, 2018 12:59 pm

frederic han a écrit :Indeed I should have add a hash method but I don't know a hash function for a gen in giac.

Bernard, is there already some hash function in giac that I could use because I fear that:

Code : Tout sélectionner

    def __hash__(self):
        return hash(str(self))
would help but it could be very slow.
I think using str is a bad idea e.g. for polynomials. Because converting a polynomial to string depends on the order for which the monomials occur. So two polynomials defined with different order of monomials will have a different hash value. For polynomial, I suggested e2r (which is invariant from the order of monomials).

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re:

Message par parisse » lun. avr. 30, 2018 6:41 pm

giac has C++ hash functions, but not exposed to the userspace because they work on monomial indices of multivariate polynomials, like

Code : Tout sélectionner

  class hash_function_object {
  public:
    size_t operator () (const index_t & v) const { return index_hash_function(v); }
    hash_function_object() {};
  };
Perhaps you can work with something like convert(e2r(3*x*y+2*y+1,[x,y]),list)? Back conversion with convert(,,polynom)

Répondre