From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <9front-bounces@9front.inri.net> X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from 9front.inri.net (9front.inri.net [168.235.81.73]) by inbox.vuxu.org (Postfix) with ESMTP id 009482028A for ; Thu, 4 Apr 2024 23:02:01 +0200 (CEST) MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit Received: from layka.disroot.org ([178.21.23.139]) by 9front; Thu Apr 4 17:00:38 -0400 2024 Received: from localhost (localhost [127.0.0.1]) by disroot.org (Postfix) with ESMTP id C336144DB2 for <9front@9front.org>; Thu, 4 Apr 2024 23:00:34 +0200 (CEST) X-Virus-Scanned: SPAM Filter at disroot.org Received: from layka.disroot.org ([127.0.0.1]) by localhost (disroot.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fJwxLUkPFWDj for <9front@9front.org>; Thu, 4 Apr 2024 23:00:32 +0200 (CEST) Date: Thu, 04 Apr 2024 23:00:31 +0200 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1712264432; bh=5z86GG1+j5nCnK10PoXKjr7o/b5/e7w+Xu0NaKe0tjI=; h=Date:To:Subject:From:References:In-Reply-To; b=KAyb6KC0yHzALH6fdXorh2mew0mvvwt4NqMawOyb895wgxFG/fsqTTPVgTCMi/mbm o2hn6HdY6A+VqU6GYWuax7cOOhEoKAgI3IX03k7l+ukmdlQTgld2B3vJcj0Z17o9wc Y16BZ63sRwLHgE1k2WzaDfb86gpbjKNbyKK4XZorj+p4Qa3C3gGSkLUixA5GSsY+J2 wGsp7rrFBnMu32NiDb8pcPL3PO/YNXXao4yq3T/o0Z3ztvMHa962q+y0FURuSenJxs ZIYGhQWJmXF3RUy+MH8wGJESCL0owadBWAz50cvJ3eh1wyC0DUKnAbVMhnr5QuhNbG z1lIwLWsWUi8A== To: 9front@9front.org From: Eolien55 References: In-Reply-To: Message-Id: <1ZNZIE3BLUACX.29LP517J7M82J@e55-lap.my.domain> List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: webscale out-scaling method factory storage-aware frontend Subject: Re: [9front] [PATCH] libc: replace lrand's algorithm Reply-To: 9front@9front.org Precedence: bulk qwx@sciops.net wrote: > I think at this point it would be better to look at a patch, with the > changes mentioned after the first post, and a sweep through the other > implementations. There are some odd occurrences as you found; libc's > frand() is also somewhat suspect but will likely need to change if > lrand() does. We need a 16bit, 32bit, floating point, and possibly > 64bit variant; this will clean up some code and remove some > redundancies which is always nice. Perhaps take the extreme route and > do *all* of the changes you'd like to see, so we could more easily > discuss each case. I don't currently have the time, but I think I'll work on it, probably next week. Having a good double/float PRNG surprisingly hard to implement. See [1] for multiple approaches. > We then need to check if there's a performance impact on non-amd64 > arches. For xoroshiro128+ vs. pcg I'd be interested to know if > there's any significant difference between the two in statistical > properties and performance; if we make a change, it'd be nice to > pick the best alternative and make it once and for all. Code size > and simplicity also counts. Is there any other variant that should > be assessed? I believe PCG has the smallest code size, and is also the one with best statistical properties, all things considered. Other alternatives of xoroshiro have better statistical properties, such as xoroshiro128**. However, if we plan on having 64-bit generators, xoroshiro256** will probably be simpler and shorter to implement. PCG64 requires 128-bit operations, which need to be emulated (and that is quite complex). xoroshiro256** would be simpler, since it uses 4 32-bit integers. I am a bit skeptic of xoroshiro256**'s statistical quality. Its output function can be easily inversed, by multiplying by 57 for example, which reveals the inner LFSR, with all its statistical flaws. Multiplying it by 57 yields very very statistically bad generator (it fails within 4MB!). It is also "too big to fail", in that empirical tests cannot reasonably show its flaws, for its period is simply too large for it to be fully tested. See [2] for more material on the matter. But that's very much "my opinion man" territory. I think I'd choose PCG because its quality is good despite its small state, and because reduced versions of it pass statistical tests (whereas many other 'reduced' (as in, with smaller state as normal) PRNGs fail them even with larger state). In the end, both are very comparable. If statistical quality matters more than code size, and if emulating 128-bit addition and multiplication isn't a problem, then I believe PCG should be chosen. If it's the other way around, I'd probably go for xoroshiro**. Cheers, Elie Le Vaillant [1] http://mumble.net/~campbell/tmp/random_real.c [2] https://pcg-random.org/blog/