Wert im Array schnellstmöglich finden

[yaro]

Ich verwende einen ATmega32. An den Programm-Flash habe ich ehrlich gesagt garnicht gedacht (und wusste bis jetzt auch garnicht, wie man Variablen dort abspeichern kann). Habe nämlich C zuerst mit einem PC gelernt, und dort stellt sich diese Frage nicht. Ich weiß zwar, wie man das in ASM macht, dachte aber, dass der C-Compiler alle Variablen (und Konstanten) zuerst in den Flash kopiert, und dann mit ihnen arbeitet. Aber nun werde ich wohl wirklich einfacheine Tabelle anlegen, und aus ihr rauslesen. Werde wohl kaum alle 32kb Flash brauchen...

Der code für sqrt sieht folgendermaßen aus (in C):

uint8_t squareroot(uint16_t value){
  uint8_t pos = 128, posdiff = 64;
  uint16_t squarepos = 128*128;

  while(posdiff){                                  //Intervallschachtellung
    if(squarepos < value){
      pos += posdiff;
    }else if(squarepos > value){
      pos -= posdiff;
    }else{
      return pos;
      break;
    }
    posdiff /= 2;
    squarepos = pos*pos;
  }

  if(squarepos < value){                              //Annäherung der Variable an eine ganze Zahl
    if((int)((value - squarepos) - ((pos+1)*(pos+1) - value)) > 0){
      return ++pos;
    }else{
      return pos;
    }
  }else if(squarepos > value){
    if((int)((squarepos - value) - (value - (pos-1)*(pos-1))) > 0){
      return --pos;
    }else{
      return pos;
    }
  }else{
      return pos;
  }
}

Die Optimiertung ist auf Stufe s.
Für eine Wurzel brauche ich ca.250T. Math.h braucht im Durchschnitt 820.
Hättest du einen Verbesserungsvorschlag für die Funktion?

Gruß, Yaro

[mare_crisium]

Hallo yaro und SprinterSB,

ihr habt zwar schon eine praktische Lösung gefunden, es gibt aber noch einen Weg nach Rom (oder ins RAM?) ! Die Beschreibung ist ein bisschen holprig, ich hoffe aber, dass die Beispiele das wieder ausbügeln.

Ciao,

mare_crisium

Edit: Anhang gelöscht wg. Upload-Limit

[yaro]

Ja... das mit den vielen Wegen ist wohl wahr =)
Am interessantesten finde ich das mit der Berechnung der nächstfolgenden RAM-Adresse.

Gruß, Yaro

[Richard]

Hallo yaro und SprinterSB,

ihr habt zwar schon eine praktische Lösung gefunden, es gibt aber noch einen Weg nach Rom (oder ins RAM?) ! Die Beschreibung ist ein bisschen holprig, ich hoffe aber, dass die Beispiele das wieder ausbügeln.

Ciao,

mare_crisium

Moin moin.

Etwas Holprig ist guuut... Aber wenn die Zahlen im Arry vorher feststehen,
kann man diese doch auch vor dem Abspeichern der Größe nach sortieren.

Bei der Abfrage fängt man in der Mitte vom Arry an und prüft auf
gleich, >, < als der Wert der Speicherstelle. Ist die gesuchte Zahl
größer, halbeirt man den oberen Rest des Arrys. Ist der Wert kleiner
halbiert man die untere Hälfte vom Arry und wiederholt das ganze bis
die Zahl = dem Arry Inhalt ist. Es ist lange her (noch unter Dos und
Quik-Basic), wenn ich es richtig in Erinnerung habe soll egal wie groß
das Arry b.z.w. die Datei ist, nach spätestens 11 Zugriffen der gesuchte
Wert gefunden sein???? Ich hatte seinerzeit damit Random Dateien
durchsucht aber fragt mich nicht wozu ich das seinerzeit gebraucht
habe.

Grüße Richard

[yaro]

Das ist genau das, was ich gemacht habe =) (es nennt sich Intervallschachtellung)
Aber ganz so einfach, wie du e bschrieben hast, ist es nicht, denn eine Vorkehrung muss man noch machen: wenn der Wert nicht im array drin ist, muss das auch erkannt werden und dann der ihm nähste wert genommen werden.

Gruß, Yaro