Fixed point-problem

[Korken]

Godagens!

Jag håller på och optimerar en beräkningsloop jag har med fixed point där jag räknar ut normalen av 2st accelerationsvektorer.
Problemet är att svaret inte får plats i mitt fixed point tal när man kvadrerar talen:

Kod: Markera allt

c = sqrt(a^2 + b^2)

a och b kan vara upp till 4095 (2^12) (från sensorerna) vilket ger att deras kvadrater behöver minst 24bitar, medans jag bara har 13 bitar över till dem (decimal delen har 18 bitar och 1 bit till tecken, 32 bitar totalt).

Finns det något trick man kan göra för att få detta att fungera?
Jag funderar på att dividera allt med ett godtyckligt tal som jag sedan kan gångra med igen så här:

Kod: Markera allt

c = sqrt((a/d)^2 + (b/d)^2)*d

för att skala om talet, men det borde finnas något bättre sätt att göra det på tycker jag.
För problemet här är om jag gör de för små så försvinner de när man tar kvadraten på de och är det förstora så får de inte plats.

Tack på förhand!

Mvh
Emil

[jesse]

Om något av talen är >= (2 ^ 6) shiftas båda talen ner en bit åt gången tills båda blir lägre än 64.

(64*64+64*64 = 8192 = 2^13 = max.)

Sedan utför du beräkningen. Om du sparat i minnet hur många shift du gjort, så shiftar du nu tillbaks resultatet samma antal steg.

Detta påverkar inte små tal.

[Korken]

Ahh, smart!

Typ något i den här stilen? fMul(x,y) är fp-multiplikation och fSqrt(x) är fp-roten ur.

Kod: Markera allt

fixed fNorm(fixed a, fixed b)
{
	int i = 0;
	while((a > 64) || (b > 64))
	{
		a >>= 1;
		b >>= 1;
		i++;
	}
	
	return (fSqrt(fMul(a,a) + fMul(b,b)) << i);
}

[sodjan]

Nedanstående kanske berör detta ämne :
http://www.piclist.com/techref/microchi ... /index.htm

[jesse]

Korken: precis!
Så som du skrivit det fungerar det på positiva tal.
Har du även negativa tal får du modifiera lite.

Jag har själv haft liknande problem med multiplikation av mätvärden med hög noggrannhet.

När man kan ha ett värde mellan -400.000 och 400.000 med upplösning 0.001 så kan man kanske tolerera en viss avvikelse , t.ex. 0.5 när värdet ligger mellan 50 och 400 , men när värdet ligger runt 0.050 så vill man inte ha ett fel på 0.500 !

[Nerre]

I och med att det handlar om kvadrering så blir ju modifieringen för negativa tal minimal: Bara att byta tecken på eventuella negativa tal.

(-x)^2 = x^2

[Korken]

Fixat!

Kod: Markera allt

fixed fNorm(fixed a, fixed b)
{
	int i = 0;
	a = (fixed)abs((int)a);
	b = (fixed)abs((int)b); 
	
	while((a > 64) || (b > 64))
	{
		a >>= 1;
		b >>= 1;
		i++;
	}
	
	return (fSqrt(fMul(a,a) + fMul(b,b)) << i);
}

Tack för all hjälp!
Liten fundering dock, om man tar sin variabel x &= 0x7FFFFFF; borde inte det bli samma som absolutbelopp på ett 32bitars tal? Genom att cleara sign biten.

[LHelge]

inte om det är tvåkomplement va? då får du väl invertera alla bitar och addera ett om signbiten är satt.

Edit:
eller om det var tvärt om, subtrahera ett och sen invertera..

[monstrum]

Skulle rekommendera att använda delat med 2 istället för shiftoperatorn. Kompilatorn kommer att förstå att den kan använda en shift, i alla fall om optimering inte är helt avstängt.
Fördelen är att det t.o.m kan gå fortare att exekvera för negativa tal då kompilatorn kan använda de shiftinstruktioner som bevarar sign-biten. Något som inte blir lika enkelt för den ifall du skriver:

Kod: Markera allt

char sign = 0;
if( tal < 0 ) {
    tal = -tal;
    sign = 1;
}
tal >>= 1;
if( sign ) {
    tal = -tal;
}

[Korken]

LHelge: Så rätt så! Ibland tänker man för fort...

monstrum: Det är helt klart att föredra. Jag kollade precis på asm koden som blir och den blir med instruktionen som bevarar sign biten, men det kan ju bara ha varit tur.
Ska ändra till delat med 2 och se om den blir lika.

[Korken]

Jag utökar denna tråd med en till fixed point funktion.

Jag har optimerat min fSqrt ett tag nu och jag har fastnat. Går denna att optimera mer? Eller finns det någon bättre funktion?
Loopen körs 10ggr som mest, oftast max 2-5ggr.

Det jag inte gillar är för varje loop måste en division (fDiv) göras med den här.

Kod: Markera allt

fixed fSqrt(fixed num)
{
	fixed a = num;

	while ((fMul(a, a) - num) > ONE/1000) // while error > 0.001 fp
		a = (a + fDiv(num,a))/2;
	
	return a;
}

[jesse]

Skulle rekommendera att använda delat med 2 istället för shiftoperatorn. Kompilatorn kommer att förstå att den kan använda en shift, i alla fall om optimering inte är helt avstängt.
Fördelen är att det t.o.m kan gå fortare att exekvera för negativa tal då kompilatorn kan använda de shiftinstruktioner som bevarar sign-biten. Något som inte blir lika enkelt för den ifall du skriver:

Kod: Markera allt

char sign = 0;
if( tal < 0 ) {
    tal = -tal;
    sign = 1;
}
tal >>= 1;
if( sign ) {
    tal = -tal;
}

Sånt där är intressant. Själv ska jag göra ett par hundra liknande beräkningar i en inte så hemskt tidskritisk miljö, men ändå, man vill inte slösa tid på en massa 32-bitars multiplikationer och särskilt inte divisioner om man kan klara sig med ett par shift. Men i och med att optimeraren är intelligentare än jag ( ) så kanske man lurar sig själv när man gör krångliga omvägar för att kunna shifta på rätt sätt. Problemet är att man aldrig vet när optimeraren tycker den ska shifta och när den tycker att multiplikation/division är OK. Multiplicera med tre kan ju också lösas lätt med shift + addition. eller division med sju: tre shift och en subtraktion. Hänger optimeraren med på sådana smarta saker? knappast!?

[LHelge]

Jag lånar din tråd lite för att fortsätta diskussionen. Om jag vill konvertera ett flyttal till fixed för att testa din kod. Jag är lite ringrostig vad gäller det här med fixed point

Du har definierat dina fixed som 32 bitar med 18 som fractional, kommer den här koden fungera för att konvertera ett flyttal till din sorts fixed

Kod: Markera allt

float f = 1.2345;

fixed fix = (fixed)f*262144.0f; // 2^18 = 262144

[jesse]

Ser inte bra ut (men jag vet inte, jag gissar).

Det finns alltså ingen inbyggd / överlagrad tilldelningsoperator från float till fix?
Eller vad gör denna: fixvariabel = (fixed)flyt_variabel ?

Du verkar förutsätta att det översätts till ett 32-bitars int, som sedan tolkas som ett fixtal?
Om det funkar så så kanske din kod fungerar. Men det låter lite konstigt.

Men man kan kringgå alltihop med hjälp av pekare. Då omvandlar du först ditt float till ett heltal efter att ha multiplicerat med 2^18. Sedan tar du en fixtals-pekare och låter den peka på adressen för heltalet. Då kommer du att få rätt värde på ditt fixtal.

Kod: Markera allt

float f = 1.2345;

fixed filurfix;
double*  dubpek = &filurfix;

dubpek* = (double)f*262144; // 2^18 = 262144

// nu har filurfix fått värdet av double / 2^18

Kod: Markera allt

f = 1.2345
f*262144 = 323617 = 0b1001111000000100001
filurfix = 1.001111000000100001   =  323617 / 262144 = 1.2345

[sodjan]

Alltså...

Ni är helt ute och cyklar och verkar inte alls förstå "fixed point".

Vilken kompilator är använd för kodexemplen i de senaste inläggen ?
Är det testat ?
En typdeklaration "fixed" vore komplett meningslös utan att ange
den "fixa" positionen för kommat !!
Vad skulle annars skillnaden vara på "int fix" och "fixed fix" ???

"Fixed point" är inget som *processorn* vet vad det är. Jag känner inte
till någon processor arkitektur, modern eller historisk, där det ingår
något som skulle motsvara "fixed point". Det är enbart något som vi
som programmerare föreställer oss och som finns i våra huvuden.

Det är ungefär som att räkna vikter i Kg men använda gram för
beräkningarna, d.v.s vi har en underförstådd "fixed point" efter
de 3 lägsta siffrorna. Det är inget som på något sätt påverkar själva
beräkningarna, de går alldeles utmärkt att göra i (hela) gram
representerat av vanliga heltal/integers. Vill vi räkna "kilon" med
bättre noggranhet, så kan vi räkna milligram istället. Fortfarande
är det inget annat än helt vanliga heltal/integers !

"Fixed point" har enbart med hur vi *tolkar* en (vanlig) integer.

Eller med andra ord, istället för att räkna med Kg i float så räknar
vi med gram som integers. Kommat, "the fixed decimal point",
finns aldrig med i beräkningarna, det läggs enbart till vid presentation.

Stoppa in ett komma i värdet i gram efter de 3 lägsta siffrorna, så
hokus-pokus, vi har ett värde i Kg ! Men kommat behövs inte förrens
värdet ska presenteras !

Som sagt, "fixed point" är ingenting som varken processorn eller språken
behöver kunna eller veta något om...

Jag känner inte till ett enda språk som har en "fixed point" datatyp.
Däremot finns det många exempel på språk där heltal/integers kan ha
en "edit-option" där det underförstådda decimalkommats position
anges. Dock ändrar detta inte alls hur värdet representeras i minnet,
det är fortfarande en helt vanlig int. Som i COBOL t.ex.

Kod: Markera allt

float f = 1.2345;
fixed fix = (fixed)f*262144.0f; // 2^18 = 262144

borde vara något i stil med

Kod: Markera allt

float f = 1.2345;
int fix = f * 262144; // 2^18 = 262144

Eventuellt om konstanten behöver castas till float för att undvika
att "f" castas till en int innan multiplikationen. Jag kan inte C...