Fun-Soft - Programmierforum

Autor

Thread - Seiten: [ 1 ] [ 2 ] > 3 <

020
09.07.2004, 21:46 Uhr
0xdeadbeef
Gott
(Operator)

Ich krieg mit NemoEimis Lösung:

shell:

real    0m16.672s
user    0m15.279s
sys     0m0.019s

Und ich muss auch zugeben, dass das ne ziemlich schöne Lösung ist. Gefällt mir, auch wenn ich aus Gewohnheit Präinkrements und >>= genommen hätte, für den Fall, dass das mal jemand mit der GMP machen will oder so. Also:

C++:

unsigned ceil_ld(unsigned n) {
  unsigned z = 1;
  int twopow = 1; /* So gehts auch in C */

  while(n ^ 1) {
    if (n&1) twopow = 0;
    n >>= 1;
    ++z;
  }
  z -= twopow;

  return z;
}

Bearbeitung:

Hups, mein neuer Ansatz war so nicht ganz korrekt...*hust*

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

Dieser Post wurde am 09.07.2004 um 21:59 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

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

021
09.07.2004, 21:49 Uhr
NemoEimi

Guguck,

eben habe ich nochmal einen anderen Ansatz probiert

C++:

unsigned ceil_rec(unsigned n, unsigned low, unsigned high, unsigned test) {
  unsigned k = n >> test;
  if (k==1) {
    unsigned tp = 1 << test;
    if (tp == n) return(test); else return(test+1);
    }
  if (k) return(ceil_rec(n, test, high, (test+high) >> 1)); else
         return(ceil_rec(n, low, test, (test+low) >> 1));}

unsigned ceil_ld2(unsigned n) {
  return(ceil_rec(n, 0, 32, 16));
  }

Meine main zum benchen sieht nun so aus:

C++:

int main() {
  unsigned i; unsigned chksum = 0;
  for(i = 1; i < 100000000L; ++i) chksum+=ceil_ld2(i);
  cout << "Fertig. Summe: " << chksum << endl;
  return 0;
}

Compiliert habe ich alles mit

C++:

g++ -O3 dateiname.cpp

Hier sind meine Ergebnisse:

beefys Lösung/meine erste Lösung ungefähr gleichauf:

Zitat:

Fertig. Summe: 2565782246

real 0m46.415s
user 0m43.851s
sys 0m0.016s

Meine zweite Lösung

Zitat:

Fertig. Summe: 2565782246

real 0m5.233s
user 0m4.990s
sys 0m0.002s

Grüße,
Nemo

Profil || Private Message || Suche

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

022
09.07.2004, 22:03 Uhr
0xdeadbeef
Gott
(Operator)

Du bist ein Bastard, weißt du das? OK, dagegen komm ich nicht mehr an.

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

Profil || Private Message || Suche

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

023
09.07.2004, 23:36 Uhr
NemoEimi

Huhu,

das Rätsel ist spassig. Ich habe nochmal eine template-Lösung probiert:

C++:

template<unsigned low, unsigned high, unsigned test>
unsigned ceil_temp(unsigned n) {
  unsigned k = n >> test;
  if (k == 1) {
    unsigned tp = 1 << test;
    if (tp == n) return(test); else return(test+1);
    }
  if (k) return(ceil_temp<test, high, (test+high) >> 1>(n)); else
         return(ceil_temp<low, test, (test+low) >> 1>(n));
     };

unsigned ceil_ld3(unsigned n) {
  return(ceil_temp<0, 32, 16>(n));
  }

aber die Performance ist leider lausig:

Zitat:

Fertig. Summe: 2565782246

real 0m6.533s
user 0m6.511s
sys 0m0.003s

und dann die tail-Rekursion aus meiner zweiten Lösung weggemacht stattdessen:

C++:

unsigned ceil_ld4(unsigned n) {
  unsigned low = 0; unsigned high = 32; unsigned test = 16;
  while(true) {
    unsigned k = n >> test;
    if (k == 1) {
      unsigned tp = 1 << test;
      if (tp == n) return(test); else return(test + 1);
      }
    if (k) low = test; else high = test;
    test = (high + low) >> 1;
    }
  }

was erwartungsgemäß noch Verbesserungen bringt:

Zitat:

Fertig. Summe: 2565782246

real 0m3.091s
user 0m3.080s
sys 0m0.003s

Ja... nett, was man bei so einer simplen Aufgabe an verschiedenen Sachen machen kann

.

Grüße,
Nemo

Profil || Private Message || Suche

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

024
10.07.2004, 11:47 Uhr
(un)wissender
Niveauwart

Ihr seid krass

.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

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

025
08.08.2004, 19:01 Uhr
0xdeadbeef
Gott
(Operator)

Ich kann zwar grad nicht benchen, weil ich keinen Compiler da hab, aber ich denke, dass das hier noch ein bisschen was rausholen dürfte (spart Vergleiche):

C++:

unsigned ceil_ld4(unsigned n) {
  unsigned low = 0;
  unsigned high = sizeof(unsigned) * 8;
  unsigned test = sizeof(unsigned) * 4;

  for(;;) {
    switch(n >> test) {
    case 1:
      return test + (1 << test != n)
    case 0:
      high = test;
    default:
      low = test;
    }
    test = (high + low) >> 1;
  }
}

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

Dieser Post wurde am 08.08.2004 um 19:04 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

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

026
03.09.2004, 22:42 Uhr
NemoEimi

Hallo,

bei mir ist das:

C++:

unsigned ceil_ld_beef(unsigned n) {
  unsigned low = 0;
  unsigned high = sizeof(unsigned) * 8;
  unsigned test = sizeof(unsigned) * 4;
  while(true) {
    switch(n >> test) {
    case 1:
      return test + (1 << test != n);
    case 0:
      high = test;
      break;
    default:
      low = test;
    }
    test = (high + low) >> 1;
  }
}

immer noch langsamer als meine letzte Lösung

Zitat:

Fertig. Summe: 2565782246

real 0m4.615s
user 0m4.298s
sys 0m0.009s

Aber, da dieser Thread jetzt ja weitergeht, habe ich mich eben auch noch einmal hingesetzt

C++:

unsigned ceil_ld4(unsigned n) {
  static unsigned start = 16;
  unsigned low = 0; unsigned high = 32; unsigned test = start;
  while(true) {
    unsigned k = n >> test;
    if (k == 1) {
      start = test;
      unsigned tp = 1 << test;
      if (tp == n) return(test); else return(test+1);
      }
    if (k) low = test; else high = test;
    test = (high + low) >> 1;
    }
  }

*hust, hust* und damit komme ich auf:

Zitat:

Fertig. Summe: 2565782246

real 0m1.766s
user 0m1.611s
sys 0m0.007s

Grüße,
Nemo

Dieser Post wurde am 03.09.2004 um 22:44 Uhr von NemoEimi editiert.

Profil || Private Message || Suche

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

027
26.10.2004, 13:46 Uhr
(un)wissender
Niveauwart

Was sagt ihr dazu? Habe mal ein wenig Asm getestet.
Läuft auf jeden x86-System.

Code:

powerOfTwo PROC input:DWORD
    mov edx, [esp + 4]
    xor eax, eax
    test edx, edx
    jz equal
    bsr eax, edx
    bsf ecx, edx
    xor ecx, eax
    jz equal
    add eax, 1
equal:
    ret 4
powerOfTwo ENDP

In C++ der Prototyp

C++:

extern "C" unsigned __stdcall powerOfTwo(unsigned);

Habe es zeitlich nicht gemessen, dürfte aber alles in den Schatten stellen.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

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

028
26.10.2004, 13:49 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

Zitat:

Was sagt ihr dazu?

Du hast nen Knall...weiter so

--
...fleißig wie zwei Weißbrote

Dieser Post wurde am 26.10.2004 um 13:49 Uhr von Windalf editiert.

Profil || Private Message || Suche

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

029
26.10.2004, 14:22 Uhr
(un)wissender
Niveauwart

In Asm kann man viel unsauberer coden als in C, wäre das nicht was für dich, Windalf?

@all
Tja, so kann man sich irren. VC++ inlined ceil_ld4 und damit ist es bei mir ca. doppelt so schnell wie powerOfTwo . Obwohl der Funktionsrumpf von powerOfTwo deutlich schneller ist, zieht der Funktionsaufruf soviel Overhead nach sich, dass das ganze nichts bringt, im Gegenteil.
Erstaunlich, was es kostet eine Funktion aufzurufen, das hätte ich nicht gedacht!

Na ja, eure ganzen Funktionen kommen mit 0 nicht klar, da gibt es eine Endlosschleife. Das sollte man vorher abfangen.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

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

Seiten: [ 1 ] [ 2 ] > 3 < [ Rätselecke ]

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: