Betragsberechnung eines Vectors in C, am16

Micha S. #2368326
Lesenswert?
• ▲
▼ 
Betragsberechnung eines Vectors in C
====================================

Guten Abend!!

Hab mal eine kleine Frage.
Ich möchte in C den Betrag eines 3D Vectors berechnen, über phythagoras.
Betrag(bzw Länge) x = Wurzel aus der Summe der Quadrate.

Nun muss man ja gezwungenermassen mit potenzen rechnen, bzw mit 
funktionen die diese berechnen. (sqrt/pow)

Kann man das nicht irgendwie umgehen? normalerweise sagt man ja X^2 = 
x*x oder pow(x, 2) oder sqr(x)

ich würde gerne auf die bibliotheksfunktionen komplett verzichten.
das quadrat am liebsten so x = x^2; (ich weiß der "^" ist eigentlich der 
Xor op) und ebenso die quadratwurzel mit x = x^(1/2)  (werde ich vorher 
noch mit 1000 multiplizieren, da ich die berechnung in int durchführen 
möchte.)

momentan sieht die berechnung so aus:

1
betrag  = ( (adc.raw_data[0]-X_OFFSET) * (adc.raw_data[0]-X_OFFSET) );

2
betrag += ( (adc.raw_data[1]-Y_OFFSET) * (adc.raw_data[1]-Y_OFFSET) );

3
betrag += ( (adc.raw_data[2]-Z_OFFSET) * (adc.raw_data[2]-Z_OFFSET) );

4
betrag  = (ui16) sqrt(betrag);


kann ich die sqrt() funktion irgendwie umgehen?
Grund ist folgender (mit sqrt):

AVR Memory Usage
    ----------------
    Device: atmega16
    Program:    6878 bytes (42.0% Full)
    (.text + .data + .bootloader)
    Data:        676 bytes (66.0% Full)

und ohne, der grund liegt klar auf der hand...

AVR Memory Usage
    ----------------
    Device: atmega16
    Program:    3776 bytes (23.0% Full)
    (.text + .data + .bootloader)
    Data:        412 bytes (40.2% Full)
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Ralf Gast #2369194
Lesenswert?
• ▲
▼ 
Hallo,

habe mal den folgenden Code von Jack Crenshaw (Embedded Math Toolkit) 
verwendet:

1
uint32 Sqrt(uint32 ulRadicand)

2
{

3
   uint32 ulRem  = 0;

4
   uint32 ulRoot = 0;

5
   int32  slIdx;

6
   for (slIdx = 0; slIdx < 16; slIdx++)

7
   {

8
      ulRoot     <<= 1;

9
      ulRem        = ((ulRem << 2) + (ulRadicand >> 30));

10
      ulRadicand <<= 2;

11
      ulRoot++;

12
      if (ulRoot <= ulRem)

13
      {

14
         ulRem -= ulRoot;

15
         ulRoot++;

16
      }

17
      else

18
      {

19
         ulRoot--;

20
      }

21
   }

22
   return (ulRoot >> 1);

23
}


Gruß,
Ralf
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Micha S. #2370029
Lesenswert?
• ▲
▼ 
Sehr schön, danke. hab mir sowas ähnliches gestern bereits selber 
geschrieben:

1
ui16 int_sqrt(ui32 zahl)

2
{

3
   ui16 wurzel = UI16MAX ;

4
   ui16 temp   = wurzel-1;

5
   while ( temp < wurzel ) 

6
   {

7
      wurzel = temp;

8
      temp   = wurzel + zahl/wurzel >> 1;

9
   }

10
   return wurzel;

11
}


funktioniert sehr gut, aber wie man auf den ersten blick sieht werden 
die nachkommastellen nicht berücksichtigt, die funktion eignet sich 
somit mehr für größere zahlen. lt. der funktion ist:
wurzel 4 = wurzel aus 5...8, nämlich 2.

man könnte sie, wenn nötig natürlich noch mit dem modulo erweitern...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Arthur Dent Gast #2370129
Lesenswert?
• ▲
▼ 
Um die Auflösung zu erhöhen eignet sich die Fixed-Point-Arithmetic, 
dabei verschiebst du quasi das Komma um ein bestimmtes Vielfaches von 
zwei und erhälts so Nachkommastellen. Ein Vielfaches von 2 deshalb, weil 
es sich mit Bit-Shift-Operationen realisieren lässt.

Viel Erfolg!
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Micha S. #2370238
Lesenswert?
• ▲
▼ 
Karl Heinz Buchegger schrieb:
> Ralf's Version dürfte grob geschätzt um mindstens den Faktor 20 bis 30
> schneller sein als deine Newton Iteration.

Guten morgen, na heute besser gelaunt? ;-)
Ja das ist klar, das ist abhängig von der zahl, je größer desto mehr 
durchläufe & somit langsamer. Mir ging es ja, wie gestern erwähnt, 
hauptsächlich darum die fliesskommaarithmetik zu umgehen, was mir auch 
erst mal gelungen ist. nächstes kriterium war dann der Speicherbedarf, 
deswegen die entscheidung zur Newtonschen Iteration.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #2370345
Lesenswert?
• ▲
▼ 
Micha S. schrieb:

> erst mal gelungen ist. nächstes kriterium war dann der Speicherbedarf,
> deswegen die entscheidung zur Newtonschen Iteration.

Gut.
Das ist jetzt in Ralfs Code noch nicht optimal gelöst. sIdx muss keine 
32 Bit Variable sein und ob die anderen beiden 32 BIt sein müssen, 
müsste man analysieren. Auch der Return Datentyp muss kein 32 Bit Typ 
sein, 16 Bit reichen. Aber abgesehen von den paar Bytes auf dem Stack 
trägt sein Code auch höchst wahrscheinlich weniger auf, als die Division 
in deinem Code, die das eigentliche Übel darstellt. AVR können nur 
schlecht allgemein dividieren. Von daher ist so gut wie jeder Code, der 
keine derartige Division braucht immer besser. Und von der Länge des 
C-Codes in Source Form solltest du dich nicht blenden lassen
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Ralf Gast #2370393
Lesenswert?
• ▲
▼ 
Karl Heinz Buchegger schrieb:
> Das ist jetzt in Ralfs Code noch nicht optimal gelöst. sIdx muss keine
>
> 32 Bit Variable sein und ob die anderen beiden 32 BIt sein müssen,
>
> müsste man analysieren. Auch der Return Datentyp muss kein 32 Bit Typ
>
> sein, 16 Bit reichen.

Was ich bei meinem Code noch dazu sagen muss ist, dass ich den Code auf 
einem STM32 laufen habe. Aus diesem Grund sind meine Variablen 32Bit 
breit damit ich mir irgendwelche Extension Befehle im Assembler sparen 
kann.
Bei einer Umsetzung auf einem AVR sollte man, wie Karl Heinz schon 
geschrieben hat, die Datenformate noch ein wenig für den AVR anpassen.
Gruß,
Ralf
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren