sortiertes Array durchsuchen

Hi,
ich habe ein sortiertes Array mit 91 Elementen. Es ist die Sinus-Tabelle von hier. Ich möchte nun mithilfe der Tabelle den asin bestimmen und habe 2 Methoden implementiert.
Tabelle:

static const int16_t linsin_tab[91] PROGMEM = 
{
	0x0000, 0x023c, 0x0478, 0x06b3, 0x08ee, 0x0b28, 0x0d61, 0x0f9a, 0x11d1, 0x1406,
	0x163a, 0x186d, 0x1a9d, 0x1ccb, 0x1ef8, 0x2121, 0x2348, 0x256d, 0x278e, 0x29ad,
	0x2bc8, 0x2ddf, 0x2ff4, 0x3204, 0x3410, 0x3619, 0x381d, 0x3a1d, 0x3c18, 0x3e0f,
	0x4001, 0x41ed, 0x43d5, 0x45b7, 0x4794, 0x496c, 0x4b3d, 0x4d09, 0x4ecf, 0x508e,
	0x5248, 0x53fb, 0x55a7, 0x574d, 0x58eb, 0x5a83, 0x5c14, 0x5d9e, 0x5f20, 0x609b,
	0x620f, 0x637a, 0x64df, 0x663b, 0x678f, 0x68db, 0x6a1f, 0x6b5b, 0x6c8e, 0x6db9,
	0x6edb, 0x6ff5, 0x7106, 0x720e, 0x730d, 0x7403, 0x74f0, 0x75d4, 0x76af, 0x7781,
	0x7849, 0x7908, 0x79bd, 0x7a69, 0x7b0c, 0x7ba5, 0x7c34, 0x7cb9, 0x7d35, 0x7da7,
	0x7e0f, 0x7e6e, 0x7ec2, 0x7f0d, 0x7f4e, 0x7f85, 0x7fb1, 0x7fd4, 0x7fed, 0x7ffc,
	0x7fff
};

naive Suche (durchlaufen des Array):

int16_t linasin(const int16_t input)
{
	uint8_t neg = input<0 ? 1 : 0;
	uint16_t _input = abs(input);
	if(_input == 0)
		return 0;
	for (uint8_t i = 0; i < 90;i++)
	{ 
		uint16_t data0 = pgm_read_word(&linsin_tab[i]);
		uint16_t data1 = pgm_read_word(&linsin_tab[i+1]);
		if (_input >= data0 && _input < data1)
		{
			data1 -= data0;
			data0 = _input - data0;
			int16_t res = ((int16_t)i << 8) + ((int32_t)data0 << 8) / data1;
			return neg ? -res : res;
		}
	}
	return neg ? -0x5A00 : 0x5A00; //90 * 256
}

und binäre Suche:

int16_t linasin(const int16_t input)
{
   uint8_t low = 0, mid, high = 91;
   uint8_t neg = input<0?1:0;
   uint16_t _input = abs(input);

   if(_input==0)
       return 0;

   while (low < high) 
   {
       mid = low + ((high - low) / 2);
       if (pgm_read_word(&linsin_tab[mid]) < _input)
          low = mid + 1;
       else
          high = mid;
   }
   if (low < 91)
   {
      int16_t data0 = pgm_read_word(&linsin_tab[low-1]);
      int16_t data1 = pgm_read_word(&linsin_tab[low]);

      data1 -= data0;
      data0 = _input - data0;
      int16_t res = (((int16_t)low-1) << 8) + ((int32_t)data0 << 8) / data1;
      return neg ? -res : res;  
   }
   else
      return neg ? -0x5A00 : 0x5A00; 

}

Mein Problem ist, dass ich für die naive Suche maximal 2469 Cycles benötige, für die binäre Suche allerdings immer 2273. Wie kann ich das schneller machen, bzw welche Alternativen gibt es? Leider weiß ich nicht wie ich die binäre Suche abkürzen könnte, da ich nicht abfragen kann pgm_read_word(&linsin_tab[mid]) == _input weil das Ganze noch interpoliert werden muss.

LG

SeppJ

Du könntest eine Näherung des Arcussinus benutzen die deutlich weniger als 2000 takte braucht um damit einen besseren Startwert für die Suche zu bekommen (und von da aus dann binär oder linear suchen). Der Arcussinus ist über weite Bereiche recht gut linear approximierbar, das sollte reichen.

Ich bin mir zwar nicht sicher ob ich dich richtig verstanden habe, aber ich habe jetzt als Startwert für mid (binäre Suche) eine lineare Approximation verwendet.

Die Suche benötigt maximal (habe nur ein paar Werte probiert) 2461 Ticks und minimal ca 1100. Das ist mir allerdings im Vergleich zum Sinus (mit < 70) noch zu viel. Vermutlich werde ich eine 2te Tabelle für die inversen Werte verwenden...

Eine Alternative wäre einen CORDIC-Algorithmus zu verwenden. Allerdings benötigt der Schnellste(den ich gefunden habe) für sin/asin usw. ~750 Cycles.

LG