Pi digits on an LCD, on an Arduino Uno

// Pi Day digits: the Uno works out the digits of pi one at a time and runs
// them across a 16x2 LCD, the newest digit on the right.
//
//   LCD       16x2 with an I2C backpack: SDA -> A4, SCL -> A5
//
// No table of digits is stored anywhere. This is the spigot algorithm of
// Rabinowitz and Wagon (1995): pi is written as a number in a mixed base,
// 2 + 1/3 (2 + 2/5 (2 + 3/7 (2 + ...))), as an array of small remainders,
// all set to 2 to start. Multiply every entry by 10 and carry from the right,
// and one decimal digit drops out on the left. Do it again for the next one.
//
// Now and then a 9 is not final, because the next digit can carry 1 into it
// (pi has six 9s in a row at digit 762). So the sketch holds back the last
// digit and any 9s after it until a digit below 9 comes along, then lets them
// all go: that is the "predigit" step.
//
// The array needs 10 * DIGITS / 3 entries. For 100 digits that is 334 small
// numbers, about 670 bytes of the Uno's 2048. Every digit is a pass over the
// whole array, 334 divisions of 32-bit numbers, which an 8-bit chip does in
// software, so the digits arrive at a few a second: just right to watch.
//
// Things to try. Change DIGITS to 50 or 150 and watch how long it takes. The
// time grows with the square of the digits.

#include <Wire.h>
#include <LiquidCrystal_I2C.h>

const int DIGITS = 100;
const int LEN = DIGITS * 10 / 3 + 1;

LiquidCrystal_I2C lcd(0x27, 16, 2);
uint16_t a[LEN];
char line[17];   // the last 16 digits shown
int shown = 0;
unsigned long startedAt;

void emit(int d) {
  // Shift the line left and put the new digit on the right.
  for (int i = 0; i < 15; i++) line[i] = line[i + 1];
  line[15] = '0' + d;
  line[16] = 0;
  shown++;
  Serial.print(d);
  if (shown == 1) Serial.print('.');
  lcd.setCursor(0, 0);
  lcd.print(line);
  lcd.setCursor(0, 1);
  lcd.print("digit ");
  lcd.print(shown);
  lcd.print("   ");
}

void setup() {
  Serial.begin(9600);
  lcd.init();
  lcd.backlight();
  for (int i = 0; i < 16; i++) line[i] = ' ';
  line[16] = 0;
  for (int i = 0; i < LEN; i++) a[i] = 2;
  Serial.println("Happy Pi Day! Working out pi:");
  startedAt = millis();

  int predigit = 0;
  int nines = 0;
  for (int j = 0; j < DIGITS; j++) {
    uint32_t q = 0;
    for (int i = LEN; i > 0; i--) {
      uint32_t x = 10UL * a[i - 1] + q * i;
      uint32_t d = 2UL * i - 1;
      q = x / d;              // one division, the slow part on an 8-bit chip
      a[i - 1] = x - q * d;   // and the remainder from it, for free
    }
    a[0] = q % 10;
    q /= 10;
    if (q == 9) {
      nines++;
    } else if (q == 10) {
      emit(predigit + 1);
      for (int k = 0; k < nines; k++) emit(0);
      predigit = 0;
      nines = 0;
    } else {
      if (j > 0) emit(predigit);
      predigit = q;
      for (int k = 0; k < nines; k++) emit(9);
      nines = 0;
    }
  }
  emit(predigit);
  Serial.println();
  Serial.print(shown);
  Serial.print(" digits in ");
  Serial.print((millis() - startedAt) / 1000.0);
  Serial.println(" s");
  lcd.setCursor(0, 1);
  lcd.print("Happy Pi Day!   ");
}

void loop() {
}