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.