Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
09.08.2006, 13:48 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

Hallo,

wie kann ihc am geschicktesten ohne Fliesskommaberechnungen die nächsthöhere Quadratzahl einer Zahl berechnen?

also z.b

63 -> 64
4 -> 4
13 -> 16
5 -> 16
65 -> 128

usw.

ein

C++:

unsigned int t = 2;
while(true)
{
    if(t >= n)
        return t;
    t *= 2;
}

ist halt nicht gerade performant.
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
09.08.2006, 14:01 Uhr
virtual
Sexiest Bit alive
(Operator)

Was denn nun?
Quadratzahl oder was Dein Algorithmus macht, also die nächst höhere zweierpotenz?
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
09.08.2006, 14:06 Uhr
~Blubber2063
Gast

Gute Frage, also wenn du die Funktion mehrfach brauchst dürfte es halbwegs performant sein, die Quadratzahlen bis zu einem benötigten Punkt zu errechnen und in einem Container zu lagern und sich dann durch den Container hangeln, bis du das richtige gefunden hast. Gibt bestimmt bessere Lösungen ist aber was mir auf die schnelle so eingefallen ist.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
09.08.2006, 14:32 Uhr
ao

(Operator)

Ich denke, die Berechnung ist dermaßen schnell, dass eine Speicherung in einem Container nicht lohnt. Das Absuchen des Containers braucht genau so lange, schätze ich.

C++:

unsigned GetNextPowerOfTwo (unsigned n)
{
    unsigned p = 1;

    // p verdoppeln, solange es kleiner ist als n
    while (p < n)
        p *= 2;

    // wenn man hier ankommt, ist p mindestens gleich n.
    return p;
}

Ist fast FloSofts Ansatz, nur ohne Endlosschleife und Ausstieg über if.

ao

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
09.08.2006, 14:36 Uhr
kronos
Quotenfisch
(Operator)

Bearbeitung:

Bezieht sich auf die prosaische Problembeschreibung, wo es um Quadratzahlen geht.

Spontan:

C++:

unsigned nächsthöchstequadratzahl(unsigned t)
{
for(int i=r=0;r<t;r+=(i++*2+1));
return r;
}

Bei höheren Zahlen lohnt sich memoization sicher, da du dir ja immer den kompletten r-t-offset merken kannst...
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 09.08.2006 um 14:38 Uhr von kronos editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
09.08.2006, 15:21 Uhr
Bruder Leif
dances with systems
(Operator)

Wenn man von 32Bit-Integerwerten ausgeht, sind eh maximal 32 Werte zu durchsuchen (ausgehend vom Wunsch nach Zweierpotenzen), ein vordefiniertes Array wäre also recht schnell durch. Reicht das nicht?
Bei Quadratzahlen sieht die Sache natürlich etwas anders aus...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
09.08.2006, 16:14 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

ähm sorry natürlich nächsthöhere 2er potenz (wie zum teufel komm ich auf quadratzahl?)
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
09.08.2006, 17:20 Uhr
0xdeadbeef
Gott
(Operator)

Binäre Suche auf dem Bitmuster. Speziell für große Zahlen sollte dieser Ansatz schneller sein. Skaliert logarithmisch mit der Breite des Datentyps, verlässt sich aber darauf, dass der Datentyp eine Potenz von 2 bit breit ist.

C++:

#include <stdio.h>
#include <limits.h>

unsigned np2(unsigned x) {
  unsigned sp = UINT_MAX << sizeof(unsigned) * 4;
  size_t ps = sizeof(unsigned) * 4;

  if(x == 0) return 1;

  do {
    if(x & sp) {
      ps >>= 1;
      sp &= sp << ps;
    } else {
      sp >>= ps;
    }
  } while(ps > 0);

  return (x & sp) << 1;
}

int main(void) {
  int i;
  for(i = 0; i < 256; ++i) {
    printf("%d: %u\n", i, np2(i));
  }
  return 0;
}

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 09.08.2006 um 17:22 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: