Betragsberechnung eines Vectors in C, am16

[Micha S. (e-tec)]

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:

betrag  = ( (adc.raw_data[0]-X_OFFSET) * (adc.raw_data[0]-X_OFFSET) );
betrag += ( (adc.raw_data[1]-Y_OFFSET) * (adc.raw_data[1]-Y_OFFSET) );
betrag += ( (adc.raw_data[2]-Z_OFFSET) * (adc.raw_data[2]-Z_OFFSET) );
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)

[Jannis C. (kabelwurm)]

Doppelt

[Micha S. (e-tec)]

schon gesehen & gelöscht ;)

[hp-freund (Gast)]

http://elm-chan.org/docs/avrlib/sqrt32.S

[Micha S. (e-tec)]

Schön :) gibts das auch in c oder muss ihc unbedingt den asm code 
einbinden?

[DirkB (Gast)]

Micha S. schrieb:
> kann ich die sqrt() funktion irgendwie umgehen?

Was machst du denn mit dem Betzrag.
Wenn du die nur vergleichen willst, brauchst du die Wurzel nicht ziehen.

[Micha S. (e-tec)]

schon klar :) naja eig. würde es mit ein paar tricks auch so gehen, 
danach den wert skalieren und gut. ich werte einen beschleunigungssensor 
aus, der betrag ist die resultierende kraft (im stand die erdanz.)

[hp-freund (Gast)]

Micha S. schrieb:
> Schön :) gibts das auch in c oder muss ihc unbedingt den asm code
> einbinden?

So schwer ist das nicht. Habe es gerade mal probiert:

http://www.mikrocontroller.net/articles/AVR-GCC-Tutorial/Assembler_und_Inline-Assembler#Assembler-Dateien

Lässt sich compilieren, ob das Ergebnis stimmt weiß ich allerdings nicht 
:-)

[Micha S. (e-tec)]

genau, und um zu wissen ob es stimmt müsste ich den befehlssatz von 
meinem kleinen lernen (zu faul...:)
aber ichg werde es mal bei gelegenheit einbinden und testen (wobei mir 
da schon mal beim durchschauen push & pop fehlen)

[Ralf (Gast)]

Hallo,

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

uint32 Sqrt(uint32 ulRadicand)
{
   uint32 ulRem  = 0;
   uint32 ulRoot = 0;
   int32  slIdx;
   for (slIdx = 0; slIdx < 16; slIdx++)
   {
      ulRoot     <<= 1;
      ulRem        = ((ulRem << 2) + (ulRadicand >> 30));
      ulRadicand <<= 2;
      ulRoot++;
      if (ulRoot <= ulRem)
      {
         ulRem -= ulRoot;
         ulRoot++;
      }
      else
      {
         ulRoot--;
      }
   }
   return (ulRoot >> 1);
}

Gruß,
Ralf

[Johann L. (gjlayde)]

32-Bit Quadratwurzel für avr-gcc gibt's in AVR Arithmetik: Wurzel.

[Micha S. (e-tec)]

Sehr schön, danke. hab mir sowas ähnliches gestern bereits selber 
geschrieben:

ui16 int_sqrt(ui32 zahl)
{
   ui16 wurzel = UI16MAX ;
   ui16 temp   = wurzel-1;
   while ( temp < wurzel ) 
   {
      wurzel = temp;
      temp   = wurzel + zahl/wurzel >> 1;
   }
   return wurzel;
}

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

[Karl H. (kbuchegg)]

Ralf's Version dürfte grob geschätzt um mindstens den Faktor 20 bis 30 
schneller sein als deine Newton Iteration.

[Arthur Dent (Gast)]

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!

[Ralf G. (ralg)]

DirkB schrieb:
> Micha S. schrieb:
>> kann ich die sqrt() funktion irgendwie umgehen?
>
> Was machst du denn mit dem Betzrag.
> Wenn du die nur vergleichen willst, brauchst du die Wurzel nicht ziehen.

Ich würde auch lieber diese Variante nehmen.

[Micha S. (e-tec)]

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.

[Karl H. (kbuchegg)]

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

[Ralf (Gast)]

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

[Micha S. (e-tec)]

Ja da hast du recht, ich denke ich werde den ralfs code ncoh ein wenig 
für den avr optimieren und bei interesse posten!

Grüße & herzlichst Dankeschön