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

LiquidCrystal_I2C lcd(0x27, 20, 4);

const int buttonPin = 2;

// Рекурсивная функция Фибоначчи с кэшированием (мемоизация)
// Это ускоряет в 100+ раз, но сохраняет рекурсию
unsigned long long fibCache[31];

unsigned long long fibonacci(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (fibCache[n] != 0) return fibCache[n];
  fibCache[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return fibCache[n];
}

void printLargeNumber(unsigned long long num) {
  if (num >= 10) {
    printLargeNumber(num / 10);
  }
  lcd.print((char)((num % 10) + '0'));
}

void setup() {
  Wire.begin();
  lcd.init();
  lcd.backlight();
  
  pinMode(buttonPin, INPUT_PULLUP);
  randomSeed(analogRead(A0));
  
  // Очищаем кэш
  for (int i = 0; i < 31; i++) fibCache[i] = 0;
  
  lcd.clear();
  lcd.setCursor(0, 0);
  lcd.print("Press button");
  lcd.setCursor(0, 1);
  lcd.print("to generate");
  lcd.setCursor(0, 2);
  lcd.print("random N (5-30)");
}

void loop() {
  if (digitalRead(buttonPin) == LOW) {
    delay(50);
    
    if (digitalRead(buttonPin) == LOW) {
      
      int randomNum = random(5, 31);
      
      lcd.clear();
      lcd.setCursor(0, 0);
      lcd.print("Random N = ");
      lcd.print(randomNum);
      lcd.setCursor(0, 1);
      lcd.print("Calculating...");
      lcd.setCursor(0, 2);
      lcd.print("Please wait...");
      
      // Замер времени
      unsigned long startTime = micros();
      
      // Очищаем кэш перед вычислением
      for (int i = 0; i < 31; i++) fibCache[i] = 0;
      
      unsigned long long fibResult = fibonacci(randomNum);
      unsigned long endTime = micros();
      
      float elapsedSeconds = (endTime - startTime) / 1000000.0;
      
      // Вывод результатов
      lcd.clear();
      lcd.setCursor(0, 0);
      lcd.print("Random N = ");
      lcd.print(randomNum);
      
      lcd.setCursor(0, 1);
      lcd.print("Time: ");
      lcd.print(elapsedSeconds, 6);
      lcd.print(" sec");
      
      lcd.setCursor(0, 2);
      lcd.print("Number: ");
      printLargeNumber(fibResult);
      
      lcd.setCursor(0, 3);
      lcd.print("                ");
      
      while(digitalRead(buttonPin) == LOW);
      delay(50);
    }
  }
}