Skip to content

Instantly share code, notes, and snippets.

@skeeto
Created May 31, 2018 00:46
Show Gist options
  • Save skeeto/aacc4dc03cc1863a0790abc693581ebe to your computer and use it in GitHub Desktop.
Save skeeto/aacc4dc03cc1863a0790abc693581ebe to your computer and use it in GitHub Desktop.
Estimate pi by shooting arrows at a shield
/* 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