On 12/19/24 14:33, Waldek Hebisch wrote:
You can do what 'value' in 'HashState' is doing, that is drop
sign bit using bitwise and. Bitwise and is much cheaper than
'positiveRemainder'.
See attached proposal.
The only problem I have with
h1: Z := ((HASHSTATEMAKEFIXNUM(h k)$Lisp) pretend I)::Z
is that it introduces another place in the algebra code that uses a call
to Lisp. If that would be what you suggest, then I'd rather prefer to
require the user to provide a non-negative hashing function. The latter
then would not add a needless chopping of bits for the default hash
function value coming from HashState.
"rem" is, in fact, not properly specified. What tells me that the result
of 5 rem 4 is 1 and not -3?
The docstring of "rem" for Integer is
rem: (%, %) -> %
x rem y is the same as divide(x, y).remainder. See divide.
divide: (%, %) -> Record(quotient: %, remainder: %)
divide(x, y) divides x by y producing a record containing a quotient
and remainder, where the remainder is smaller (see sizeLess?) than
the divisor y.
And we have ...
%%% (9) -> for i in [5,-5] repeat for j in [4, -4] repeat print(i rem j)
1
1
- 1
- 1
And sizeLess?(+/-1, +/-4) is true for all 4 combinations of the sign. So
it is, in fact, unclear wheter rem gives a positive or negative value.
So that speaks against the usage of 'rem' (even though, of course, our
implementation always returns a positive value for positive input).
I'd like to make the specification of 'rem' more precise in the same patch.
BTW, can you say whet
convert(x : %) : Integer == x pretend Integer
qconvert(x : Integer) : % == x pretend %
are actually doing internally? Integer and SingleInteger surely have not
the same representation. Does "pretend" do any conversion in FriCAS.
My belief up to this point was that "pretend" is just like a type cast
in C, i.e. no change in the underlying bit representation.
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.
Sure, but XHashTable maybe interesting for people implementing their own
datastructures. It would be their responsibility to use XHashTable
accordingly.
Ralf
--
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/15f2b233-c69d-4773-b408-6d676ae1e8ef%40hemmecke.org.
From d58bb59b814fe5243135e7b0b2e7f086445332b1 Mon Sep 17 00:00:00 2001
From: Ralf Hemmecke <r...@hemmecke.org>
Date: Thu, 19 Dec 2024 15:54:55 +0100
Subject: use rem instead of positiveRemainder
---
src/algebra/xhash.spad | 19 +++++--------------
1 file changed, 5 insertions(+), 14 deletions(-)
diff --git a/src/algebra/xhash.spad b/src/algebra/xhash.spad
index 6c101ea6..1ab3b690 100644
--- a/src/algebra/xhash.spad
+++ b/src/algebra/xhash.spad
@@ -1,16 +1,7 @@
)abbrev domain XHASHTBL XHashTable
)if LiterateDoc
\documentclass{article}
-\usepackage{url}
-\usepackage{color}
-\definecolor{bgcode}{rgb}{1,1,0.7}
-
-\usepackage{listings}
-\lstdefinelanguage{spad}{basicstyle=\footnotesize\ttfamily,%
- numbers=left,firstnumber=last,backgroundcolor=\color{bgcode}}
-\parindent0pt
-\parskip\medskipamount
-
+\usepackage{literatedoc}
\begin{document}
\title{A hash table implementation via double hashing}
\author{Ralf Hemmecke}
@@ -45,7 +36,7 @@ respectively. \texttt{VACANT} and \texttt{DELETED} should not be part
of the key space.
Let's assume that the type of the marker values is \texttt{Marker}.
-Naively, and type correctly, we would have to use as representation
+Naively, and type correctly, we would have to use a representation
like the following.
\begin{verbatim}
Union(Marker, Record(key: Key, entry: Entry))
@@ -341,9 +332,9 @@ stored and thus the loops eventually terminate.
mk := getMKey(a, p)
n: Z := numOfBuckets a
- h1: Z := (h k)::Z
- p: Z := positiveRemainder(h1, n) -- position in array
- h2: Z := 1 + positiveRemainder(h1, n-2)
+ h1: Z := ((HASHSTATEMAKEFIXNUM(h k)$Lisp) pretend I)::Z -- h1>=0
+ p: Z := h1 rem n -- position in array (p>=0)
+ h2: Z := 1 + (h1 rem (n-2)) -- h2>=0
mk: MKey := getMKey(a, p)
deletedPosition?: Boolean := false
while not vacant? mk repeat
--
2.43.0
