Bill Page wrote:
>
> 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.
I specifically wrote "given set of independent kernels". Just
now I do not want to think what happens if you give input which
violates implicit assumptions about independence of kernels
made in Expression. Equality in expression computes difference
of two expressions treating them as rational functions of kernes.
Then it reduces powers of algebraic kernels takes into account
their defining relations. If after that you get 0, than
expression are deemed equal, otherwise unequal. If there
are no dependent algebraics this is just equality in apropriate
algebraic extension of field of rational functions. For such
fields a standard fact is that a given function is equal to
one without algebraics. The equality you noted is just
an example, after all canonical form of x is supposed to
be equal to x.
Note: if you introduce dependent kernels most of the times
you get sensible results. But you may also get nonsense
regardless of any problems due to hashing.
> > 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?
When it comes to hash _we_ are FriCAS designers. In Axiom code we
inherited hashing was mostly unimplemented, but implemented part
did not guarante anything. I tried to make sure that hash gets
implemented in way compatible to equality in domans. In
particular I removed default implementation via SXHASH which
violated this condition and I left unimplemented cases where
simple implementation _could_ violate compatibility of
equality and hash.
And I think that only sane use of hash tables is when hash
and equality are compatible. Users of hash tables should
insure this, possibly by modifying equality like 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.
Right, in this specific case your implementation is more
efficient. But I do not think that we should optimize
for such use case -- it looks quite unusual.
--
Waldek Hebisch
[email protected]
--
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.
