flak rss random

on the efficacy of cosmic ray sorting

Cosmic rays are believed by some to exist, although I’ve never seen one. Have you? Are the cosmic rays in the room with us now? It has been further claimed that these cosmic rays may interact with our computers, possibly causing strange behaviors. This sounds like pseudo scientific babble from people who don’t believe in the ghost in the machine.

It’s been proposed that cosmic rays could even sort data. Take an array of unsorted data, wait for cosmic rays to strike it, and eventually it will become sorted. Will this work? Let’s conduct an experiment. Or rather, a simulation, since that seems better suited for probing the nature of the unreal.

The setup for our simulation will be a very simple unsorted array, consisting of two bytes, [2 1], and we will wait for it to become a sorted array. Note that there are quite a few sorted arrays consisting of two bytes other than the correct answer of [1 2]. For example, if a cosmic rays transmutes our initial array into [2 65], it will be sorted, but it will not be a sort of the input array.

The test harness is not very much code. We keep running the experiment, focusing a very concentrated narrow beam of cosmic rays into our two byte memory, until the array sorts and matches the correct result. I was a little worried this would run forever, but it’s actually very fast.

#include <stdio.h>
#include <stdlib.h>

uint64_t rays = 0;
static uint16_t cosmicray(void) { rays++; return 1 << (arc4random() & 0xf); }

static int
onetest(void)
{
        union {
                uint8_t bytes[2];
                uint16_t word;
        } ram = {{ 2, 1}};

        while (!(ram.bytes[0] < ram.bytes[1])) {
                ram.word ^= cosmicray();
        }
        return ram.bytes[0] == 1 && ram.bytes[1] == 2;
}

int
main(int argc, char **argv)
{
        uint64_t tries = 0;
        while (!onetest())
                tries++;
        printf("correct sort after %ju tries and %ju rays\n", tries, rays);
}

Results are achieved after a moderate number of tests. Varies, of course, but usually somewhere in the thousands. A little mental conditional probability checks out. Initially, nearly half of the possible ray targets will increment the second number to be greater than 2, and it will sort, but incorrectly. If we pass that test, there’s still many ways to screw up. The ideal sequence would be something like increment first byte, hit the two data bits, then clear the first byte again. In any case, the error rate is very high, and I would not recommend using this as a sort function, even if you have access to a ready supply of these so called cosmic rays.

Posted 28 Apr 2022 18:13 by tedu Updated: 28 Apr 2022 18:13
Tagged: c programming