Created
February 23, 2021 21:51
-
-
Save alwynallan/a15ce329e8e0efcacf1eeffe4e9431e7 to your computer and use it in GitHub Desktop.
Tests the 64-bit hardware efficient generation of random 1-in-3 choices.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <stdint.h> | |
| #include <assert.h> | |
| // alwynallan@gmail.com February 2021 | |
| // tests the 64-bit hardware efficient generation of 1-in-3 choices. | |
| // uses the fact that 2^65 is just ~1% larger than 3^41 | |
| // whereas 2^2 is 25% larger than 3^1 | |
| // compile: gcc -Wall thirds.c -o thirds | |
| uint64_t random64() { | |
| static FILE * fr = NULL; | |
| uint64_t res; | |
| if(fr == NULL) { | |
| fr = fopen("/dev/urandom","r"); | |
| assert(fr != NULL); | |
| } | |
| fread(&res, sizeof(uint64_t), 1, fr); | |
| return res; | |
| } | |
| int thirds() { | |
| static uint64_t thirds_res; | |
| static int thirds_res_level = 0; // how many times thirds_res can be div/mod cycled 0-40 | |
| static uint64_t bits; | |
| static int bits_level = 0; // how many unused bits 0-64 | |
| if(thirds_res_level) { | |
| int res = thirds_res % 3; | |
| thirds_res /= 3; | |
| thirds_res_level--; | |
| return res; | |
| } | |
| while(1) { | |
| uint64_t n64 = random64(); | |
| if(!bits_level) { | |
| bits = random64(); | |
| bits_level = 64; | |
| } | |
| int bit = bits & 1; | |
| bits = bits >> 1; | |
| bits_level--; | |
| if(bit) { | |
| if(n64 <= 18026252303461234787u){ // big number is 3^41 - 2^64 | |
| thirds_res = 6148914691236517205u + n64 / 3; // big number is 2^64 / 3 | |
| int res = n64 % 3 + 1; // 1 here is 2^64 % 3 | |
| if(res == 3) { | |
| thirds_res++; | |
| res = 0; | |
| } | |
| thirds_res_level = 40; | |
| return res; | |
| } // else go for another loop | |
| } | |
| else { | |
| thirds_res = n64 / 3; | |
| thirds_res_level = 40; | |
| return n64 % 3; | |
| } | |
| } // no guarantee it will return, but 99% chance each loop | |
| } | |
| int main() { | |
| unsigned bins[3] = {0, 0, 0}; | |
| for(int i = 0; i < 1000; i++) printf("%d ", thirds()); | |
| for(unsigned i = 0; i < 3000000000; i++) bins[thirds()]++; | |
| printf("\n%u, %u, %u\n", bins[0], bins[1], bins[2]); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment