On 1 April 2015 at 02:26, Waldek Hebisch <[email protected]> wrote: >> >> On 31 March 2015 at 18:21, Waldek Hebisch <[email protected]> wrote: >> ... >> > For expression equality requires >> > computing difference, while simple hash would remove irrationalities >> > from denominators, which is much more involved. >> >> Expressing the difference of two rational functions as a rational >> function involves at least the product of two polynomials but I admit >> that I am not certain that it is even possible to define a compatible >> hash function for expression equality defined in this way. Could you >> explain what you mean by removing irrationalities from the >> denominators? > > For example transforming: > > 1/sqrt(x^2 + 1) into sqrt(x^2 + 1)/(x^2 + 1) > > This is trivial case, but in general all algebraics (in particular roots) > can be removed from denominator to numerator, so that denominator > is purely transcendental. If you also normalize numerator in some > way (for example by forcing leading coefficient to 1) then > for given set of independent kernels you get canononical form. >
I think that such transformations do not respect all possible definitions of equality, but your claim then is that it is possible to get a canonical form for all expressions in the Expression domain relative to whatever is meant by equality ( =$Expression ) in this domain? Noting for example that 1/sqrt(x^2 + 1) - sqrt(x^2 + 1)/(x^2 + 1) does in fact already evaluate to 0. > ... >> >> > 2) What you write above looks like attempt at error hiding. >> > If essential precondition is violated, then more approprate >> > reaction is to signal error. >> >> Yes perhaps but in 'xhash.spad' Ralf wrote: >> >> table: (Key -> SingleInteger) -> % >> ++ table(h) creates an empty hash table that uses h instead of >> ++ hash$Key. Note that h should be a mathematical function in >> ++ the sense that from k1=k2 follows h(k1)=h(k2). If that is not >> ++ the case, k1 and k2 will internally be considered as being >> ++ different keys. >> >> My suggested change would only do what he claims. > > Ralf should say if he cares about this specification. Apparently his answer is that he does not care. :( > AFAICS > currently even if we ignore problem with rehash this does > not work. Namely consider case when eq(k1, k2) holds but h(k1)~= h(k2). That is exactly the case I was considering. > Still, k1 and k2 may map to the same slot (because we reduce hashes > to smaller range, so after reduction values may match). Without > extra test we will store one of k-s and ignore the second. > Yes, but not ignore. It is important to remember what happens to the entry part of the (key,entry) pair in this case. > To fix this basically in any place you use 'eq' we would have use > your variant. Yes. There are only two places in the code where eq is used. I mentioned both places in my email. > We could say that k1 and k2 _may_ be treated > as different and modify rehash to ignore (drop) duplicates. No. In that case the table behaves unpredictably after rehash because corresponding entries are dropped. > But then you may inseret the same key case several times: > > you insert k1 > you insert k2 because it maps to different slot > rehash: k1 and k2 map to the same slot, drop one say k1 > reshash: k1 and k2 map to different slots > you insert k1 > rehash: k1 and k2 map to the same slot, drop one say k2 > reshash: k1 and k2 map to different slots > you insert k2 > ... > > That looks crazy for me, so while it is easy to specify > and probably to implement I do not think we want this. I agree that we do not want this. > > If treating k1 and k1 is really desirable, then custom > eq, for example > > eq(x, y) == > x = y and hash(x) = hash(y) > > looks like reliable way. This has advantage that normal > case is not burdened with extra computations Are you saying that if no argument is passed, we can assume (hope?) that the FriCAS designers have already guaranteed that the hash$Key and =$Key are compatible, so then eq just defaults to =$Key. But if we want a custom hash and/or equality, then we would locally define eq as above? My proposal optimized the (re-)calculation of hash(x). This seems a bit harder to do if we want it only in the latter case. At minimum I guess we need to test a flag which could then be moved outside the while loops. > -- we do extra work only when needed. > What you wrote actually does extra work if hash is passed: It recomputes both hash(x) and hash(y) every time eq is evaluated. The specific way eq (or =$Key) is used in XHashTable makes it possible to compute hash(x) for the target key x just once, then hash(y) and eq(x,y) for each y in some set of y's already in the table. Bill. -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" 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 http://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
