Zahlenfresser

Algorithmus zur schnellen Berechnung von Kubikwurz Gast #3880702 
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 Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
ich Gast #3880731 
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 Melden Danke
Jürgen S. #3880774 
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 Melden Danke
c-hater Gast #3880888 
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 Melden Danke
Marc V. (Firma: Vescomp) #3880968 
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 Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 11 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.