/* Wurzel_Funktion
  Datum: 12.04.2024
  Zweck: Die Wurzel einer Zahl berechnen
  Autor: MIWIS
*/

/* 
Der Werte-Bereich liegt zwischen 0 und 2^32 - 1 (4.294.967.295)
Achtung, der rechte Wert im Quadrat darf 2^16 nicht überschreiten.
Die maximale Anzahl der Schleifendurchläufe beträgt daher 17  
Python kann beispielsweise mit beliebig großen Zahlen umgehen.
*/
// maximal 4,294,967,295 (2^32 - 1)
unsigned long zahl = 337873941;
int warte = 0;

// hier startet das Programm
void setup() {
  // die serielle Schnittstelle (USB) wird initialisiert
  Serial.begin(115200); /*Bits pro Sekunde(Baud)*/
  // auf dem seriellen Monitor wird etwas zeilenweise ausgegeben
  Serial.println("***Programm startet***");
  Serial.print("Berechne Wurzel aus ");
  Serial.println(zahl);
  wurzel_berechnen();
  Serial.println("***Programm beendet***");
}

void loop() {
}

void wurzel_berechnen() {
  //zahl -= 0;
  int schritte = 0;
  unsigned long links = 1;
  unsigned long rechts = zahl;
  // rechter Wert darf maximal 2^16 - 1 betragen
  if (rechts > pow(2,16)) {
    rechts = pow(2,16) - 1;
  }
  unsigned long hilf = (rechts + links) / 2;
  Serial.println("hilf links rechts");

  while (1) {
    schritte +=  1;
    Serial.print(hilf);
    Serial.print(" ");
    Serial.print(links);
    Serial.print(" ");
    Serial.println(rechts);
    delay(warte);

    if (rechts - links == 1) {
      Serial.println("Abbruch -> rechts - links == 1");
      Serial.print("Die Wurzel aus ");
      Serial.print(zahl);
      Serial.print(" liegt zwischen ");
      Serial.print(links);
      Serial.print(" und ");
      Serial.println(rechts);
      Serial.print(schritte); Serial.println( " Durchgänge benötigt.");
      // welche Wurzel ist genauer? Wir vergleichen die Abstände der Quadrate
      if (rechts * rechts - zahl < zahl - links * links) {
        Serial.print(rechts);
        Serial.print(" im Quadrat ist näher an ");
        Serial.print(zahl);
        Serial.print(" als ");
        Serial.print(links);
        Serial.println(" im Quadrat");

      } else {
        Serial.print(links);
        Serial.print(" im Quadrat ist näher an ");
        Serial.print(zahl);
        Serial.print(" als ");
        Serial.print(rechts);
        Serial.println(" im Quadrat");
      }
      delay(100);
      return;
    }

    if (hilf * hilf == zahl) {
      Serial.println("Abbruch -> hilf * hilf == zahl");
      Serial.print("Die Wurzel aus ");
      Serial.print(zahl);
      Serial.print(" ist ");
      Serial.println(hilf);
      Serial.print(schritte); Serial.println( " Durchgänge benötigt.");
      delay(100);
      return;
    }

    if ((hilf * hilf) > zahl) {
      rechts = hilf;
    }
    else {
      links = hilf;
    }
    hilf = (rechts + links) / 2;
  }
}