Zahlenfresser

[Algorithmus zur schnellen Berechnung von Kubikwurz (Gast)]

Einen guten Tag an das Forum

Wie der Titel sagt suche ich einen Algorithmus mit dem ich möglichst 
schnell Kubikwurzeln berechnen kann. Als Prozessor soll ein Atmega 328 
oder vergleichbares mit Hardware-Multiplier verwendet und in Assembler 
programmiert werden.

Gegeben sind positive Ganzzahlen mit 32 Bit Länge, aufgeteilt in 4 
Register zu 8 Bit. Das Ergebnis soll auch wieder eine Ganzzahl sein und 
ein Flag angeben ob die Wurzel aufgeht oder ein Rest übrig blieb.

Mein bisheriger Ansatz ist die Sukzessive Approximation. Ich setze 
probeweise Bit 10 und multipliziere die Zahl zweimal mit sich selbst 
damit ich die dritte potenz habe. Dann vergleich ich mit der Zahl von 
der die Wurzel gezogen werden soll. Ist mein Zwischenergebnis zu groß 
lösche ich Bit 10 und setze Bit 9, ist es zu klein setze ich Bit 10 und 
9. Das ganze fortgesetzt bis Bit 1.

Wie ihr an meiner Sprache seht5 habe ich Programmieren nicht formell 
gelernt sondern arbeite mich mehr experimentell in das Thema ein.

Habt ihr Vorschläge für einen effizienteren Algorithmus oder 
leichtverständliche Quellen im Internet wo ich mich weiter einlesen 
kann?

[Dominik S. (dasd)]

> Wie der Titel sagt

Hallo "Algorithmus zur schnellen Berechnung von Kubikwurz",

was tut denn so ein Zahlenfresser-Algorithmus genau?

scnr

[Eric B. (beric)]

Ist ein guter Ansatz, würde ich auch so machen.
Nur würde ich nicht bis bit 1 fortsetzen sondern bis bit 0 ^_^

[ich (Gast)]

Hi
Ich würde erst mal das Lösungs intervall eingrenzen, da müsste es was zu 
fischen geben weil ja ein Produkt aus zwei n stelligen Zahlen eine 2n 
stellige Zahl gibt.
Also müsste ja beim Kubizieren: aus n Stellen 3 N werden (maximal) 
daraus müsste sich eine Schranke ableiten lassen.
Mfg
ich

[Winfried J. (Firma: Nisch-Aufzüge) (winne)]

http://de.wikipedia.org/wiki/Logarithmus

eine logarithmentabelle sollte hilfreich sein

[Sinus T. (micha_micha)]

Hat Xalu schon gemacht: Bischen suchen:
Beitrag "Re: Kubikwurzel bilden"

[Jürgen S. (jurs)]

Algorithmus zur schnellen Berechnung von Kubikwurz schrieb im Beitrag 
#3880702:
> Habt ihr Vorschläge für einen effizienteren Algorithmus oder
> leichtverständliche Quellen im Internet wo ich mich weiter einlesen
> kann?

Also ich habe nur Google, und der findet z.B. als Algorithmus in C:

int icbrt2(unsigned x) {
   int s;
   unsigned y, b, y2;

   y2 = 0;
   y = 0;
   for (s = 30; s >= 0; s = s - 3) {
      y2 = 4*y2;
      y = 2*y;
      b = (3*(y2 + y) + 1) << s;
      if (x >= b) {
         x = x - b;
         y2 = y2 + 2*y + 1;
         y = y + 1;
      }
   }
   return y;
}

Das scheint mit 16-Bit int gehau so wie mit 32-Bit int hinzuhauen. Ein 
Flag, ob die Kubikwurzel aufgeht, wird zwar nicht zurückgeliefert, aber 
die Info dürfte dann wohl am Ende in den Hilfsvariablen stehen.

[c-hater (Gast)]

Jürgen S. schrieb:

> Also ich habe nur Google, und der findet z.B. als Algorithmus in C:
>

> int icbrt2(unsigned x) {
>    int s;
>    unsigned y, b, y2;
> 
>    y2 = 0;
>    y = 0;
>    for (s = 30; s >= 0; s = s - 3) {
>       y2 = 4*y2;
>       y = 2*y;
>       b = (3*(y2 + y) + 1) << s;
>       if (x >= b) {
>          x = x - b;
>          y2 = y2 + 2*y + 1;
>          y = y + 1;
>       }
>    }
>    return y;
> }
>

> Das scheint mit 16-Bit int gehau so wie mit 32-Bit int hinzuhauen.

Bestimmt nicht. Es muß mindestens der Startwert von s angepaßt werden, 
das sieht man doch sofort.

[Johann L. (gjlayde)]

Jürgen S. schrieb:
> Also ich habe nur Google, und der findet z.B. als Algorithmus in C:

Yalus Implementierung ist da klar zu bevorzugen, auch wenn man erst nach 
C bzw. Assembler übersetzen muss.

[Yalu X. (yalu) (Moderator)]

Sinus Tangentus schrieb:
> Hat Xalu schon gemacht: Bischen suchen:
> Beitrag "Re: Kubikwurzel bilden"

Wobei man hier den HW-Multiplizierer – da sowieso vorhanden –
wahrscheinlich auch nutzen sollte.

[Marc V. (Firma: Vescomp) (logarithmus)]

Algorithmus zur schnellen Berechnung von Kubikwurz schrieb im Beitrag 
#3880702:
> Gegeben sind positive Ganzzahlen mit 32 Bit Länge, aufgeteilt in 4
> Register zu 8 Bit. Das Ergebnis soll auch wieder eine Ganzzahl sein und
> ein Flag angeben ob die Wurzel aufgeht oder ein Rest übrig blieb.

 Ist doch OK so.
 Wenn 4 Register, dann vielleicht nur vorher jedes einzelne Register
 auf > 0 prüfen, je nach Zustand Startbit der gesetzt wird nach rechts
 schieben. Kann sich bei kleineren Zahlen als nützlich erweisen, z.B.
 bei Reg0 bis Reg3 braucht bei Reg3 = Reg2 = 0 Startwert nicht grosser
 als 40 zu sein. Das sind schon 5 bits nach rechts.
 Mit einer entsprechenden Tabelle liesse sich das Ganze sogar richtig
 optimieren.