Raymond Toy pushed to branch issue-276-xoroshiro128starstar at cmucl / cmucl

Commits: 52a08e62 by Raymond Toy at 2024-02-13T18:52:07-08:00 Add some comments

For x86, we've switched to xoroshiro128**. But sparc still uses xoroshiro128+ which, of course, has different results.

- - - - - 1b1c57ad by Raymond Toy at 2024-02-13T18:57:20-08:00 Add test program for generating reference results

This test program generates reference outputs for the xoroshiro128** generator to be used in the rng unit test.

- - - - -

2 changed files:

- tests/rng.lisp - + tests/rng/test-128-star-star.c

Changes:

===================================== tests/rng.lisp ===================================== @@ -48,28 +48,31 @@ (assert-equal 0 (kernel::random-state-rand *test-state*)) (assert-equal nil (kernel::random-state-cached-p *test-state*))

- (dolist (item #-x86 - '((#x18d5f05c086e0086 (#x228f4926843b364d #x74dfe78e715c81be)) - (#x976f30b4f597b80b (#x5b6bd4558bd96a68 #x567b7f35650aea8f)) - (#xb1e7538af0e454f7 (#x13e5253e242fac52 #xed380e70d10ab60e)) - (#x011d33aef53a6260 (#x9d0764952ca00d8a #x5251a5cfedd2b4ef)) - (#xef590a651a72c279 (#xba4ef2b425bda963 #x172b965cf56c15ac)) - (#xd17a89111b29bf0f (#x458277a5e5f0a21b #xd1bccfad6564e8d)) - (#x529e44a0bc46f0a8 (#x2becb68d5a7194c7 #x3a6ec964899bb5f3)) - (#x665b7ff1e40d4aba (#xededfd481d0a19fe #x3ea213411827fe9d)) - (#x2c9010893532189b (#xd7bb59bcd8fba26f #x52de763d34fee090)) - (#x2a99cffa0dfa82ff (#xf96e892c62d6ff2e #xc0542ff85652f81e))) - #+x86 - '((#x41db14eb317141fe (#x16dfbf3d760d0fa4 #xe9bfcf1ce2b9037c)) - (#xaa4ee6e025dfec01 (#xb237e99a3c7ad367 #x96819b1fec0e0432)) - (#xea080e50cb948fa5 (#xcc0fd8226093e0bc #x0e9aeaa496ce50ba)) - (#x647f057cff408a6e (#xd273573bfa97bfde #xcbb600d852a650de)) - (#x232ac586565d037e (#x75dc686d99e39c57 #x063de00338aafc75)) - (#xdf2da206813da6d6 (#x9616cabb961ebc4a #x292c044e7c310dd4)) - (#x00d17cb1b38c852f (#xca593a661127a754 #x45f633d7e759debd)) - (#xd7a1f881fc34e641 (#xe00fd868db5d20d3 #xcfcf3d31f5e1363e)) - (#x64853747af628d30 (#xa24296c5ebb11935 #xd782dda5f81cab25)) - (#xda40653710b7293d (#xfb4be9d4941ff086 #x75b6420eb8096c02)))) + (dolist (item + ;; Results for xoroshiro128+ + #-x86 + '((#x18d5f05c086e0086 (#x228f4926843b364d #x74dfe78e715c81be)) + (#x976f30b4f597b80b (#x5b6bd4558bd96a68 #x567b7f35650aea8f)) + (#xb1e7538af0e454f7 (#x13e5253e242fac52 #xed380e70d10ab60e)) + (#x011d33aef53a6260 (#x9d0764952ca00d8a #x5251a5cfedd2b4ef)) + (#xef590a651a72c279 (#xba4ef2b425bda963 #x172b965cf56c15ac)) + (#xd17a89111b29bf0f (#x458277a5e5f0a21b #xd1bccfad6564e8d)) + (#x529e44a0bc46f0a8 (#x2becb68d5a7194c7 #x3a6ec964899bb5f3)) + (#x665b7ff1e40d4aba (#xededfd481d0a19fe #x3ea213411827fe9d)) + (#x2c9010893532189b (#xd7bb59bcd8fba26f #x52de763d34fee090)) + (#x2a99cffa0dfa82ff (#xf96e892c62d6ff2e #xc0542ff85652f81e))) + ;; Results for xoroshiro128** + #+x86 + '((#x41db14eb317141fe (#x16dfbf3d760d0fa4 #xe9bfcf1ce2b9037c)) + (#xaa4ee6e025dfec01 (#xb237e99a3c7ad367 #x96819b1fec0e0432)) + (#xea080e50cb948fa5 (#xcc0fd8226093e0bc #x0e9aeaa496ce50ba)) + (#x647f057cff408a6e (#xd273573bfa97bfde #xcbb600d852a650de)) + (#x232ac586565d037e (#x75dc686d99e39c57 #x063de00338aafc75)) + (#xdf2da206813da6d6 (#x9616cabb961ebc4a #x292c044e7c310dd4)) + (#x00d17cb1b38c852f (#xca593a661127a754 #x45f633d7e759debd)) + (#xd7a1f881fc34e641 (#xe00fd868db5d20d3 #xcfcf3d31f5e1363e)) + (#x64853747af628d30 (#xa24296c5ebb11935 #xd782dda5f81cab25)) + (#xda40653710b7293d (#xfb4be9d4941ff086 #x75b6420eb8096c02)))) (destructuring-bind (value state) item (assert-equal value (64-bit-value *test-state*)) @@ -82,10 +85,12 @@ :rand 0 :cached-p nil)) (dolist (result + ;; Results for xoroshiro128+ jump function #-x86 '((#x291ddf8e6f6a7b67 #x1f9018a12f9e031f) (#x88a7aa12158558d0 #xe264d785ab1472d9) (#x207e16f73c51e7ba #x999c8a0a9a8d87c0) (#x28f8959d3bcf5ff1 #x38091e563ab6eb98)) + ;; Results for xoroshiro128** jump function #+x86 '((#x19a22191480b0a4e #x43b3d7ee592dd4cf) (#x76cb87035d0b6e99 #xb6827bcf2ef8267c) (#x5125201dbdf76860 #x8984c075043869e2)

===================================== tests/rng/test-128-star-star.c ===================================== @@ -0,0 +1,143 @@ +/* Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org) + +To the extent possible under law, the author has dedicated all copyright +and related and neighboring rights to this software to the public domain +worldwide. This software is distributed without any warranty. + +See http://creativecommons.org/publicdomain/zero/1.0/. */ + +#include <stdint.h> + +/* This is xoroshiro128** 1.0, one of our all-purpose, rock-solid, + small-state generators. It is extremely (sub-ns) fast and it passes all + tests we are aware of, but its state space is large enough only for + mild parallelism. + + For generating just floating-point numbers, xoroshiro128+ is even + faster (but it has a very mild bias, see notes in the comments). + + The state must be seeded so that it is not everywhere zero. If you have + a 64-bit seed, we suggest to seed a splitmix64 generator and use its + output to fill s. */ + + +static inline uint64_t rotl(const uint64_t x, int k) { + return (x << k) | (x >> (64 - k)); +} + + +static uint64_t s[2]; + +uint64_t next(void) { + const uint64_t s0 = s[0]; + uint64_t s1 = s[1]; + const uint64_t result = rotl(s0 * 5, 7) * 9; + + s1 ^= s0; + s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b + s[1] = rotl(s1, 37); // c + + return result; +} + + +/* This is the jump function for the generator. It is equivalent + to 2^64 calls to next(); it can be used to generate 2^64 + non-overlapping subsequences for parallel computations. */ + +void jump(void) { + static const uint64_t JUMP[] = { 0xdf900294d8f554a5, 0x170865df4b3201fc }; + + uint64_t s0 = 0; + uint64_t s1 = 0; + for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++) + for(int b = 0; b < 64; b++) { + if (JUMP[i] & UINT64_C(1) << b) { + s0 ^= s[0]; + s1 ^= s[1]; + } + next(); + } + + s[0] = s0; + s[1] = s1; +} + + +/* This is the long-jump function for the generator. It is equivalent to + 2^96 calls to next(); it can be used to generate 2^32 starting points, + from each of which jump() will generate 2^32 non-overlapping + subsequences for parallel distributed computations. */ + +void long_jump(void) { + static const uint64_t LONG_JUMP[] = { 0xd2a98b26625eee7b, 0xdddf9b1090aa7ac1 }; + + uint64_t s0 = 0; + uint64_t s1 = 0; + for(int i = 0; i < sizeof LONG_JUMP / sizeof *LONG_JUMP; i++) + for(int b = 0; b < 64; b++) { + if (LONG_JUMP[i] & UINT64_C(1) << b) { + s0 ^= s[0]; + s1 ^= s[1]; + } + next(); + } + + s[0] = s0; + s[1] = s1; +} + +/*********************************************************************/ + +#include <stdio.h> + +/* + * Print out the first 10 random numbers from the generator. This is + * used for the expected results in the rng unit test. + */ +void +test_rng() +{ + int k; + uint64_t r; + + + s[0] = 0x38f1dc39d1906b6full; + s[1] = 0xdfe4142236dd9517ull; + + printf(";; First 10 outputs\n"); + + for (k = 0; k < 10; ++k) { + r = next(); + printf("%2d: #x%016llx (#x%016llx #x%016llx)\n", k, r, s[0], s[1]); + } +} + +/* + * Print out the first 4 states from jumping generator by 2^64 steps. + * This is used for the expected results in the rng unit test. + */ +void +test_jump() +{ + int k; + + s[0] = 0x38f1dc39d1906b6full; + s[1] = 0xdfe4142236dd9517ull; + + printf(";; First 4 jumps\n"); + for (k = 0; k < 4; ++k) { + jump(); + printf("%2d: #x%016llx #x%016llx\n", k, s[0], s[1]); + } +} + + +int +main() +{ + test_rng(); + test_jump(); + + return 0; +}

View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/3914424237eb1ad708c7da5...