Wurzel aus 32 bit Zahl - Speicherverbrauch

[pegy (Gast)]

Möchte die Entfernung (C) von zwei Punkten (Koordinaten) berechnen. Dazu 
verwende ich den Satz von Pythagoras (mit Strecke A und B) also A² + B² 
= C². A und B sind Variablen vom Typ unsigned long (32 bit). Das Problem 
ist die Wurzel aus C, das verbraucht zu viel Speicher für mein Programm!

In meinem Code verwende ich für die Wurzel sqrt() (mit #include math.h). 
Diese Operation verbraucht jedoch 3164 Byte im Flash und 264 Byte im 
SRAM. Ich verwende den Atmega8.

Hat jemand eine Idee, ob ich das Wurzelziehen umgehen kann? Oder wie 
könnte man mit geringerem Speicheraufwand die Wurzel ziehen? Gibt es da 
bessere Funktionen?

Bin für alle Tips dankbar!

[Sam .. (sam1994)]

Wenn die Entfernung nur intern verrechnet werden soll, kann man auch mit 
der quadrierten Summe weiterrechnen. Man muss nur alles andere auch 
quadrieren.

[pegy (Gast)]

Nein, das Ergebnis soll auf einem LCD ausgegeben werden...

[Dennis H. (c-logic)]

http://www.mikrocontroller.net/articles/AVR_Arithmetik#avr-gcc_Implementierung_.2832_Bit.29

[pegy (Gast)]

Danke! Die Funktionen sind super ;-)

[Wurzelsepp (Gast)]

pegy,

ich habe das mal in Java (J2ME) gemacht. Wenn Du willst, kannst Du es 
nach C portieren. Der Code implemetiert das Newton-Verfahren und sollte 
recht ressourcenschonend sein. Kannst ja zurückmelden, wieviel RAM/ROM 
verbraucht wurde.

In J2ME ist "long" vom Typ sint32. Vermutlich willst Du in C den Typ 
uint32 verwenden.

Viel Erfolg!

public static long qwurzel(long qzahl)
{//Berechnung der Quadratwurzel mit Newton-Verfahren:
 //f(x) = x² – qzahl, d.h.: ret_qwurzel² - qzahl
 //f'(x) = 2x,     d.h.: 2*ret_qwurzel
 //Xn+1 = Xn – (f(x) / f'(x))
 //d.h.: ret_qwurzel n+1 = ret_qwurzel n - ((ret_qwurzeln² - 
qzahl)/(2*ret_qwurzeln))
 //d.h.: ret_qwurzel n+1 = ((ret_qwurzeln² + qzahl)/(2*ret_qwurzeln))
 // Startwert X0 = qzahl/2, funktioniert für alle Werte von 1 aufwärts
 // Iteration solange bis Xn+1 == Xn

  long ret_qwurzel, ret_qwurzel_alt; //long in Java entspricht sint32 in 
C

  if (qzahl < 1)
  {// kann man weglassen im Fall uint32
    return ret_qwurzel = 0;
  }
  else if (qzahl < 4) //ist eh alles 1...
  {
    return ret_qwurzel = 1;
  }

  ret_qwurzel = ret_qwurzel_alt = qzahl>>1;

  while (true)
  {
    ret_qwurzel += (qzahl/ret_qwurzel_alt);
    ret_qwurzel >>= 1;
    if (ret_qwurzel_alt-ret_qwurzel <= 1)
    {
      break;
    }
    ret_qwurzel_alt = ret_qwurzel;
  }
  return ret_qwurzel;
}