Von n auf die nächst größere 2er Potenz

Vielleicht stehe ich ja gerade auf dem Schlauch, aber was ist falsch an borgs Lösung? Ich würde auch den Zweierlogarithmus nehmen, aufrunden, und wieder 2 hoch vorheriges Ergebnis rechnen. Sollte doch wesentlich schneller sein als alle Schleifen, oder?

Blue-Tiger

Sven25 @logged off schrieb:

Vielleicht stehe ich ja gerade auf dem Schlauch, aber was ist falsch an borgs Lösung? Ich würde auch den Zweierlogarithmus nehmen, aufrunden, und wieder 2 hoch vorheriges Ergebnis rechnen. Sollte doch wesentlich schneller sein als alle Schleifen, oder?

Wer sagt dir denn, das log() intern ohne Schleife auskommt? Die schnellste Loesung ist sicher die template-Loesungen von hustbaer, die aber nur funktioniert wenn das Argument bereits zur Compilezeit feststeht.
Wenn das nicht geht, ist die von Undertaker die schnellste, da sie ohne Schleife, ohne Runden, etc. auskommt. Andere sehr schnelle Loesungen gaebs noch auf der Seite, deren Link ich vorhin gepostet hab, nur leider ist die grad offline. Aber die "naive"-Methode ueber den 2er Logarithmus wahrscheinlich die langsamste.

EDIT: hier nochmal ein Link der auch funktioniert: http://www.cs.utk.edu/~vose/c-stuff/bithacks.html#RoundUpPowerOf2

CStoll

Ja, der Logarithmus-Ansatz hat (vermutlich) konstante Laufzeit - aber er verwendet Gleitkomma-Arithmetik und die ist meist um einiges langsamer als Ganzzahl-Arithmetik.

(womit wir beim Grundproblem der Komplexitätstheorie sind: O(1) ist "besser" als O(log n), zumindest für große Werte von n. Bei relativ kleinen Werten mußt du dir die Laufzeit genauer ansehen, um zu entscheiden - und da ist 10s (liegt in O(1)) natürlich schlechter als 1ms*log₂n (O(log n) (zumindest für n<10³⁰⁰⁰))

hustbaer

camper schrieb:

.filmor: da fehlt eine Abbruchbedingung, Templates werden auch (noch) instantiiert, wenn sie wegen des ?: Operators eigentlich nicht gebraucht werden.
template <unsigned N> struct next_pow2 { static const unsigned value = 2 * next_pow2< ( N + 1 ) / 2 >::value; };
template <> struct next_pow2<1> { static const unsigned value = 1; };
template <> struct next_pow2<0> { static const unsigned value = 1; };

Hehe, ok, das IST eleganter
(und erzeugt vermutlich auch viel weniger instanzierte Templates, was auch gut ist)
Und geht vermutlich auch nocht mit dem ollen VC6 der ja keine partielle Spezialisierungs-Ding kann - müsste man nur den "static const" genen ein enum tauschen...

@Blue-Tiger: dein Link ist 403...

----

BTW: logarithmus und Gleitkomme und co: das ist Pfui! weil man gefälligst nicht mit Gleitkomme rechnet wenn man genaue Ergebnisse braucht

Hallo

wieso ist eine halbseitige Template-Sequenz elegant, wenn es auch eine
4-buchstabige Formel tut?

Eleganz ist Einfachheit im Verein mit Allgemeingültigkeit.

Gruß

CStoll

kleine Bemerkung schrieb:

wieso ist eine halbseitige Template-Sequenz elegant, wenn es auch eine
4-buchstabige Formel tut?

Erstens ist die letzte Template-Version nur drei Zeilen lang und zweitens ist die Formel zwar wunderbar geeignet, die Lösung mathematisch zu erfassen - die Frage ist jedoch, wie diese Formel technisch umgesetzt werden sollte.

Hallo

so vielleicht?:

exp(log(2)*ceil(log(n)/log(2)))

nicht schnell, aber elegant.

Gruß

CStoll

kleine Bemerkung schrieb:

Hallo

so vielleicht?:
exp(log(2)*ceil(log(n)/log(2)))
nicht schnell, aber elegant.

Und auch nicht sonderlich genau (selbst wenn das mathematisch exakt den Vorgaben entspricht, scheitert es in der Praxis an der begrenzten Genauigkeit der Gleitkomma-Arithmetik).

Undertaker

ohne jetzt angeben zu wollen, aber meinen vorschlag finde ich immer noch am elegantesten.
- keine schleifen
- kein fliesskomma
- keine sprünge
- konstante laufzeit
- lesbarer, verständlicher code (im gegensatz zu dem ersten template-gewurschtel)
usw...

Michael E.

Tja, Undertaker, die Laufzeit vom Template ist leider auch konstant, nämlich konstant 0.

Undertaker

Michael E. schrieb:

Tja, Undertaker, die Laufzeit vom Template ist leider auch konstant, nämlich konstant 0.

und was macht das template, wenn der input zur compilezeit noch nicht bekannt ist?

Michael E.

Na auf deine Lösung ausweichen Die Vor- und Nachteile wurden doch schon bereits genannt. Ich wollte halt nur sagen, dass deine Lösung nicht in allen Fällen die beste ist.

Undertaker

Michael E. schrieb:

Ich wollte halt nur sagen, dass deine Lösung nicht in allen Fällen die beste ist.

kann schon sein, aber meine version lässt sich sehr leicht in jede programmiersprache umsetzten, die addition und bitoperationen kennt.
ausserdem kann man sie sogar, wenn's denn sein muss, mit ein paar logikchips zusammenlöten.
das versuch mal mit 'nem template... :p

CStoll

Undertaker schrieb:

- konstante laufzeit

Wenn du die Größe der Eingaben beschränkst, kannst du für jeden Algorithmus "konstante Laufzeit" angeben

(btw, was die Lesbarkeit angeht, steht der Code auch nicht gerade hoch im Kurs - da muß man schon sehr genau hinsehen, um ihn zu verstehen)

Undertaker

CStoll schrieb:

Undertaker schrieb:

- konstante laufzeit

Wenn du die Größe der Eingaben beschränkst, kannst du für jeden Algorithmus "konstante Laufzeit" angeben

irgendwelche beschränkungen hat man bei computern doch immer.
der wertebereich von z.b. 'double' ist auch nicht unendlich gross.

CStoll schrieb:

(btw, was die Lesbarkeit angeht, steht der Code auch nicht gerade hoch im Kurs - da muß man schon sehr genau hinsehen, um ihn zu verstehen)

das musst du nicht mir, sondern der programmiersprache C ankreiden

CStoll

Undertaker schrieb:

CStoll schrieb:

Undertaker schrieb:

- konstante laufzeit

Wenn du die Größe der Eingaben beschränkst, kannst du für jeden Algorithmus "konstante Laufzeit" angeben

irgendwelche beschränkungen hat man bei computern doch immer.
der wertebereich von z.b. 'double' ist auch nicht unendlich gross.

Wenn du es so siehst, hat jedes reale Programm konstante Laufzeit Aber der Punkt ist - dein Ansatz funktioniert nur für 32-Bit-Zahlen (und wenn du irgendwann mit größeren Werten rechnen willst, mußt du die Funktion in Handarbeit erweitern). Die Lösungen mit Schleifen und Templates funktionieren dagegen für jedes n (solange der Computer es im Speicher unterkriegen kann).

(und der Unterschied zwischen O(1) und O(log n) macht sich idR erst für "große n" bemerkbar)

CStoll schrieb:

(btw, was die Lesbarkeit angeht, steht der Code auch nicht gerade hoch im Kurs - da muß man schon sehr genau hinsehen, um ihn zu verstehen)

das musst du nicht mir, sondern der programmiersprache C ankreiden

Nein, das hat nichts mit der Programmiersprache zu tun. Das Bit-Geschiebe an sich ist nicht ohne zusätzliche Hilfen verständlich.

Undertaker

CStoll schrieb:

Das Bit-Geschiebe an sich ist nicht ohne zusätzliche Hilfen verständlich.

ich könnte mit dir wetten, dass die meisten meinen code lesbarer finden als die templates...

CStoll

Undertaker schrieb:

CStoll schrieb:

Das Bit-Geschiebe an sich ist nicht ohne zusätzliche Hilfen verständlich.

ich könnte mit dir wetten, dass die meisten meinen code lesbarer finden als die templates...

Bei dem halbseitigen Konstrukt von hustbaer glaube ich das sofort, bei der Variante von camper nicht mehr (und im Gegensatz zu dem Bit-Gebastel kann man (a) sowas auch mathematisch herleiten und (b) es auch auf andere Basen erweitern).

Undertaker

CStoll schrieb:

...und im Gegensatz zu dem Bit-Gebastel kann man (a) sowas auch mathematisch herleiten...

das bit-gebastel lässt sich auch mathematisch erfassen, allerdings muss man dafür einen anderen zweig der mathematik bemühen.

CStoll

Undertaker schrieb:

CStoll schrieb:

...und im Gegensatz zu dem Bit-Gebastel kann man (a) sowas auch mathematisch herleiten...

das bit-gebastel lässt sich auch mathematisch erfassen, allerdings muss man dafür einen anderen zweig der mathematik bemühen.

Wenn du das sagst - dann zeig doch mal die mathematische Herleitung dafür

(PS: Du bist nicht zufällig mit einem gewissen net/ten/vista/pale dog verwandt?)