logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Jak zastąpić pierwiastkowanie [C]

Fredy 20 Sie 2011 20:02 3041 16
REKLAMA
  • #1 9844956
    Fredy
    Poziom 27  
    Witam;

    muszę obliczyć wzór D=sqrt (x*x + y*y) ;
    Użycie funkcji sqrt kosztuje mnie około 1KB.
    Tymczasem nie potrzebuje aż takiej dokładności, wystarczyłaby mi dokładność na poziomie 10% - 15%.

    Czy można jakimś prostym szeregiem zastąpić tą ciężką funkcję?
  • REKLAMA
  • Pomocny post
    #2 9844959
    gaskoin
    Poziom 38  
    Możesz funkcję pierwiastkowania rozwinąć w szereg Taylora, w okół punktu np 9:

    http://pl.wikipedia.org/wiki/Wz%C3%B3r_Taylora

    Bierzesz tyle wyrazów rozwinięcia w zależności od dokładności jaką potrzebujesz.
  • Pomocny post
    #3 9844976
    snnaap
    Poziom 25  
    Jeżeli nie zależy ci na wielkiej dokładności to można to zastąpić mnożeniem i pętlą.
    Jeżeli to co w nawiasach czyli (x*x+y*y) nazwiemy zmienną pod_pierwiastkiem to robimy to w taki sposób że bierzemy liczbę pomocniczą tmp i podnosimy ją do kwadratu sprawdzając czy wynik jest większy od zmiennej pod_pierwiastkiem.
    Dla przykładu
    zaczynamy od tmp = 1, sprawdzamy czy pod_pierwiastkiem>tmp*tmp jeżeli nie zwiększamy tmp o 1 i tak w kółko aż do spełnienia warunku. Teraz Od ciebie zależy o ile będziesz zwiększał zmienną tmp - to będzie twoja dokładnośc.
  • #4 9845178
    Fredy
    Poziom 27  
    snnaap napisał:
    Jeżeli nie zależy ci na wielkiej dokładności to można to zastąpić mnożeniem i pętlą.


    dokładnie o to mi chodziło.
    Dziekuję
  • REKLAMA
  • #6 9845609
    __Grzegorz__
    Poziom 30  
    Chcesz szybko, łatwo, i w miarę dokładnie?
    Proszę:
    http://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm

    Standard w DSP gdy chodzi o dużą wydajność przy zachowanej sporej dokładności.
    Przypomnę tylko, że wartości alfa i beta nie są przypadkowe (szybkie shifty )

    dokładność ~12% osiągniesz licząc sumę wartości bezwzględnej mniejszej z obu i połowy wartości bezwzględnej większej...

    Prościej się nie da...
  • #7 9845719
    drzasiek
    Specjalista CNC
    snnaap napisał:

    Dla przykładu
    zaczynamy od tmp = 1, sprawdzamy czy pod_pierwiastkiem>tmp*tmp jeżeli nie zwiększamy tmp o 1 i tak w kółko aż do spełnienia warunku. Teraz Od ciebie zależy o ile będziesz zwiększał zmienną tmp - to będzie twoja dokładnośc.


    A to można jeszcze udoskonalić, żeby działało szybciej dla większych liczb.
    Mianowicie zmienną tmp zmieniać wagowo, tak jak np w przetwornikach A/C.
  • #8 9845820
    snnaap
    Poziom 25  
    drzasiek napisał:
    snnaap napisał:

    Dla przykładu
    zaczynamy od tmp = 1, sprawdzamy czy pod_pierwiastkiem>tmp*tmp jeżeli nie zwiększamy tmp o 1 i tak w kółko aż do spełnienia warunku. Teraz Od ciebie zależy o ile będziesz zwiększał zmienną tmp - to będzie twoja dokładnośc.


    A to można jeszcze udoskonalić, żeby działało szybciej dla większych liczb.
    Mianowicie zmienną tmp zmieniać wagowo, tak jak np w przetwornikach A/C.


    Dokładnie, metoda wagowa na pewno będzie szybsza. Dla przykładu dla pierwiastka ze 100 zwiększanie co 1 daje rozwiązanie po 10 krokach natomiast stosując metodę wagową, przy tej samej dokładności, wynik mamy po 5 krokach - jeżeli dobrze liczę.
    Tylko że program będzie troszkę większy, ale na pewno nie będzie miał 1K.
  • #9 9846363
    Konto nie istnieje
    Konto nie istnieje  
  • REKLAMA
  • #11 9850163
    Fredy
    Poziom 27  
    Nie potrzebuje dużej dokładności, więc metoda z pętlą jest najlepsza. Tym bardziej że chcę ominąć liczby zmiennoprzecikowe.
  • #12 9850270
    rajszym
    Poziom 21  
    Przy zastosowaniu liczb całkowitych: D = max(x,y) + (min(x,y) + 2) / 4. Tak wynika z linku, który podał __Grzegorz__. Jedno działanie!!! Prościej się nie da.
  • #13 9853102
    kubus_puchatek
    Poziom 18  
    Panowie zanim dacie poradę pierwsze pytanie to typ danej jest ważny.
    drugie pytanie to typ kontrolera.
    biblioteka nie wykorzystuje wbudowanych instrukcji mnożenia w AVR nawet jak jest taki mnemonik w danym procu. może prościej będzie napisać funkcję która używa te rozkazy. będzie i szybko i małe.
  • REKLAMA
  • #14 9853116
    jarekz_2
    Poziom 16  
    Fredy napisał:
    (...)muszę obliczyć wzór D=sqrt (x*x + y*y) ; Użycie funkcji sqrt kosztuje mnie około 1KB. Tymczasem nie potrzebuje aż takiej dokładności, wystarczyłaby mi dokładność na poziomie 10% - 15%(...)

    Czy przypadkiem nie chodzi o amplitudy widma po przekształceniu Fouriera? Jeśli tak, to może da się w ogóle zrezygnować z pierwiastkowania? Zwłaszcza jeśli wyniki - amplitudy prążków widma - mają być przeliczone na decybele. Wynika to z tożsamości:
    20 log(sqrt(Re*Re+Im*Im)) = 10 log(Re*Re+Im*Im)
  • #15 9856019
    pburczyn
    Poziom 12  
    Proponuje coś takiego:


    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    PB
  • #16 9856612
    Konto nie istnieje
    Konto nie istnieje  
  • #17 9856696
    jarekz_2
    Poziom 16  
    pburczyn napisał:
    Proponuje coś takiego(...)

    A może taki, nieco szybszy wariant tego algorytmu:
    typedef	unsigned short	WORD;
    typedef	unsigned long		DWORD;
    
    WORD FastSqrt(DWORD d)
    {
    	WORD	r = 0;
    	WORD	m;
    
    	for ( m=0x8000; m!=0; m>>=1 )
    	{
    		DWORD	rr;
    
    		r += m;
    		rr = (DWORD)r * (DWORD)r;
    		if ( rr == d ) break;
    		if ( rr > d ) r -= m;
    	}
    	return r;
    }

    Argument: 32-bitowy bez znaku. Wynik: 16-bitowy bez znaku. Obliczenia wykonują się w 1...16 krokach.
REKLAMA