x86 machine code, 21 bytes
The rdtsc version is the same size for x86-64 machine code.
rdrand reg (3 bytes) gives us a truly random number. Branching on its sign bit is cheap. By testing only 1 bit, the 50/50 probability is obviously satisfied exactly with zero bias.
rdtsc (2 bytes) gives us a "reference cycle" timestamp whose low bits are somewhat random (it takes at least 25 cycles to run back-to-back RDTSC instructions, but the counter isn't running that much faster than we're sampling it). Testing one bit with test al, 1 leads to significant correlation between consecutive decisions, but test al,al / jnp (branch on the parity flag, horizontal xor of the low 8 bits) gives surprisingly good results, and could be used on pre-IvyBridge machines that lack rdrand. Both of them golf to the same overall size in 32-bit mode.
Try it online!
NASM listing for rdrand version: EAX rfib(ECX), callable from C with MS __fastcall
21 rfib: ;;; 0-indexed. ecx=5 gives the n=6 test case results.
22 00000020 31C0 xor eax, eax
23 00000022 99 cdq ; EDX = fib[-1] = 0
24 00000023 40 inc eax ; fib[0] = 1
25 00000024 E30E jecxz .done ; ecx=0 : return 1 without looping
27 .loop:
28 00000026 0FC7F7 rdrand edi
29 00000029 85FF test edi, edi ; 1 byte shorter than sar reg, imm / xor / sub 2's complement bithack
30 0000002B 7902 jns .no_negate ; the top bit is fully random
31 0000002D F7DA neg edx
32 .no_negate:
33 0000002F 0FC1D0 xadd eax, edx ; like xchg + add, and same size
34 00000032 E2F2 loop .loop
35 .done:
36 00000034 C3 ret
size = 0x35 - 0x20 = 0x15 = 21 bytes
Note that xadd doesn't actually save any bytes vs. xchg eax, edx / add eax, edx. It's just fun. And it's "only" 3 uops, instead of 4 total, on Intel Skylake with register operands. (Normally the instruction is only used with the lock prefix and a memory destination, but it fully works with registers).
Test case:
bash loop to test the ECX=5 case
$ asm-link -m32 -dn random-fib.asm &&
{ declare -A counts; counts=();
for i in {1..10000}; do ./random-fib; ((counts[$?]++));done;
for i in "${!counts[@]}"; do echo "result: $(( i > 128 ? i-256 : i )):
${counts[$i]} times";done }
result: 8: 617 times
result: 4: 1290 times
result: 2: 2464 times
result: 0: 3095 times
result: -2: 2534 times
NASM listing for rdtsc version: EBX rfib2(ECX). This version would be the same size in 64-bit mode; doesn't need 1-byte inc. RDTSC writes EAX and EDX so we can't take advantage of cdq in the init.
2 rfib2: ; 0-index count in ECX, returns in EBX
3 00000000 31F6 xor esi, esi
4 00000002 8D5E01 lea ebx, [esi+1] ; fib[0] = 1, fib[-1] = 0
5 00000005 E30D jecxz .done
6 .loop:
7 00000007 0F31 rdtsc ; EDX:EAX = TimeStamp Counter
8
9 00000009 84C0 test al, al ; low bits are essentially random; high bits not so much
10 0000000B 7B02 jnp .no_negate
11 0000000D F7DE neg esi
12 .no_negate:
13 0000000F 0FC1F3 xadd ebx, esi
14 00000012 E2F3 loop .loop
15 .done:
16 ; returns in EBX
17 00000014 C3 ret
size = 0x15 = 21 bytes
Test results for ECX=5:
result: 8: 668 times (ideal: 625)
result: 4: 1217 times (ideal: 1250)
result: 2: 2514 times (ideal: 2500)
result: 0: 3135 times (ideal: 3125)
result: -2: 2466 times (ideal: 2500)
vs. with test al, 1 / jnz to use just the low bit of the TSC as the random value:
# test al,1 / jnz version: correlation between successive results.
result: 8: 115 times
result: 4: 79 times
result: 2: 831 times
result: 0: 3070 times
result: -2: 5905 times
test al,4 happens to work reasonably well for long runs on my Skylake CPU (i7-6700k) which ramps up to 3.9GHz at the energy_performance_preference=balance_performance I'm using, vs. a reference (TSC) frequency of 4008 MHz (more info on x86 constant-TSC stuff). I imagine there's some strange alchemy of branch prediction, and rdtsc itself having ~25 cycle throughput (core clocks) on Skylake (https://uops.info).
Results are generally better distributed with test al,al / jnp though, so prefer that to take entropy from all 8 low bits. When CPU frequency is low (idle), so the TSC is not close to the same frequency as the core, taking entropy from a single bit might work even better, although the parity of the low 8 bits is probably still best.
I haven't tested on a CPU with turbo disabled where non-boost core clock exactly equals the TSC reference clock. That could more easily lead to bad patterns if the rdtsc throughput happens to be a power of 2 or something, perhaps favouring some sequence that lets branch prediction lock on.
All my testing has been with one invocation of the function per process startup. A Linux static executable is pretty efficient to start up, but is still vastly more expensive than calling the function in a loop from inside the process.
