On Thu, Dec 19, 2024 at 02:14:03PM +0100, 'Ralf Hemmecke' via FriCAS - computer
algebra system wrote:
> On 12/17/24 23:59, Waldek Hebisch wrote:
> > 'positiveRemainder' (that is about 30% of 'localSearch' is due to
> > 'positiveRemainder'). 'positiveRemainder' is more expensive than
> > necessary, because it can handle Integer. However, AFAICS the
> > numbers involved are nonnegative SingleInteger-s and 'rem' from
> > SingleInteger should work fine.
>
> Looking at the code I wonder a bit why I used both Integer and
> SingleInteger. The reason must have been that PrimitiveArray(S) uses
> #: % -> NonNegativeInteger and elt: (%, Integer) -> S, but we have
> hash: % -> SingleInteger. So we must anyway have a conversion between
> Integer and SingleInteger, although we could for efficiency reasons let
> XHashTable use an adhoc implementation of PrimitiveArray (which is not seen
> outside of XHashTable) that uses SingleInteger for indexing. OK, but that
> was not your question.
>
> The positiveness is important to get a proper index into the array.
> And no, the numbers involved are not necessarily only non-negative.
>
> 1) The value function from HashState claims to return a SingleInteger
> (see http://fricas.github.io/api/HashState.html) and not a
> "non-negative SingleInteger".
>
> 2) In XHashTable, one can create a new table via the function
> table: (Key -> SingleInteger) -> %.
>
> While (1) can easily be resolved by adding some text to the specification of
> "value" saying that the returned integer will be non-negative (because
> according to our current implementation it is, in fact, the case), I am not
> so sure about (2). Requiring the user to provide only hash functions that
> return non-negative SingleInteger, is possible, but I fear that this might
> be overlooked and then leading to
> indexing errors while using XHashTable.
>
> I would rather keep a safety meassure inside XHashTable. And probably that
> was the reason why I chose positiveRemainder over rem.
You can do what 'value' in 'HashState' is doing, that is drop
sign bit using bitwise and. Bitwise and is much cheaper than
'positiveRemainder'.
>
> Thinking about that actual reason for XHashTable, it makes, of course, sense
> to care about efficiency. However, I started this domain, because there was
> nothing that would allow me my own hashing function. So
>
> table: (Key -> SingleInteger) -> %
>
> is an important function.
>
> Discussion is open of what compromise between speed and safety is to be
> taken here.
Actually, if you want your own hash function you should also want
your own "equality" function. Namely, hash and "equality" naturally
make a pair. And for several domains hash matched with mathematical
equality is hard or impossible to define, while hash and "equality"
for representation may be reasonably easy and useful.
--
Waldek Hebisch
--
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 fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/Z2QgqJICSSjMOh_3%40fricas.org.
