//const size_t arraySize = 3868; //array to hold 7736 BCD digits on a mega, a bit over 37000 iterations
const size_t arraySize = 880; //array to hold 1760 BCD digits on an UNO, 8421 iterations
uint8_t num1[arraySize];
uint8_t num2[arraySize];
uint16_t loopcount = 0;
uint8_t* bcd1;
uint8_t* bcd2;
uint8_t* bcdTemp;

void setup() {
  Serial.begin(115200);
  //set num1 = 0, num2 = 1
  for (size_t i = 0; i < sizeof(num1); i++) {
    num1[i] = 0;
    num2[i] = 0;
  }
  num2[sizeof(num2) - 1] = 1;
  Serial.print(F("0:"));
  printBCD(num2, arraySize);
  bcd1 = num1;
  bcd2 = num2;
}

void loop() {
  addBCD(bcd1, bcd2, arraySize);
  loopcount++;
  if ((loopcount % 1000) == 0) {
    Serial.print(loopcount);
    Serial.print(':');
    printBCD(bcd1, arraySize);
    Serial.print(F("millis: "));
    Serial.println(millis());
  }
  if ((bcd1[0] >> 4) > 4) { //stop when doubling the number would cause overflow
    Serial.print(F("terminated at: "));
    Serial.println(loopcount);
    printBCD(bcd1, arraySize);
    Serial.print(F("millis: "));
    Serial.println(millis());
    while (true) {};
  }
  //swap digits 
  bcdTemp = bcd1;
  bcd1 = bcd2;
  bcd2 = bcdTemp;
}

void addBCD(uint8_t* bcd1, uint8_t* bcd2, size_t bcd_size) {
  //add bcd1 to bcd2, storing result in bcd1
  uint8_t carry = 0;
  uint8_t lowerBCD;
  uint8_t upperBCD;
  for (size_t i = 0; i < bcd_size; i++) {
    size_t index = bcd_size - i - 1;
    lowerBCD = (bcd1[index] & 0x0F) + (bcd2[index] & 0x0F) + carry;
    if (lowerBCD > 9) {
      lowerBCD = lowerBCD - 10;
      carry = 1;
    } else {
      carry = 0;
    }
    upperBCD = (bcd1[index] >> 4) + (bcd2[index] >> 4) + carry;
    if (upperBCD > 9) {
      upperBCD = upperBCD - 10;
      carry = 1;
    } else {
      carry = 0;
    }
    bcd1[index] = (upperBCD << 4) | lowerBCD;
  }
}

void printBCD(uint8_t* bcd, size_t bcd_size) {
  uint16_t numDigits = 0;
  bool leadingZero = true;
  for (size_t i = 0; i < bcd_size; i++) {
    byte upperBCD = bcd[i] >> 4;
    byte lowerBCD = bcd[i] & 0x0f;
    if (leadingZero && !(upperBCD == 0)) {
      leadingZero = false;
    }
    if (!leadingZero) {
      Serial.write('0' + upperBCD);
      numDigits++;
    }
    if (leadingZero && !(lowerBCD == 0)) {
      leadingZero = false;
    }
    if (leadingZero && (i == bcd_size - 1)) {
      leadingZero = false;
    }
    if (!leadingZero) {
      Serial.write('0' + lowerBCD);
      numDigits++;
    }
  }
  Serial.print(F("\nnumber of digits: "));
  Serial.println(numDigits);
}