Effektiv "lookup table"-sökalgoritm

[twse]

Om lookupvärdet går mot oändligheten så kanske du kan använda 1/x istället som sökvärde?
Och om värdet går mot noll i andra änden så kan du dela upp det i två tabeller, varav den ena är linjärt proportionell och den andra inverterad (1/x).

Japp, det är i praktiken samma sak som lösningen jag föreslog. Om kvoten y / x > 1 så kollar man upp x / y istället, i samma tabell, och omvandlar resultatet.

[bearing]

ahlsten tipsade om http://en.wikipedia.org/wiki/CORDIC
i den här tråden http://elektronikforumet.com/forum/view ... =7&t=45090

[twse]

Intressant, om man har väldigt ont om minne så är det en bra idé. Man kan nog få högre precision också än med lookup-tables. Men det lämpar sig väl mer för sin, cos och tan än för arcsin, arccos och arctan, eller kan man köra något liknande baklänges?

[bearing]

Jag googlade efter: arctan cordic, och fann den här:
http://www.convict.lu/Jeunes/Math/arctan.htm
Så det verkar ju gå även baklänges.

[4kTRB]

Nu vet jag inte om det är ett seriöst alternativ men
derivatan av arctan(x) = 1/(1+x^2) så om du kan
integrera snabbt så är det ett sätt.

På wiki listar de den här formeln av Euler...





http://en.wikipedia.org/wiki/Inverse_tr ... _functions

[Korken]

Jag har testat lite olika funktioner nu och kan först stapla upp de som inte fungerade så bra (de tog lång tid för att få bra precision):
- Matte formel av summor eller produkter. Samt det var ofta svårt att inte gå över max storleken på 32bitars tal.
- Testade taylorutveckling och den var mest lovande! Dock den var fortfarande ca 3ggr långsammare än min tabellsökning och arctan2.

De som fungerade bättre:
- arctan2, men de roliga var att kolla vart man var för att spegla å så vidare så tog det ish lika lång tid som den extra iterationen för att köra min sökalgoritm. Vilket var ganska förvånande.
Så den drar mindre på minnet med ish samma prestanda.
- Min lilla rackare. Tar mer minne men är också ganska snabb. (fick ner både arctan2 och min till ca 180-200 klockcykler i "worst case" och runt 110-130 i medel.

Jag har dock inte testat att transformera indexena, men jag är nöjd med det jag fick så tror jag stannar här.

Så jag är ganska nöjd! Tackar alla för hjälpen!
Ska putsa vidare på det här och se om jag kommer på något bra.

[Korken]

Justja! Glömde ju å posta koden!
Slit den med hälsan folk!

Den är skriven som fixed point just nu, men kan lätt konverteras för annat. Samt x är större än 0.

Kod: Markera allt

fixed fArcTan(fixed x)
{
	fixed* start;
	start = &fArcTan_table[0];
	fixed* end;
	end = &fArcTan_table[ARC_TABLE-1];
	fixed* ptr;
	fixed* jmp;	
	
	do 	// When the length of the jump is 1 or less, then we have the answer.
	{
		jmp = ptr;
		ptr = start + ((end - start) >> 1); 	// Middle of the table

		if (*ptr < x)
			start = ptr;
		else
			end = ptr;
			
		jmp = (int*)(abs(jmp - ptr));
	} while (jmp > (int*)0);
	
	return ((fixed)int2fp(ptr - &fArctan_table[0]) >> 2); 	// No. of steps from table start divided by 4 -> Degrees
}

[twse]

En liten förenkling?

Kod: Markera allt

fixed fArcTan(fixed x)
{
   int start = 0;
   int end = ARC_TABLE - 1;
   int index;
   
   while (end > start) {
      index = (end - start) >> 1;

      if (fArcTan_table[index] < x)
         start = index;
      else
         end = index;
   }
   
   return ((fixed) int2fp(index) >> 2);    // No. of steps from table start divided by 4 -> Degrees
}

[Korken]

Mycket stiligare!
Dock så går den saktare nu för någon anledning... Ska undersöka asm-koden och se vad som hände.
Edit: Samt för att den ska fungera nu måste man göra såhär:

Kod: Markera allt

fixed fArcTan(fixed x)
{
	int start = 0;
	int end = ARC_TABLE - 1;
	int index;
	   
	while (end > start+1)
	{
		index = (start + end) >> 1;

		if (fArcTan_table[index] > x)
			end = index;
		else
			start = index;
	}

[twse]

Skulle bara se om någon var uppmärksam...

Det är helt rätt, om (end == start + 1) så blir (index == start), och om (fArcTan_table[index] <= x) så blir (start = start) och min rutin loopar för evigt. Den här typen av rutiner kräver stor uppmärksamhet för detaljer. Jag skrev en quicksort-rutin i asm en gång (väldigt likt detta) och det var klurigt att få det rätt.

Jo, beroende på kompilator och processor kan pekare vara snabbare än index eller tvärtom. Men för mig brukar kodens läslighet ha högsta prioritet, och då kör jag med index i vilket fall som helst.

[Korken]

Det är vad jag vill kalla en bra rutin att ha.
Ibland snöar man lätt in sig på effektivitet och funktionen i sig blir näst in till oförståelig.

Jag har kollat på asm-koden nu och de är väldigt lika. Dock den gör något konstig vid varje läsning av värdet som drar upp tiden.
Ska se om jag lyckas optimera bort det.

[4kTRB]

Surfade på annat och råkade se den här AN2341 från Cypress

"Algorithm - ArcTan as Fast as You Can"

kanske inte klarar kraven men intressant läsning i vilket fall

http://www.cypress.com/?docID=2279