Schnelle Lösung gesucht

[del_4901]

Für eine gegebene Zahl x€N brauche ich die nächstgrößere Zahl der Gruppe 2^n für n€N. Ich denke das sich das Ganze auf das diskrete Logarithmus Problem (DLP) reduzieren lässt, wenn dem so ist, dann kann ich's gleich sein lassen.

Bitte lasst mich einen Denkfehler haben!

Ok, ich könnte das ganze vllt auf eine endliche Gruppe drücken, aber da kenn ich keine Lösung die schnell genug währe.

[Der_Donnervogel]

Für eine gegebene Zahl x€N brauche ich die nächstgrößere Zahl der Gruppe 2^n für n€N. Ich denke das sich das Ganze auf das diskrete Logarithmus Problem (DLP) reduzieren lässt, wenn dem so ist, dann kann ich's gleich sein lassen.

Bitte lasst mich einen Denkfehler haben!

Ok, ich könnte das ganze vllt auf eine endliche Gruppe drücken, aber da kenn ich keine Lösung die schnell genug währe.
Es ist noch früh am Morgen, also sorry falls ich total daneben liegen sollte, bin aber noch etwas müde. :frown:

Also wenn ich das richtig verstehe ist z.B. die Zahl x=7 gegeben und es wird in diesem Fall 3 gesucht, da 2^2 < 7 < 2^3.

Falls dem so ist müßte man das doch mit etwas Bitschubserei lösen können.
Ich weiß jetzt nicht wie der Fall abgehandelt werden soll, falls x eine zahl ist, die direkt mit 2^n erreicht wird, aber das sollte kein Problem sein im Falle eines Falles diese Ausnahme zu prüfen.

Ansonsten, nimmt man die Zahl binär und sucht die größte Stelle, die mit einer 1 belegt ist. Dann muß das nächst größere 2^n also die Zahl sein, die entsteht, wenn man auf der nächstgrößeren Binärstelle eine 1 setzt und der Rest alles Nullen sind. Also z.B x=7 -> 0000 0111 also sucht man die größte 1, und macht eine neue Zahl, mit 1 links daneben:

0000 0111 -> 7
0000 1000 -> 8

Kommt das so hin, oder hab ich da was falsch verstanden?

[del_4901]

Also das mit der Bitschubserei habe ich auch erst gedacht. Ich habe aber keine vernünftige Lösung gefunden. Das letzte würde zwar gehen, ist aber extrem langsam. (bzw. die Kosten isses mir dann nicht wert)

2->2 (2^1)
3->4 (2^2)
4->4 (2^2)
5->8 (2^3)
6->8 (2^3)
7->8 (2^3)
8->8 (2^3)
9->16 (2^4)
10->16 (2^4)
11->16 (2^4)
12->16 (2^4)
13->16 (2^4)
14->16 (2^4)
15->16 (2^4)
16->16 (2^4)
17->32 (2^5)
18->32 (2^5)
...

[Mdk]

Was meinst Du mit "extrem langsam"? Wie groß ist Dein n? Und wieviel Zeit darf es brauchen? Der Wikipedia Algorithmus (http://en.wikipedia.org/wiki/Power_of_two) ist Dir zu langsam?

mfg
mdk

[del_4901]

mein n wird wohl auf 4096 hinauslaufen. Aber ich hätt gern das Ergebniss sofort .. Ok ne LUT bauen, die währe dann 8kB. Aber eigendlich wollte ich n nach oben hin offen lassen, wenn es geht. Aber da das geht warscheinlich nicht.

Ich glaube es ist billiger ich such mir ne andere Funktion zum Hashen, das kostet zwar ein bissel Schreibarbeit, aber immernoch besser, als soviel Zeit an dieser performancekritischen Stelle zu verplämpern (new operator) ... ich wollte nämlich eigendlich Zeit einspaaren, und nicht draufzahlen.

[Besserwissend]

Also das mit der Bitschubserei habe ich auch erst gedacht. Ich habe aber keine vernünftige Lösung gefunden. Das letzte würde zwar gehen, ist aber extrem langsam. (bzw. die Kosten isses mir dann nicht wert)
...
Die Aufgabe riecht wirklich nach Bitmanipulation.
Vielleich hilf das weiter http://www.wikiservice.at/dse/wiki.cgi?BitAlgorithmen
Abschnitt "Bestimmung spezieller Bits" -
wie schon vorher gesagt wurde: most significant bit bestimmen, um eine Stelle verschieben, fertig.
Viele Programmiersprachen (deren Standardlibs) bieten eine Funktion "bsr"
zur Bestimmung des MSB, vielleicht könnte man da mal in den Quellcode reinschauen.
Da einige Prozessoren (Intel x86) dafür sogar eine festverdrahtete Funktion besitzen "bsr" sollte eine performante Implementierung eigentlich kein Problem sein.

[del_4901]

Also x = bsr(x-1)<<1 ... das sieht doch gut aus! Danke an den Besserwisser!

Was passiert eigendlich bei x=1? Kommt dann 0 bei raus? ... naja mein Gott, man kann nicht alles haben!

[del_4901]

inline unsigned __fastcall NearestPow2(unsigned n)
{
_asm
{
dec ecx
mov eax, 2
bsr ecx, ecx
shl eax, cl
}
}

Der code ist bei mir am schnellsten, wenn jemand was besseres findet, dann soll er das hier kundtun, und nicht für immer schweigen.

Ist übrigens genauso schnell wie das hier:

unsigned __fastcall add( unsigned n )
{
return (--n<<3)+8;
}

[del_4901]

#include <intrin.h>

unsigned __fastcall NearestPow2(int n)
{
unsigned long index;
_BitScanReverse(&index, --n);
return 2<<index;
}


das hier ist etwas langsamer ... war zu erwarten.

[transstilben]

Man kann auch eine Konvertierung in der Floating Point Einheit machen:
Ganzzahl -> Floating point Darstellung
und danach den Zweierexponenten aus der Floating Point Darstellung ausmaskieren. Das lohnt sich evtl. dann, wenn man keinen "BSR" in Hardware zur Verfügung hat:

inline unsigned __fastcall MyNearestPow2(unsigned int n)
{
assert(n >= 2);

float f_n = n-1;

_asm
{
mov eax,f_n
mov ecx,-126
shr eax,23
add ecx,eax
mov eax,1
shl eax,cl
}
}

[del_4901]

BTW: Hat geklappt, der SpeicherManager ist in Größenordnungen von 3000x so schnell wie die Systemfunktion und hat nicht das Problem von externer Fragmentierung, kann aber auch nur Blöcke der Größe 2^n hohlen. Alles in allem ein Erfolg.
Sicherlich wird sich der eine oder Andere Konsolenprogrammierer an den Kopp fassen, was ich im WorstCase für Speicher verplemper, aber ich hatte ein echtes Problem mit vielen kleinen Objekten, was ich aus der Welt schaffen musste.