The Random Walker and the PI Searcher

random walk

Why?

A while ago I started researching[1] microcontrollers, using mainly Arduinos and the STM32 Nucleo boards.

So, naturally, I have a bunch of Arduino Pro Minis lying around. Originally, they were meant for a measuring device that records temperature, humidity, possibly CO2 and dust. But it never happened. The moment I connected the SH1006 OLED display and the DHT22 temperature sensor, the Arduino stopped working. Why this is so, I still have to find out. Enough to say that I spent days researching the internet and debugging, to no avail.

No problem to get that setup running with an ESP32 (and I would go with that board for the project anyway), but no luck with the Arduino Pro Mini. So, what to do with the Arduinos? I decided to make some math fun devices. Why not turn fail into fun?

Hardware

Because I wanted a little gadget that I could hang on the wall, I put it all on a board and did some soldering. The Arduino and the OLED are soldered to a strip board. Connections are done on the back of the board.

I also added a battery compartment that contains three 1.2 Volt AA batteries. Together, they provide 3.6 Volt, which is just fine for an Arduino Pro Mini, which needs at least 3.3 Volts.

There are not that many connections to be done. The OLEDs SDA is connected to A4 on the Arduino. It’s the yellow wire you can see in the images. The green wire connects the SCK of the OLED to the Arduinos A5.

The red wire connects VCC from the OLED, RAW on the Arduino and the plus pole of the battery compartment. Finally, the black wire connects GND of OLED and Arduino with GND of the batteries. That’s it.

The casing is made from the bottom of Mon Cheri box. Later, I bent the connectors up a bit, so the Arduino can be easily connected for reprogramming.[2]

Another idea that I had was to make a plushie that contains the hardware. Something like a Teletubby that has the OLED in its belly. The plushie could be either sewn or crocheted. Right now, I just put everything in a box.

So, using the Arduino Pro Mini and a SH1106 OLED display, I wrote some sketches. One for a random walk and another one that computes PI.

Random walk

random walk display

A random walk is a mathematical model of random movements.[3] One application is to model the movements of small particles or bacteria, for example. The concept is simple. You start somewhere, typically at zero. In every iteration, you throw a dice, with the outcomes 1 or -1. This value is added to the current value, which gives you a graph that slowly wanders up and down the y-scale.

Random walks have some really strange and interesting properties. One of them is that a random walk visits every integral number at least once, if you let it run forever. For example, will my random walk reach 1000000000000000000000000000123? Yes, one day it will. You just may have to wait a bit.

When you think about it, it’s just logical. If we can roam forever, we will go everywhere. Yet, it’s still an astonishing fact that bends my brain quite a bit. But then again, I’m a mathematician, so I like getting my brain bent.

The device displays the current value of the random walk and some statistics: The minimum and maximum, the average and the mid, which is half the distance between minimum and maximum. The mid is computed in absolute values, which means that the distance between mid and min is the same as the distance between mid and max. So, for example, the mid of -5 and 17 is

-5 + (17 - -5)/2 = -5 + 11 = 6

When the freshly computed values have been displayed, the device sleeps for a second. We want to watch progress and savor it, and not just see values run by frantically.

Computing the average

When you want to compute the average, there is a gotcha. The common way to compute an average is to sum up all values and divide by the number of values. But here, we don’t store all those values, for two reasons. The memory of the poor Arduino would overflow with all the numbers. Also, summing up all the values would result in a big value, to big to represent as an integer in Arduino code. So, all we have is the last and the current value.

Luckily, there is a way to compute a running average from a few values.[4] All that we need is the average so far and the new value of the random walk.

The new average is defined as

(a1 + …​ + an+1) / n+1

Lets transform this a bit to get

(a1 + …​ + an) / n+1 + an+1 / n+1

Multiplying the left term of the sum by n/n = 1 is ok and gives us

(((a1 + …​ + an) n) / n) / n+1 + an+1 / n+1

Transform again to get

(a1 + …​ + an) / n + n / n+1 + an+1 / n+1

The left term is just our old average and so we finally get

new average = old_average + n / n+1 + an+1 / n+1

One nice aspect of this formula is that n / n+1 is getting closer to 1 as n increases, so we don’t have big values in our computation.

Note: The formulas are a bit hard to read. I would have liked to display the formulas using stem, but with my current blogging process (convert Asciidoc to HTML and make a static website with Pelican), this does not work. Sorry for the inconvenience.

Code

So, here’s the code of the sketch. We have a .ino file as the main file. We do the usual things here: Set up the display, compute and display the values, sleep a little.

#include <Adafruit_GFX.h>
#include <Adafruit_SH1106.h>
#include <LowPower.h>
#include "RandomWalker.h"

/*
 * Simple random walker, displaying current value, as well as min and max so far.
 */

Adafruit_SH1106 display(-1);
RandomWalker walker;

void setup()
{
  // Initialize display.
  display.begin(SH1106_SWITCHCAPVCC, 0x3C);
  display.setTextColor(WHITE);

  /*
   * We want different random values for every run, else it gets boring. If you
   * need repeatable values, comment out the function call below or change the
   * call to
   *
   * This assumes that PIN 0 is not connected, so it delivers random values
   * instead of possibly constant sensor input.
   *
   * randomSeed(0);
   */
  randomSeed(analogRead(0));
}

void loop()
{
  display.clearDisplay();
  display.setTextSize(1);
  display.setCursor(2, 2);
  display.print("Val: ");
  display.println(walker.next());
  display.print("Min: ");
  display.println(walker.minimum());
  display.print("Max: ");
  display.println(walker.maximum());
  display.print("Avg: ");
  display.println(walker.average());
  display.print("Mid: ");
  display.println(walker.midrange());
  display.print("Num: ");
  display.println(walker.count());
  display.display();

  LowPower.powerDown(SLEEP_1S, ADC_OFF, BOD_OFF);
}

The random walk is implemented in a class. Here’s the header (a file with the suffix .h):

#ifndef RandomWalker_h
#define RandomWalker_h

class RandomWalker
{
  public:

    /*
     * Do the next step in the random walk. Returns the new value and updates
     * the other metric (maximum and friends).
     */
    long int next();

    double average();
    long int count();
    long int minimum();
    long int maximum();
    long int midrange();

  private:
    long int value = 0;
    long int min = 0;
    long int max = 0;
    long int mid = 0;
    double avg = 0;
    long int _count = 0;
};

#endif

And here comes the implementation (a file with the suffix .cpp):

#include <Arduino.h>
#include "RandomWalker.h"

long int RandomWalker::next()
{
  long int randnum = random(2) * 2 - 1;

  this->value += randnum;

  this->min = (this->value < this->min) ? this->value : this->min;
  this->max = (this->value > this->max) ? this->value : this->max;

  /*
   * Note that we have to cast the nominator of the fractions to double, else we
   * would get a rounded int (aka floor).
   */
  this->avg = (this->avg * ((double) this->_count / (this->_count + 1))) + ((double) this->value / (this->_count + 1));

  this->_count++;

  return value;
}

double RandomWalker::average()
{
  return this->avg;
}

long int RandomWalker::count()
{
  return this->_count;
}

long int RandomWalker::maximum()
{
  return this->max;
}

long int RandomWalker::minimum()
{
  return this->min;
}

long int RandomWalker::midrange()
{
  /*
   * When there are negative values, computation of the midrange is a bit more
   * complex than just building the average.
   * This formula should do the trick.
   */
  return this->min + (abs(this->min) + abs(this->max)) / 2;
}

Here we update the value and the statistics with every call of the next() method.

In search of PI

Another sketch computes PI, using the Leibniz series.[5] It converges slowly, but that’s part of the fun: Watch the device creep slowly towards the value of PI.

search pi

First, there is quite some progress, but after a week or so, the display still changes between 3.1415…​ and 3.1416…​

And here’s the code:

#include <Adafruit_GFX.h>
#include <Adafruit_SH1106.h>
#include <LowPower.h>

// Set up math stuff.
int toggle = 1;
double x = 1;
double series = 0;

Adafruit_SH1106 display(-1);

void setup()
{
  Serial.begin(9600);

  // Initialize display.
  display.begin(SH1106_SWITCHCAPVCC, 0x3C);
  display.setTextColor(WHITE);
}

void loop()
{
  String s = "PI: " + String(calc_pi(), 12);

  display.clearDisplay();
  display.setTextSize(1);
  display.setCursor(2, 2);
  display.println(s.c_str());
  display.display();

  LowPower.powerDown(SLEEP_4S, ADC_OFF, BOD_OFF);
}

double calc_pi()
{
  double el = 1/x * toggle;

  //Serial.print("El: ");
  //Serial.println(el);

  series += el;
  toggle *= -1;
  x += 2;

  //Serial.print("X: ");
  //Serial.println(x);

  double pi = 4 * series;

  //Serial.print("PI: ");
  //Serial.println(pi, 4);

  return pi;
}

Stamina

Originally, like any Arduino noob, I used the delay() function in my sketches, with a delay of one second for the random walk and five seconds for the PI search. Then the device runs for a bit less than three days with three Ansmann 1.2 V, 2850 mAh batteries. Thats a bit short for practical[6] use. One solution would of course be a different power source. You could just use a USB power adaptor or a bigger battery.

But there is also a software solution. To make it run longer, you can use the Lowpower library (https://github.com/rocketscream/Low-Power) and replace the delay with a line like the following:

LowPower.powerDown(SLEEP_1S, ADC_OFF, BOD_OFF);

This increased the run time to about nine days.[7] Note that this slows down the whole thing, after a day, you have somewhere over 50000 one-second cycles for the random walk, not 84600, as you would expect.[8] But those are fun gadgets and not mission critical, so that’s ok.

Lessons learned

As you can see, the OLED is a bit tilted. Next time, I would fixate the OLED with screws instead of only soldering it in.


1. Ok, I play around with those devices. But that does not sound halfways as professional as "researching".
2. The Pro Mini is stripped down quite a bit, so, to program it, you need an extra USB to TTL converter, for example the FTDI FT232.
3. Citation needed? Here it is: https://en.wikipedia.org/wiki/Random_walk.
4. I discovered this by myself and it took me the better part of an afternoon. But I’m sure that trick is already known to the mathematical world.
6. If you consider watching random walks or PI computations "practical", that is.
7. Also with three 2850 mAH batteries.
8. If I counted correctly, this effect does not appear when delay() is used. Then a day is approximately 84600 seconds.

links

social