flak rss random www

sorted arrays, theory and practice

The average time to check if a random array is sorted is e - 1. This was not the result I was expecting, but it’s also easy to check.

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

typedef unsigned int unt;

const unt length = 100;

unt
sortlen(unt *arr)
{       
        unt i;

        for (i = 0; i < length - 1; i++)
                if (arr[i] > arr[i + 1])
                        break;
        return i + 1;
}       

void
shuffle(unt *arr)
{       
        unt i;
        
        for (i = 0; i < length - 1; i++) {
                unt j = i + arc4random_uniform(length - i);
                unt t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
        }       
}       

int
main(int argc, char **argv)
{       
        const unt trials = 1000000;
        unt arr[length];
        unt i;
        unt count = 0;
        
        for (i = 0; i < length; i++)
                arr[i] = i;
        
        for (i = 0; i < trials; i++) {
                shuffle(arr);
                count += sortlen(arr);
        }       
        printf("avg sort len %f\n", (double)count / trials);
}       

And the results:

carbolite:/tmp> ./sort                 
avg sort len 1.718539
carbolite:/tmp> ./sort 
avg sort len 1.717483
carbolite:/tmp> ./sort 
avg sort len 1.718032

I’m not sure if it’s reasonable to expect the inputs to such a function to be uniformly random arrays. Any program which checks if an array is sorted probably deals with sorted arrays more frequently. But at least the math checks out.

Posted 30 Oct 2016 23:34 by tedu Updated: 30 Oct 2016 23:34
Tagged: math programming

incomprehensible + illegible = illiterate

Any Wikipedia article that has been mathematized is practically guaranteed to be incomprehensible. And it’s definitely guaranteed to be illegible. The article for locality sensitive hashing doesn’t disappoint.

wiki math

Why is math illiteracy rampant? Because nobody should be forced to read text like this unless they’re guilty of some heinous crime.

Posted 30 May 2014 20:40 by tedu Updated: 30 May 2014 20:40
Tagged: math rants web

super bowl squares

Get excited, the Super Bowl is coming, which means Super Bowl Squares are coming! It’s time to start thinking about the value of each cell in the square. You can let players pick cells, but it’s more fun to randomly assign them. That still allows trading cell for the skill player, but doesn’t leave a hobbled 2-2 cell lying around for some sucker to pick. Either way, it’s good to know the expected value of each cell.

more...

Posted 17 Jan 2014 04:43 by tedu Updated: 10 Oct 2014 00:34
Tagged: math programming sports

gluten free math puzzle

Quoting from Celiac Power, “They tested the blood for gluten antibodies, expecting to see the current 1 percent rate of disease. Instead, only 0.002 percent of the airmen tested positive. Further tests showed today’s young men were 41/2 times more likely to have the illness.”

Puzzle: Arrange the numbers 0.01, 0.00002, and 20.5 in a sensible equation.

Posted 23 Jun 2013 19:29 by tedu Updated: 23 Jun 2013 19:29
Tagged: food magreview math rants