Zahlenfresser

Algorithmus zur schnellen Berechnung von Kubikwurz Gast #3880702
Lesenswert?
• ▲
▼ 
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?
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
ich Gast #3880731
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Jürgen S. #3880774
Lesenswert?
• ▲
▼ 
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:
1
int icbrt2(unsigned x) {

2
   int s;

3
   unsigned y, b, y2;

4


5
   y2 = 0;

6
   y = 0;

7
   for (s = 30; s >= 0; s = s - 3) {

8
      y2 = 4*y2;

9
      y = 2*y;

10
      b = (3*(y2 + y) + 1) << s;

11
      if (x >= b) {

12
         x = x - b;

13
         y2 = y2 + 2*y + 1;

14
         y = y + 1;

15
      }

16
   }

17
   return y;

18
}


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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
c-hater Gast #3880888
Lesenswert?
• ▲
▼ 
Jürgen S. schrieb:

> Also ich habe nur Google, und der findet z.B. als Algorithmus in C:
>
1
> int icbrt2(unsigned x) {

2
>    int s;

3
>    unsigned y, b, y2;

4
> 

5
>    y2 = 0;

6
>    y = 0;

7
>    for (s = 30; s >= 0; s = s - 3) {

8
>       y2 = 4*y2;

9
>       y = 2*y;

10
>       b = (3*(y2 + y) + 1) << s;

11
>       if (x >= b) {

12
>          x = x - b;

13
>          y2 = y2 + 2*y + 1;

14
>          y = y + 1;

15
>       }

16
>    }

17
>    return y;

18
> }

19
>


> 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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Marc V. (Firma: Vescomp) #3880968
Lesenswert?
• ▲
▼ 
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.
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