Quote (CyberPunk666 @ 24 Nov 2013 13:07)
van egy gyorsulásmérőm, ami 6 tengelyes (x,-x,y,-y,z,-z)
Ezt ő 3 darab előjeles 16 bites számként adja meg.
int16_t X,Y,Z
Kellene az eredő g erő.
Mivel ezek mind egymásra merőleges tengelyek:
eredo=sqrt(X*X+Y*Y+Z*Z)
A probléma pedig a következő.
Mivel X egy előjeles 16 bites szám, és a processzor maximum ekkorát tud kezelni, ezért az X*X műveletet nem tudja elvégezni, hiszen két 15 bites szám szorzata (az MSB az előjel), nem fér el 16 biten. Már az 1024*1024 (egyhelyben tartva 1024=1g az Y értéke, ami gravitációs erőt mutatja) is jóval nagyobb, mint a 65534 (16 biten maximálisan tárolható érték).
Ezt a problémát megoldottam még ciklussal, ami X alkalommal összeadja X-t önmagával. Minden összeadás alkalmával megvizsgálja, hogy ez a 16 bites változó túlcsordult-e, ha igen, akkor egy másikat inkrementál. Így végül az X*X kiszámítható és kettő darab 16 bites regiszterben tárolható.
Még ezek összeadása is megoldható, aminek eredménye egy olyan szám, ami maximális kitérések esetén ((32767^2)*3)=3 221 028 867
Ez a szám 32 bites változót igényel.
Ez a 32 bites változó rendelkezésre áll 2 darab 16 bites változóban. Ezeket a rendszer nem tudja egy, összetartozó adatként fogadni. Tehát nekem kell a kapcsolatot megcsinálni.
Hogyan vonjak belőle gyököt?
Az elv érdekel, nem mással akarom megcsináltatni, szóval a processzor típusa lényegtelen.
A baj az, hogy valahogy becsülni kéne, hogy rendes időn belül le tudjon futni az algoritmus. Mivel az eredő gyakorlatilag 0-56754-ig terjedhet, ezért ez kibaszott sok számítást igényelne.
Reméltem, hogy van itt valami pr0 eltés vagy bmes, aki tud erre valami gyors és optimális módszert.
Léteznek egész számokra megírt gyökvonó eljárások, amelyek elég jól becsülhetőek. (Float esetben akár konstans időn belül is elvégezhető:
http://www.beyond3d.com/content/articles/8/)
Amire neked van szükséged, az egy integer square root algoritmus. Ilyenek léteznek, például én ezt használom:
Code
inline wt_i32 sqrt_i32(wt_i32 n)
{
wt_i32 a = 0;
while(n>=(a<<1))
{
n -= ((a++)<<1) + 1;
}
return a;
}
Ez felülről becsülhető, hiszen 'n' 32 bites. Hasonló létezik 64-bites egészekre is.
Google kiadott egy nagyon jót:
http://www.finesse.demon.co.uk/steven/sqrt.htmlVan asm és C kód is benne, érdemes végigolvasni. Talán ez az egyik legjobb ebben a témában. Eglsz sok magyarázat van benne.
(a többi post az tl;dr volt, de majd most elolvasom)