LATEX-L Archives

Mailing list for the LaTeX3 project

LATEX-L@LISTSERV.UNI-HEIDELBERG.DE

Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Condense Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Sender:
Mailing list for the LaTeX3 project <[log in to unmask]>
Date:
Fri, 22 Jun 2018 09:44:45 +0200
Reply-To:
Mailing list for the LaTeX3 project <[log in to unmask]>
Subject:
MIME-Version:
1.0
Message-ID:
In-Reply-To:
<[log in to unmask]> (Will Robertson's message of "Fri, 22 Jun 2018 16:46:41 +0930")
Content-Type:
text/plain
From:
David Kastrup <[log in to unmask]>
Parts/Attachments:
text/plain (35 lines)
Will Robertson <[log in to unmask]> writes:

> On 22 Jun 2018, at 5:54 am, David Kastrup <[log in to unmask]> wrote:
>> 
>> A stupid question that just occured to me: should we be discouraging
>> registering prefixes that match another prefix' contribution to the
>> overly simplistic hash function used in almost all TeX engines?
>
> Would it be easier to update the hash function in the engines? :)

Probably.

> What would be the easiest way to test for clashes?

Well, the hash function is just

@<Compute the hash code |h|@>=
h:=buffer[j];
for k:=j+1 to j+l-1 do
  begin h:=h+h+buffer[k];
  while h>=hash_prime do h:=h-hash_prime;
  end

So basically it's multiplying the ASCII codes by increasing powers of
two from right to left before reducing modulo hash_prime.  hash_prime
will tend to stay around for a few years until getting bumped but there
will be collisions even before the modulo operation.

Prefixes will tend to be less than 20 letters, so any programming
language offering 32bit integers should be fine for finding collisions
even before reducing modulo hash_prime.

-- 
David Kastrup

ATOM RSS1 RSS2