[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CA+TsHUBWsK_03gGLzRmDY+GgE9KO29pTsEr9GTx4OTJXXsYM9A@mail.gmail.com>
Date: Mon, 9 Mar 2015 19:14:57 +0530
From: Sayantan Datta <std2048@...il.com>
To: john-dev <john-dev@...ts.openwall.com>
Subject: Re: 256/128 bit integer arithmatic
On Mon, Mar 9, 2015 at 7:00 PM, Aleksey Cherepanov <lyosha@...nwall.com>
wrote:
> For a given set of values, you can make a perfect hash table.
> https://en.wikipedia.org/wiki/Perfect_hash
>
> For a small set (up to 256 elements) you may try something like:
> ((v >> C1) ^ (v >> C2) ^ (v >> C3)) & 0xff
> where v is a input value and C1, C2, C3 are constants. You compute
> these constants when you take a set (with this particular function, it
> may not be possible to construct a function for a certain given set).
> And the function gives an index.
>
> Though for 10M, something more complex is needed. To compute
> variable part of function for each set may be quite long even with
> smarter algorithms.
>
> Also the variable part should be inserted into the code. It may
> add compilation time or need "low level gpu" task to be done.
>
I'm implementing an algorithm by Lefebvre and Hoppe in their paper 'Perfect
Spatial Hashing'. Although they are from a different domain i.e computer
graphics but the same technique can be applied in our case. I have a naive
implementation ready and looking for ways to optimize it.
Regards,
Sayantan
Content of type "text/html" skipped
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
