Hi Martin,
On Wed, Nov 18, 2020 at 10:41:13AM +1100, Martin Thomson wrote:
> The function I've been thinking of looks like this:
>
> def grease(n):
> v = 27
> i = 1
> while n > 0:
> v = (v << i) | (n & 1)
> i = i + 1
> n = n >> 1
> return v
>
> This is bit spreader, taking the bits of the random value and adding
> progressively more space between each bit.
What about:
(35 + 35 * (i % 18) / 18) << (i / 18) - 35
for i in 0..1023
It returns progressive values from 0 to 2^62-35 following an exponential
curve, thus all encodings will be evenly spread. While it relies on a
56-bit shift, it doesn't require more than 10 bits operations at a time,
but needs unsigned arithmetics. We can keep only the 6 higher bits set
with all the remaining ones to zero and avoid unsigned overflow by
simplifying it like this:
(34 + 35 * (i % 18) / 18) << (i / 18)
It only varies the upper bits. It also has the benefit of being easy to
validate by checking that the value is exactly one of these 18 values
followed by any number of zeroes: 34,35,37,39,41,43,45,47,49,51,53,
55,57,59,61,63,65,67 (i.e. (value >> fls(value)) equals one of these).
Just my two cents,
Willy
