Skip to content

Instantly share code, notes, and snippets.

@flyingmutant
Last active July 24, 2021 15:43
Show Gist options
  • Save flyingmutant/cb69e96872023f9f580868e746d1128a to your computer and use it in GitHub Desktop.
Save flyingmutant/cb69e96872023f9f580868e746d1128a to your computer and use it in GitHub Desktop.
> time ./birthday.wyrandskip65536.sort 10
Testing skipping_rng<WyRand,65536>
0..281474976710655 is range of generator
75029991 outputs to scan for duplicates [4.47214*sqrt(range)]
10 duplicates expected on average
4.54e-05 is probability of zero duplicates
0x54a2be72 is seed for this run
---
- Testing for repeats started...
- Allocating memory started...
- allocated array of size 75029991.
- Allocating memory completed (3.0818e-05 seconds)
- Storing PRNG output started...
- Storing PRNG output completed (4154.58 seconds)
- Sorting started...
- Sorting completed (6.95675 seconds)
- Scanning for duplicates started...
- repeat of 9339559682391 found
- repeat of 22152142043371 found
- repeat of 33755183249585 found
- repeat of 42374506467846 found
- repeat of 97901010117324 found
- repeat of 115244553244097 found
- repeat of 116278300755486 found
- repeat of 148431320016741 found
- repeat of 156548117953649 found
- repeat of 171103438244796 found
- repeat of 175323503640754 found
- repeat of 181147974224283 found
- repeat of 207556848907292 found
- repeat of 226021369390278 found
- repeat of 228388994289050 found
- repeat of 229632200399167 found
- repeat of 236393619723146 found
- Scanning for duplicates completed (0.0599048 seconds)
- Testing for repeats completed (4161.6 seconds)
---
17 repeats, p-value = 1 - 0.0142776
________________________________________________________
Executed in 69,36 mins fish external
usr time 69,16 mins 0,00 micros 69,16 mins
sys time 0,03 mins 1174,00 micros 0,03 mins
> time ./birthday.wyrandskip65536.sort 10
Testing skipping_rng<WyRand,65536>
0..281474976710655 is range of generator
75029991 outputs to scan for duplicates [4.47214*sqrt(range)]
10 duplicates expected on average
4.54e-05 is probability of zero duplicates
0x19cc8bbe is seed for this run
---
- Testing for repeats started...
- Allocating memory started...
- allocated array of size 75029991.
- Allocating memory completed (2.8946e-05 seconds)
- Storing PRNG output started...
- Storing PRNG output completed (3175.85 seconds)
- Sorting started...
- Sorting completed (6.0666 seconds)
- Scanning for duplicates started...
- repeat of 913288115833 found
- repeat of 30250333060819 found
- repeat of 35701161406351 found
- repeat of 50846633716114 found
- repeat of 56616672386980 found
- repeat of 59148699398272 found
- repeat of 60622960984701 found
- repeat of 68284155789849 found
- repeat of 70246722271544 found
- repeat of 72981549978784 found
- repeat of 102078990207300 found
- repeat of 105598177376481 found
- repeat of 113152712466326 found
- repeat of 143794467881666 found
- repeat of 144208580907049 found
- repeat of 171282305285318 found
- repeat of 183771090075984 found
- repeat of 205549215513879 found
- repeat of 222778896925587 found
- repeat of 242846648763651 found
- repeat of 259994985930374 found
- Scanning for duplicates completed (0.0536843 seconds)
- Testing for repeats completed (3181.97 seconds)
---
21 repeats, p-value = 1 - 0.00069965
________________________________________________________
Executed in 53,03 mins fish external
usr time 53,01 mins 1066,00 micros 53,01 mins
sys time 0,01 mins 0,00 micros 0,01 mins
#ifndef WYRAND_HPP_INCLUDED
#define WYRAND_HPP_INCLUDED 1
struct WyRand {
using result_type = uint64_t;
static constexpr uint64_t min() { return 0; };
static constexpr uint64_t max() { return ~uint64_t(0); };
WyRand(uint64_t seed): seed_(seed) {}
uint64_t operator()() {
seed_ += 0xa0761d6478bd642full;
__uint128_t m = __uint128_t(seed_) * __uint128_t(seed_ ^ 0xe7037ed1a0b428dbull);
return uint64_t(m) ^ uint64_t(m >> 64);
}
private:
uint64_t seed_;
};
#endif // WYRAND_HPP_INCLUDED
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment