Tuesday, 3 December 2013

Evolution of Pseudo Randomness

                "Anyone who attempts to generate random numbers by 
                                    deterministic means is, of course, living in a state of sin."  
                                                                                                        John Von Neumann

The GIF below shows the evolving outputs of Pseudo Random Number Generators (PRNGs) produced by the Genetic Program I implemented in C.

See the Wiki pages on Genetic Algorithms & ProgrammingEntropy and Koza's paper [1] for supporting information to this post.

Each PRNG in the population outputs 16384 "random" bits / 2048 bytes. Fitness (or "randomness") of a PRNG is measured using the Shannon Entropy equation for binary sub sequences of size $h$ from $1 \to N_{max} = 8$, across the 2Kb output. For each sub sequence of size $h$; 

$E_{h} = - \sum_{j} P_{(hj)}\ \log_2\ P_{(hj)}$

therefore the total entropy of a PRNG output for binary sub sequences of size $h$ from $1 \to N_{max} = 8$;

$E_{total} = \sum_{h = 1}^{N_{max}} \left[ - \sum_{j} P_{(hj)}\ \log_2\ P_{(hj)} \right]$

Therefore in order to achieve maximum entropy for $E_h$, all probabilities for all $2^h$ binary sub sequences of length $h$ must be equal to $\frac{1}{2^h}$.

The maximum achievable entropy for sub seqences of sizes $1 \to 8$ can be calculated as;

$E_{max} = \sum_{i = 1}^{8} i = \frac{8 \cdot (8 + 1)}{2} = 36$

For this run the population is evolved over 39 Generations. The entropy is evolved rapidly to begin with and then fluctuates around 97~99%* until on the 39th generation it reaches the terminating entropy of 99.93% (or 35.97386 bits of entropy out of a maximum 36 bits). Each frame in the GIF shows the output of the fittest PRNG in the population at that generation.

May the lord have mercy on my soul!

* The implementation isn't driven by hill climbing.

[1] John R. Koza, Evolving a Computer Program to Generate Random Numbers Using the Genetic Programming Paradigm. Stanford University, 1991.

Tuesday, 3 September 2013

I'm Home v1.0.1 Android Application

I'm Home is a new Android Application from West Coast Labs which automatically starts up your computer when you arrive at home or work, and runs quietly and efficiently in the background of your Android device.

If you are someone who likes their PC to be on constantly so that you don't have to spend time waiting for you PC to turn on. Then this app is a smart alternative which will help you save on energy bills and do a little extra for the environment!

Alternately if you are someone who shuts their computer down when you leave your home/work and turn it back on when you return, then this app will help reduce the time in your day spent staring at loading screens, and you don't even need to take your phone out!

It works by using the Wake On Lan service built into almost all motherboards, and by sending magic packets to your computer when your android phone joins your WiFi network. Wake On Lan is only provided by ethernet adaptors so your PC will have to be connected to the router via ethernet. (This app will work on WiFi only to wake the PCs in sleep mode (i.e. when the WiFi card is still on)).

How To

Step 1) Simply configure your Windows PC/Mac/Linux machine using the tutorial in this link. The most important part is to ensure that Wake On Lan is enabled in your BIOS (usually that's all that's needed).
Step 2) Download the application on the Play Store here or using the QR code above.
Step 3) Configure the application as follows;

PC IP or Broadcast IP: This is the broadcast IP of your router or the specific IP of the PC. Note that putting the broadcast IP of the router is more reliable than the specific IP address especially if IP addresses are allocated dynamically on your router. As it says in the app, typically your Broadcast IP will be one of the following;, or

MAC: The MAC address of your computer. To find out, in Windows type "ipconfig /all" into a command prompt and look for "physical address" under your Ethernet Adaptor.

In Mac or Linux type "ifconfig" and look for "HWaddr" under your eth device.

Port: This is important for when the PC is in sleep mode instead of being completely turned off. (Must be filled out anyway, it will either be 9/7)

SSID: This is the name of the router to which your phone and computer are connected or connect to. You can use the button to auto fill this box with your current WiFi network's SSID.

The time slider is used to stop the application from sending packets for a certain amount of time after the last disconnect. This is useful if you briefly come back but don't want your computer started. Also I noticed that Android phones have a habit of quickly disconnecting and reconnecting from WiFi even when they are in range, in the middle of the night! So this feature also prevents your computer being started when your asleep.

The first checkbox stops your PC from waking up when you start your phone and connect to WiFi straight away. The second checkbox explains itself.

The disable from checkbox allows you to setup a time frame in which the app will be disabled and your PC will not be woken.

All the forms must be filled out when saving and the IP and MAC must be in the correct syntax.

The send test button sends magic packets using the configuration on the screen (so it doesn't need to be saved).

Cancel closes the configuration. The PC wakeup part of the app is started when the device connects to the SSID in the configuration.

Note: On some machines Wake On Lan only works after a clean shutdown. If you turn the power off and on at the switch or at the PSU then the ethernet adapter might not be turned back on again until you start the computer manually.

Edit 13/09/2013 - Version 1.0.1