Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 9 Mar 2015 19:14:57 +0530
From: Sayantan Datta <>
To: john-dev <>
Subject: Re: 256/128 bit integer arithmatic

On Mon, Mar 9, 2015 at 7:00 PM, Aleksey Cherepanov <>

> For a given set of values, you can make a perfect hash table.
> 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.


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.