How to subdivide integer hash into ranges

Question

I have unsigned 64bit number, representing mantissa, or fraction (which represent range from [0..1), where 0.0 maps to 0 and 0xffffff.. maps to a number "just before 1.0")

Now i want to split this range into equal buckets - and to answer - given random number key, to which part of the range it will fall to?

Its easier to get from following code:

func BucketIndex(key, buckets uint64) uint64 {
    return uint64(float64(key) / ((math.Pow(2, 64) / float64(buckets)))
}

My attempt to "hack this over" - was to split 2^64 to two, like if I will reduce range to 32bit, and operate in 64bit in order to conduct math:

// ~=key / ((1 << 64) / buckets)
return ((key >> 32) * buckets) >> 32

but ranges stopped to be equal.. eg one third (buckets==3) will be at 0x5555555600000000, instead of being at 0x5555555555555556 thats sad story, so im asking do you know of a better methods of finding (1 << 64) / buckets?

Answer 1

If buckets is (compile-time) constant, you may use constant expression to calculate bucket size: constants are of arbitrary size. Else you may use big.Int to calculate it at runtime, and store the result (so you don't have to use big.Int calculations all the time).

Using a constant expression, at compile-time

To achieve an integer division rounding up, add divisor - 1 to the dividend:

const (
    max        = math.MaxUint64 + 1
    buckets    = 3
    bucketSize = uint64((max + buckets - 1) / buckets)
)

Using big.Int, at runtime

We can use the above same logic with big.Int too. An alternative would be to use Int.DivMod() (instead of adding buckets -1), and if mod is greater than zero, increment the result by 1.

func calcBucketSize(max, buckets *big.Int) uint64 {
    max = max.Add(max, buckets)
    max = max.Add(max, big.NewInt(-1))
    return max.Div(max, buckets).Uint64()
}

var bucketSize = calcBucketSize(new(big.Int).SetUint64(math.MaxUint64), big.NewInt(3))