Re: [bloom] Benchmarks with Knuth multiplier-based hash production

From: Peter Dimov (pdimov_at_[hidden])
Date: 2025-06-07 08:32:19

Joaquin M López Muñoz wrote:
> El 07/06/2025 a las 1:33, Peter Dimov via Boost escribió:
> > Joaquin M López Muñoz wrote:
> >> Hi,
> >>
> >> As per feedback given here:
> >>
> >> https://lists.boost.org/Archives/boost//2025/05/259548.php
> >>
> >> I've experimented with the  hash production scheme suggested by
> >> Kostas, where h_{i+1} is calculated as h_i * 6364136223846793005 mod
> 2^64:
> > Where does this multiplier come from?
> 
> This is the constant suggested by Kostas. A search on the Internet suggests this
> is used in connection with so-called PCG algorithms.

Wikipedia lists it as "MMIX by Donald Knuth", 6364136223846793005 * x + 1442695040888963407 mod 2^64.

This is an LCG multiplier (used with b != 0), so it's not clear whether it would be
"good" for an MCG (b == 0).

For multipliers my go-to reference is Vigna and Steele, https://arxiv.org/pdf/2001.05304.

For MCG mod 2^64, it gives 0xf1357aea2e62a9c5 as the "good multiplier".