Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Jak zastąpić pierwiastkowanie [C]

Fredy 20 Sie 2011 20:02 2324 16
  • #1 20 Sie 2011 20:02
    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ę?

    0 16
  • Pomocny post
    #3 20 Sie 2011 20:09
    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.

    0
  • #4 20 Sie 2011 21:05
    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ę

    0
  • #6 20 Sie 2011 22:39
    __Grzegorz__
    Poziom 27  

    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...

    0
  • #7 20 Sie 2011 23:02
    drzasiek
    Specjalista - Mikrokontrolery

    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.

    0
  • #8 20 Sie 2011 23:34
    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.

    0
  • #9 21 Sie 2011 10:29
    94075
    Użytkownik usunął konto  
  • #11 22 Sie 2011 12:45
    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.

    0
  • #12 22 Sie 2011 13:18
    rajszym
    Poziom 20  

    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.

    0
  • #13 23 Sie 2011 07:53
    kubus_puchatek
    Poziom 17  

    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.

    0
  • #14 23 Sie 2011 08:04
    jarekz_2
    Poziom 15  

    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)

    0
  • #15 23 Sie 2011 22:40
    pburczyn
    Poziom 12  

    Proponuje coś takiego:


    Kod: c
    Zaloguj się, aby zobaczyć kod


    PB

    0
  • #16 24 Sie 2011 07:40
    94075
    Użytkownik usunął konto  
  • #17 24 Sie 2011 08:41
    jarekz_2
    Poziom 15  

    pburczyn napisał:
    Proponuje coś takiego(...)

    A może taki, nieco szybszy wariant tego algorytmu:
    Code:
    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.

    0