-
-
Save skeeto/aacc4dc03cc1863a0790abc693581ebe to your computer and use it in GitHub Desktop.
Estimate pi by shooting arrows at a shield
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
/* Estimate pi by shooting arrows at a shield. | |
* https://www.smbc-comics.com/comic/math-and-war | |
* Only uses integer operations except for displaying the quotient. | |
*/ | |
#include <time.h> | |
#include <stdio.h> | |
#include <inttypes.h> | |
#define HALF UINT64_C(0x80000000) | |
#define QUARTER UINT64_C(0x40000000) | |
static uint64_t | |
xoroshiro128plus(uint64_t s[2]) | |
{ | |
uint64_t s0 = s[0]; | |
uint64_t s1 = s[1]; | |
uint64_t result = s0 + s1; | |
s1 ^= s0; | |
s[0] = ((s0 << 24) | (s0 >> 40)) ^ s1 ^ (s1 << 16); | |
s[1] = (s1 << 37) | (s1 >> 27); | |
return result; | |
} | |
int | |
main(void) | |
{ | |
uint64_t s[] = {0x8ecdf50ac9ce517d, 0xa687a3079cb1d1d2}; | |
uint64_t inside = 0; | |
s[0] ^= time(0); | |
for (uint64_t i = 1; i < UINT64_MAX; i++) { | |
uint64_t r = xoroshiro128plus(s); | |
uint64_t x = r & UINT64_C(0xffffffff); | |
uint64_t y = r >> 32; | |
if (x < HALF && y < HALF) { | |
uint64_t dx = x < QUARTER ? QUARTER - x : x - QUARTER; | |
uint64_t dy = y < QUARTER ? QUARTER - y : y - QUARTER; | |
if (dx * dx + dy * dy < UINT64_C(0x1000000000000000)) | |
inside++; | |
} | |
if (!(i & UINT64_C(0x3ffffff))) { | |
printf("%.17g %" PRIu64 " %" PRIu64 "\n", | |
16.0 * inside / i, 16 * inside, i); | |
fflush(stdout); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment