[es] - Algoritan za korenovanje u asembleru

zofr

Član broj: 126534
Poruke: 119
*.dynamic.sbb.rs.

+1 Profil

Algoritan za korenovanje u asembleru

^{30.01.2009. u 20:47 - pre 185 meseci}

Posle duzeg vremena vratih se pred novogodisnje praznike, i poceh da cackam tamo gde sam stao pre vise meseci.

Pokusavam da mikrokontrolerom izmerim efektivnu vrednost AC napona, i za to mi je potrebno korenovanje. Ne mogu da se setim ni postupka korenovanja koji sam ucio u skoli, a tek na nivou bitova...

Ako je neko to radio bilo bi korisno za mene a mozda i jos nekog. Uzgred, trebala bi mi tacnost izmerene efektivne vrednosti oko 2%.

Pozdrav svima.

Odgovor na temu

madwolf
Milan Vukov
Leuven, Belgium

Član broj: 8409
Poruke: 51
92.244.136.*

Profil

Re: Algoritan za korenovanje u asembleru

^{31.01.2009. u 00:48 - pre 185 meseci}

Pa... prvo reci koji mikrokontroler 8B/16B/32B, kolicina RAM/ROM memorije, takt. Mislim da je najlakse da odradis sa look-up tabelom ukoliko imas dovoljno memorije. Zapravo, ako imas dovoljno ROM (flash) memorije ovo ti je najbrzi postupak da bi uradio korenovanje- najmanje racunanja (nema ga :)). A ujedno stedis i RAM. E sad, ako nemas dovoljno memorije, onda racunas... Ako se ipak odlucis za racunanje, pogledaj metod sukcesivnih aproksimacija (mislim da je ovo tacan termin). Ako ti ovo racunanje ipak bude trebalo, mogu da obesim ideju ovde...

Pozdrav,
Milan.

Odgovor na temu

rsinisa
Siniša Radanočević
Smederevo

Član broj: 2716
Poruke: 1586
79.101.69.*

+321 Profil

Re: Algoritan za korenovanje u asembleru

^{31.01.2009. u 10:26 - pre 185 meseci}

Nisi naveo familiju mikrokontrolera, ni potrebnu preciznost, ali evo za PIC, odaberi, pa prilagodi ako treba.

http://www.piclist.com/techref/microchip/math/sqrt/index.htm

Pozdrav.
Sinisha

Odgovor na temu

korak
Nis

Član broj: 125522
Poruke: 622
*.dynamic.sbb.rs.

+7 Profil

Re: Algoritan za korenovanje u asembleru

^{31.01.2009. u 13:06 - pre 185 meseci}

Drago mi je da si se vratio, dugo te nije bilo.

Evo ti postupka korenovanja koji ne zavisi od MCU-a ni od duzine celog broja. Predpostavljam da radis ca celim brojevima. On je napravljen po postupku koji smo ucili u skoli kada smo broj ciji se koren trazi delili na klase od po 2 cifre i t. d....

p := 0;
q := 1;
r := n;

while q <= n do q := q*4;

while q <> 1 do
begin
q := q div 4;
h := p-q;
p := p div 2;
if r >= h then
begin
p := p+q;
r := r-h;
end;
end;

Na kraju je:

p^2 <= n < (p+1)^2

Dakle, n je broj iz kojeg se vadi kvadratni koren, a p je rezultat.

Kada sam ja implementirao ovaj algoritam u svoje programe, on je trosio u proseku oko 50% vise vremena od deljenja. Ako se opredelis za ovaj algoritam, i imas problema sa implementacijom, onda javi koji je MCU u pitanju i sa koliko bajta racunas pa ce ti neko pomoci.

Pozdrav.

Odgovor na temu

zofr

Član broj: 126534
Poruke: 119
*.dynamic.sbb.rs.

+1 Profil

Re: Algoritan za korenovanje u asembleru

^{31.01.2009. u 20:56 - pre 185 meseci}

Evo malo vise detalja. Jednim pajacivacem apsolutne vrednosti, vodim AC signal (koji nije obavezno sinusoida) u 12-to bitni ADC, od toga pravim kvadratnu vrednost cije uzorke propustam kroz NF digitalni filter sa granicnom frekvencijom od oko 1Hz. Od te filtrirane vrednosti treba da dobijem korenovanjem efektivnu vrednost.

Do sada sam radio najvise sa PIC-om, ali sam pre mozda godinu dana malo obratio paznju na Freescale MC908, i nabavio sam u Austriji par komada MC9S08AW32 i Multilink S08/S12.

Interesuje me algoritam za korenovanje, koji u principu moze da se primeni na svaki mikrokontroler, dok mi gotovi programi zadaju problem jer ne mogu da ih primenim dok ih ne razumem. Probacu postupak koji je dao korak, pa ako imam problema javicu se.

Ako je neko, osim koraka, pisao kod za korenovanje, jako bi me interesovalo, jer bih voleo da koristim najbrzi algoritam.

Pozdrav svima.

Odgovor na temu

madwolf
Milan Vukov
Leuven, Belgium

Član broj: 8409
Poruke: 51
92.244.136.*

Profil

Re: Algoritan za korenovanje u asembleru

^{01.02.2009. u 02:47 - pre 185 meseci}

Koliko sam video imas 32K flash memorije, pa bi ti ja ponovo preporucio look-up tabelu.
Sto se tice racunanja, ukucaj u gugl:

sqrt successive approximations

izaci ce ti gomila korisnih linkova, pa ti proceni sta ti je najbrze :)

Pozdrav,
Milan.

Odgovor na temu

zofr

Član broj: 126534
Poruke: 119
*.dynamic.sbb.rs.

+1 Profil

Re: Algoritan za korenovanje u asembleru

^{01.02.2009. u 20:23 - pre 185 meseci}

Hvala na linkovima. Tamo vidim da se bar nekoliko puta koristi deljenje, akorak kaze da postupak koji je predstavio trosi 50% vise vremena od jednog deljenja. To jos nisam proverio.

Kada dobijem sumu kvadrata, ona je 24-o bitna, pa ne znam koliko bi trajao postupak primenom interpolacije za tako sirok opseg vrednosti. Da li da interpolacija bude linearna ili polinomalna (i kog reda). Ima li neko iskustva u tome.

Pozdrav.

Odgovor na temu

madwolf
Milan Vukov
Leuven, Belgium

Član broj: 8409
Poruke: 51
92.244.136.*

Profil

Re: Algoritan za korenovanje u asembleru

^{02.02.2009. u 02:39 - pre 185 meseci}

U ideji koju je predstavio <korak> ne koristis deljenje. Na primer, kad delis sa 4 to ti je ekv. sa siftovanjem u desno dva puta. Evo da malo preformulisem njegov kod:

p = 0;
q = 1;
r = n;

while ( q <= n ) q <<= 2;

while ( q != 1 )
{
q >>= 2;
h = p-q;
p >>= 1;
if ( r >= h )
{
p += q;
r -= h;
}
}

Nisam probao da li ovo zaista radi, ali evo ti ideje :) Ovde cak nemas ni mnozenje...

Evo sad malo detaljnije, kako bi ja na primer to uradio... Ideja. Ti dobijas 12b broj sa A/D konvertora: 0-0FFF hex (sve na dalje pisem u hex). Ukoliko trazis koren iz 16b broja, taj koren ce ti biti 8b. Slicno, ukoliko trazis koren iz 32b broja, ti dobijas 16b koren. Da bi racun bio tacniji, hajde da tvoju "sumu kvadrata" predstavimo kao 32b broj. Dakle, jedan sempl 0-0FFF, njegov kvadrat je u opsegu 0 - 00FFE001; "suma kvadrata" je dakle 0 - 01FFC002. Gornjih 16b (0-01FF) mozes da iskoristis kao indeks u 16b look-up (LUT) tabelu od 512 semplova korenova. Ukoliko ti nije to dosta, siftujes "sumu kvadrata" za jedan u levo (0-03FF8004) i dobijes indeks za LUT od 1024 semplova, itd. LUT naravno ide u flash memoriju... Sto se tice tacnosti, to vec moras da bacis na papir, ili na primer da simuliras u MATLAB-u. Ako se ipak to pokaze kao nedovoljno tacno (odnosno da bi LUT za potrebnu tacnost bila velika) onda se bacis na racun. Mislim da je ovo najbrze... Sa druge strane, ako ti brzina izracunavanja nije mnogo bitna onda radi proracun, stekas memoriju :) - nisi naveo koji su ti vremenski okviri.

Pozdrav,
Milan.

Odgovor na temu

zofr

Član broj: 126534
Poruke: 119
*.dynamic.sbb.rs.

+1 Profil

Re: Algoritan za korenovanje u asembleru

^{02.02.2009. u 21:35 - pre 185 meseci}

Suma kvadrata ce biti u opsegu 0 - 00FFE001 jer je suma zapravo filtritan niz vrednosti kvadrata kroz NF filter sa beskonacnim impulsnim odzivom sa granicnom frekvencijom 1 do 2Hz. Za izracunavanje korena linearnom interpolacijom trebala bi mi tabela od 256 x 2 bajta sto je 512 bajtova. To nije mnogo. Tabela bi bila otprilike ovako:

000000 : 0000
010000 : 0100
020000 : 016A
030000 : 01BB (196608 : 443)
040000 : 0200 (262144 : 512)
-
-
FB0000 : 0FD8
FC0000 : 0FE0
FD0000 : 0FE8
FE0000 : 0FF0
FF0000 : 0FF8

Vidi se da pri kraju tabele kriva postaje skoro linearna, i tu ce se interpolacijom dobiti tacne vrednosti. U zagradi na dva mesta su date decimalne vrednosi zbog primera koji sledi.

Na primer, ako je suma kvadrata 038765, sto je 231269 interpolacijom bi se dobilo:

512-443
--------------- * (231269-196608) + 443
263144-196608

sto je

69
-------- * 34661 + 443 = 467
65536

Dakle, jednostavno: pomnozi se 69 i 34661, od rezultata se odbiju 16 bita (uz naravno zaokruzenje) i tome doda 443. Medjutim 231269^0.5 je 480.9 ili celobrojno sa zaokruzenjem 481. Greska je 38 sto je 0.93% od pune skale. Ovo daje na displeju kao tacne samo 2 cifre ne racunajuci greske u analognom delu.

Naravno, mogu uzeti 3 tacke i napraviti kvadratnu interpolaciju, ali se bojim da bi tada vreme izracunavanja bilo uporedivo sa nekim algoritmom za izracunavanje kvadratnog korena.

Mozda neko zna bolji i brzi postupak za interpolaciju od ovog po kome sam ja racunao, neka se javi.

Pozdravljam sve ucesnike.

Odgovor na temu

zofr

Član broj: 126534
Poruke: 119
*.dynamic.sbb.rs.

+1 Profil

Re: Algoritan za korenovanje u asembleru

^{03.02.2009. u 23:41 - pre 185 meseci}

Ako nekog interesuje (a zbog neceg mi je utisak suprotan) proverio sam algoritam koji je prezentovao korak: za najveci broj 00FFE001 koren je izracunao za 3835 ciklusa (192us), a potrocio je 216 bajta koda. Tacnost je bila do pislednjeg bita, dakle bez greske. Mozda se moze napisati i malo stedljivije, ali jos nisam toliko vican sa Freescale mikrokontrolerima.

Ako nekom treba slobodno moze da koristi taj algoritam. Mrzi me da ga napisem za PIC, bas sam znatizeljan koji bi rezultat bio. AVR bi mozda to brze uradio, ne znam.

Pozdrav.

Odgovor na temu