/*
 * Berechnung der ersten 384 Fibonacci-Zahlen bis 10^80
 * 
 */

#define NO_PRINT
#define NO_CONVERT

// 3 BCD kodierte Zahlen mit 80 Dezimalstellen
uint8_t z[3][40];
char str_buffer[100];

// z3 = z1 + z2;
void add80(uint8_t *z1, uint8_t *z2, uint8_t *z3) {
  uint8_t i, carry, tmp, low, high, lowA, highA;

  carry = 0;
  for (i=0; i<40; i++) {
    tmp   = z1[i];
    low   = tmp & 0xF;
    high  = tmp >> 4;
    tmp   = z2[i];
    lowA  = tmp & 0xF;
    highA = tmp >> 4;
    
    lowA  += low + carry;
    if (lowA > 9) {
      lowA  -= 10;
      carry = 1;
    } else {
      carry = 0;
    }
    highA += high + carry;
    if (highA > 9) {
      highA -= 10;
      carry = 1;
    } else {
      carry = 0;
    }
    z3[i] = (highA<<4 ) | lowA;
  }
}

// Umwandlung in ASCII
void convert80(uint8_t *zahl, char *str) {
  uint8_t tmp;
  
  for (int i=39; i>=0; i--) {
    tmp   = zahl[i];
    *str++ = (tmp >> 4) + '0';
    *str++ = (tmp & 0xF) + '0';
  }
  *str = 0;
}

// Ausgabe auf UART

void print80(uint8_t *zahl) {
  uint8_t tmp, low, high;
  
  for (int i=39; i>=0; i--) {
    tmp   = zahl[i];
    low   = tmp & 0xF;
    high  = tmp >> 4;
    Serial.print(high);
    Serial.print(low);
  }
}

void setup() {
  Serial.begin(115200);
  Serial.println();
  Serial.println(F("Fibonaccizahlen bis 10^80"));
  z[1][0] = 1;
}

void loop() {
  long start, stop;
  int i, j;

#ifndef NO_PRINT
  // Number 0 und 1 sind nicht berechnet
  Serial.print(0);
  Serial.print(" ");
  print80(z[0]);
  Serial.println();

  Serial.print(1);
  Serial.print(" ");
  print80(z[1]);
  Serial.println();
#endif

  start = millis();
  j=2;
  for (i=2; i<=384; i++) {
    switch(j) {
      case 2: add80(z[0], z[1], z[2]); break;
      case 1: add80(z[2], z[0], z[1]); break;
      case 0: add80(z[1], z[2], z[0]); break;
    }
#ifndef NO_CONVERT
  convert80(z[j], str_buffer);
#endif          
#ifndef NO_PRINT
    Serial.print(i);
    Serial.print(" ");
    Serial.print(str_buffer);
    Serial.println();
#endif    
    j++;
    if (j>2) j=0; 
  }
  stop = millis();
  Serial.print(F("Rechenzeit: "));
  Serial.print(stop-start);
  Serial.println(F("ms"));
  while(1);
}