Path: ...!news.nobody.at!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita Montero <Bonita.Montero@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Thu, 30 May 2024 11:27:17 +0200
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <v39gpj$1kkhu$1@raubtier-asyl.eternal-september.org>
References: <v2n88p$1nlcc$1@dont-email.me>
 <v2qm8m$2el55$1@raubtier-asyl.eternal-september.org>
 <v2qnue$2evlu$1@dont-email.me> <v2r9br$2hva2$1@dont-email.me>
 <86fru6gsqr.fsf@linuxsc.com>
 <v2sudq$2trh1$1@raubtier-asyl.eternal-september.org>
 <8634q5hjsp.fsf@linuxsc.com>
 <v2vmhr$3ffjk$1@raubtier-asyl.eternal-september.org>
 <86le3wfsmd.fsf@linuxsc.com>
 <v2voe7$3fr50$1@raubtier-asyl.eternal-september.org>
 <86ed9ofq14.fsf@linuxsc.com>
 <v2vs40$3gflh$1@raubtier-asyl.eternal-september.org>
 <v317u2$3td1f$1@raubtier-asyl.eternal-september.org>
 <87ikyyntae.fsf@bsb.me.uk>
 <v39c9e$1js0q$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 30 May 2024 11:27:16 +0200 (CEST)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="4f77e9ad9c96e0a8deefbb7b6a4db45f";
	logging-data="1724990"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19V5Eh/c+rFSHlsyLUQkrPWR4tz6c5gYrI="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:Zsk7lr8knOGOv0d9bLY27z96KG0=
In-Reply-To: <v39c9e$1js0q$1@raubtier-asyl.eternal-september.org>
Content-Language: de-DE
Bytes: 2982

I further improved my code to show sth. which hasn't to do anything
with the initial question. If I don't multiply an indexed value but
a random value with the prime I still get a random value. The dis-
tribution of the bucked-depths is then 1 / (e * N!), which is accor-
ding to the coupon collector's problem:

#include <iostream>
#include <vector>
#include <random>

using namespace std;

int main()
{
	constexpr bool SIXTEEN = true;
	using width_t = conditional_t<SIXTEEN, uint16_t, uint32_t>;
	constexpr width_t PRIME = SIXTEEN ? 65521 : 0xFFFFFFFBu;
	constexpr size_t N = (size_t)(width_t)-1 + 1;
	vector<uint8_t> buckets;
	auto distrib = [&]( auto gen )
	{
		buckets.resize( 0 );
		buckets.resize( N );
		for( size_t b = buckets.size(); b; )
			if( !++buckets[gen( (width_t)--b ) * PRIME & (width_t)-1] )
				return;
		vector<size_t> loads;
		for( uint8_t ld : buckets )
		{
			if( loads.size() <= ld )
				loads.resize( ld + 1 );
			++loads[ld];
		}
		for( size_t l = 0; ptrdiff_t ld : loads )
			cout << l++ << ": " << 100.0 * ld / N << "%" << endl;
	};
	distrib( []( width_t i ) { return i; } );
	cout << endl;
	mt19937_64 mt;
	uniform_int_distribution<uint32_t> uid( 0, -1 );
	distrib( [&]( width_t ) { return uid( mt ); } );
}