From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id B8766388459A; Wed, 19 Jun 2024 06:38:47 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B8766388459A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1718779127; bh=SjAsZ9+P8wmQ/+rj++/atJM64ufQQ4Nx+P4Fwew2Q1w=; h=From:To:Subject:Date:In-Reply-To:References:From; b=rhKLRWgItHogsQPGIIMVGkjyFAbsl6LLH3SG/BAOakQib7JZ/48XJspm8JBf1x1TM cdPuhBMSOvvN2voJLR1vCpldGV66mAWs+PdISqbXwjR7RatrK3UUUK1O2/zPa5UwIt BPBxZNDARbW9qeQVXjT6id16QuUhJ0iNnYKJBw5A= From: "agriff at tin dot it" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements Date: Wed, 19 Jun 2024 06:38:44 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Version: 8.2.1 X-Bugzilla-Keywords: patch, wrong-code X-Bugzilla-Severity: normal X-Bugzilla-Who: agriff at tin dot it X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: cc Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D88935 Andrea Griffini changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |agriff at tin dot it --- Comment #12 from Andrea Griffini --- Even assuming rand() were generating hardware random numbers (not allowed by the standard because of srand, obviously), gcc would still be broken and performing a terrible random_shuffle with ranges larger than 64k elements (indeed non-uniformity becomes evident even at much smaller ranges). Mingw's rand() numbers are decent enough (and the period is not just 2**16,= for example) but they're only 16 bit. This is allowed. The gcc bug is that it uses rand() (that can be just 16) bit to pick a rand= om number between 0 and the size of the range even when the range is much bigg= er than 65536. Using rand() to feed data into a xorshift64 or something similar only for large ranges would fix, and would also keep shuffle of small ranges backward compatible (shuffling elements in small ranges exactly as current implementation does if starting from the same random seed). I've somewhere an half backed patch for doing that but quite frankly I don't know if I should polish it and submit here as, in all honesty, seems that in this case the maintainers simply don't want to have this bug fixed, for rea= sons that I really cannot understand.=