Hi Waldek,
h(k) And max()$Singleinteger
Due to your question about HASHSTATEMAKEFIXNUM and representation I realised that there is potential trouble with GCL: in GCL max()$SingleInteger is not a power of 2 minus 1. That is bitwise "and" that we are using may turn some lower order bits to 0, decreasing quality of hash function. So we probably need special version of HASHSTATEMAKEFIXNUM for GCL.
With this GCL danger in mind, I tend to rather require the user to already provide a hash function that does not yield negative SingleInteger values. Modified patch attached.
If you mean changing docstring, you probably guessed that I have doubts about this. Our docstrings are _not_ specification.
Yes. Unfortunately.
I normally try to give enough information in docstrings so that user with general knowledge can "identify" given operation.
I understand that you'd like to have a simple docstring that is easy and quick to understand. What I do not understand is that you seem to be much against additional text that clarify any doubts a user might have.
I, for example, would not have been able to guess from the docstring of rem how the function behaves if negative arguments are involved. And I still don't know whether (if I now use my experiments made with SCBL) I get the same results if I run on a different LISP. Clearly, my wish is that Code written and documented in SPAD does behave the same no matter on which LISP FriCAS runs.
Thanks for you explanation about "pretend".
That would show a difference between Aldor and FriCAS.
Aldor obviously employs "immediate integers". The attached
program gives output:
%>aldor -Fx -laldor int.as
%>./int
1
1
0
1
3
5
9
17
The commented line in int.as would lead to a segmentation fault.
That is certainly different from FriCAS.
%%% (1) -> (1$SingleInteger) pretend Integer
(1) 1
Type: Integer
%%% (2) -> (1$Integer) pretend SingleInteger
(2) 1
Type: SingleInteger
OK, no problem, because there is the dangerous "pretend", but one should
be aware of that when dealing with Aldor and FriCAS at the same time.
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 [email protected].
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/2ea25836-f562-4c5f-bd7a-0e061a3a6277%40hemmecke.org.
int.as
Description: application/applix-spreadsheet
From 8919f59f02c72dace49174ba917f0142d8a79f34 Mon Sep 17 00:00:00 2001 From: Ralf Hemmecke <[email protected]> Date: Thu, 19 Dec 2024 15:54:55 +0100 Subject: use rem instead of positiveRemainder --- src/algebra/hashstate.spad | 3 ++- src/algebra/xhash.spad | 21 +++++++-------------- 2 files changed, 9 insertions(+), 15 deletions(-) diff --git a/src/algebra/hashstate.spad b/src/algebra/hashstate.spad index ca95aa31..bd04fdf8 100644 --- a/src/algebra/hashstate.spad +++ b/src/algebra/hashstate.spad @@ -58,7 +58,8 @@ HashState() : with ++ update!(hs, x) computes new values of HashState from hs ++ and x and might destructively operate on its first argument. value : % -> SingleInteger - ++ value(x) returns a SingleInteger value corresponding to x. + ++ value(x) returns a non-negative SingleInteger value + ++ corresponding to x. == add -- These two macros are necessary to distinguish between Rep and \%. rep x ==> (x@%) pretend Rep diff --git a/src/algebra/xhash.spad b/src/algebra/xhash.spad index 6c101ea6..2c626285 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)) @@ -111,6 +102,8 @@ XHashTable(Key: Hashable, Entry: Type): ++ 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. + ++ For XHashTable to work correctly, the function h must only + ++ yield non-negative values. == add KE ==> Record(key: Key, entry: Entry) UE ==> Union(Entry, "failed") @@ -341,9 +334,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 := (h k)::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
