Nächste Zweierpotenz berechnen

[Don P]

Hallo,

Die Dikussion um das beste Verfahren, die nächste größere Zweierpotenz für eine Zahl zu ermitteln, die keine Potenz von 2 ist, hat mich zu weiteren Experimenten angeregt.

Obwohl man mit dem einfachen Test (n-1)&n == 0 schnell ermitteln kann, ob n eine Potenz von 2 ist, war das leider wenig hilfreich zur Entwicklung eines schnellen Algorithmus', der ggf. nächst größere Zweierpotenz liefert.

Længlich hat gemessen, dass sein Algorithmus (PHP) um einiges schneller ist als meiner. Seiner braucht immer gerade so viele Schleifendurchläufe, wie die Zahl Binärstellen hat. Hier ist er in JavaScript:

  
var leanglich = function(zahl){        // Ermittelt die nächste Zweierpotenz nach Længlich.  
  
    var potenz = 1;                    // Wir fangen mit der kleinsten an  
  
    while (zahl > potenz)              // Solange sie noch zu klein ist...  
    {  
        potenz <<= 1;                  // ... versuchen wir die nächsthöhere  
    }  
    return potenz;  
}

Und hier meiner:

  
var donP = function(zahl) {            // Ermittelt die nächste Zweierpotenz nach Don P.  
  
  if (!((zahl - 1) & zahl)) { return zahl; }  // Für Zweierpotenzen gilt: (n-1)&n === 0  
  
  var shr = 1;                                // Anzahl Rechts-Shifts bis Zweierpotenz erreicht  
  
  while ((zahl - 1) & zahl) {                 // Solange keine Zweierpotenz erreicht ist:  
  
    zahl >>= 1;                               //  Verschiebung um 1 nach rechts,  
    shr++;                                    //  Anzahl Verschiebungen merken.  
  }  
  
  return zahl << shr;                         // Enprechend wieder zurückschieben.  
}

Obwohl hier oft weniger Schleifendurchläufe nötig sind, im Idealfall gar keiner, ist dieser Code um die Hälfte langsamer, wohl hauptsächlich wegen der vielen Berechnungen von (n-1)&n.

Hier nochmal Længlichs Messergebnisse (PHP) für 5 mal 60000 Berechnungen in sec:

1. Don P: 0.44359087944
   Længlich: 0.278346061707
2. Don P: 0.409577131271
   Længlich: 0.289813995361
3. Don P: 0.392857074738
   Længlich: 0.295516967773
4. Don P: 0.398221969604
   Længlich: 0.284239053726
5. Don P: 0.409832954407
   Længlich: 0.280338048935

Wie ich herausfand, gibt es aber einen noch schnelleren Weg (jedenfalls in JavaScript): Man bestimmt das höchste gesetzte Bit einer Zahl mit Hilfe eines geeigneten Näherungsverfahrens, das stets nur wenige Iterationen braucht:

  
var newton = function(zahl) {          // Ermittelt die nächste Zweierpotenz durch Näherungsverfahren.  
  
  var step = 32,                       // Schrittweite in Bits für nächste zu testende Zweierpotenz  
      test = 1 << 62;                  // Unsere größte zu testende Zweierpotenz sei 2^30  
  
  while (step && test>zahl) {          // während Schrittweite>0 und Testzahl ist größer  
  
    step >>= 1;                        //  Schrittweite halbieren,  
    test >>= step;                     //  mit nächst kleinerer Testzahl weitermachen.  
  
    while (step && test<zahl) {        //  während Schrittweite>0 und Testzahl ist kleiner  
  
      step >>= 1;                      //   Schrittweite halbieren,  
      test <<= step;                   //   mit nächst gößerer Testzahl weitermachen.  
    }  
  }  
  
  if (test<zahl) { return test << 1; } // Zahl ist keine Zweierpotenz => nächst größere zurückgeben  
  return test;                         // Zahl ist Zweierpotenz => diese zurückgeben  
}  

Hier ein paar typische Messergebnisse für jeweils 60000 Berechnungen (JavaScript) in ms:

1. 60000 Zahlen 1...60001
   Don P: 500
   Newton: 344
   Længlich: 375

2. 60000 Zahlen 89940000...90000000
   Don P: 781
   Newton: 344
   Længlich: 563

3. 60000 Zahlen 1073681823...1073741823
   Don P: 859
   Newton: 329
   Længlich: 610

Wie man sieht, ist der Geschwindigkeitsvorteil ist umso deutlicher, je größer die Zahlen werden. Das war zu erwarten, weil die Anzahl der Schleifendurchläufe bei den bisherigen Lösungen linear mit den Testzahlen steigt, während es beim Näherungsverfahren immer nur max. 6 Iterationen sind.

Gruß, Don P

[e7]

Hi,

hab mir das ganze mal angesehen und bin durch eine kurze Google-Recherche auf die Idee mit log() gekommen... Folgender PHP-Code ist zumindest schneller als die Newton-Variante (einfach ein $, dann läufts auch schon in PHP *g*):

pow(2,ceil(log($zahl, 2)))

Ergebnisse bei for ($i = 1000; $i < 50000000; $i += 5):
Newton: 32.09 ms
log(): 25.53 ms

Zahlen ähneln sich zumindest beim mehrfachen Durchlauf, also scheinen die Ergebnisse ganz grob zur Orientierung geeignet zu sein...

e7

[Don P]

Hallo,

Folgender PHP-Code ist zumindest schneller als die Newton-Variante (einfach ein $, dann läufts auch schon in PHP *g*):

pow(2,ceil(log($zahl, 2)))

Cool, hätte ich nicht eigentlich gedacht.

In javascript geht es nicht ganz so einfach, weil es nur ln (Basis e) und log (Basis 10) gibt. Man kann sich für Basis 2 so behelfen:

  
var logarithmisch = function(zahl) {  
  
  with (Math) { return pow(2,ceil(log(zahl)/log(2))); }  
}

Das ist aber etwas langsamer als die Newton-Variante. Das Tempo hängt aber ebenfalls nicht von der Größe der Zahlen ab:

60000 Zahlen 1...60001
Newton: 344
Log: 391

60000 Zahlen 89940000...90000000
Newton: 343
Log: 406

60000 Zahlen 1073681823...1073741823
Newton: 313
Log: 406

Gruß, Don P

[Norbert]

Hai,

lesen ist auch nicht Eure Staerke was?
Im urspruenglichen Thread war die Loesung doch schon drin.
Und lange bevor Ihr angefangen habt darueber zu sinnieren.
Habt Ihr nix zu tun ... hier muesste mal aufgereumt werden ... ;-)

Gruss Norbert

[Don P]

Hallo,

lesen ist auch nicht Eure Staerke was?

Und schreiben nicht die deine... (siehe die ^ unten).

Im urspruenglichen Thread war die Loesung doch schon drin.

Das wissen wir, aber ich wollte nicht glauben, dass das die schnellste Lösung ist.

Und lange bevor Ihr angefangen habt darueber zu sinnieren.

^
Stimmt eben nicht.

Habt Ihr nix zu tun ...

Doch, wir beschäftigen uns mit dem Laufzeitverhalten versch. Implementierungen der selben Funktion.

hier muesste mal aufgereumt werden ... ;-)

^
Gruß, Don P

[Længlich]

Namaskaaramulu!

lesen ist auch nicht Eure Staerke was?

Ich hatte den gesamten ursprünglichen Thread gelesen, bevor ich gepostet habe, und das hat eigentlich auch ganz gut geklappt. ;-)

Sowohl Don P als auch mir war die ganze Zeit klar, daß der Ursprungsthread schon eine Lösung enthielt (sogar mehrere). Und der OP war zu diesem Zeitpunkt ja auch schon längst zufrieden.
Trotzdem empfinde ich es nicht als Zeitverschwendung, Alternativen zur Diskussion zu stellen. Selbst wenn im Anwendungsbereich des OP die erste Lösung jetzt vermutlich sogar die optimale war, ist das in anderen Fällen vielleicht nicht so. Wir wissen ja nicht, was die Leute vorhaben, die diese beiden Threads später im Archiv finden werden. Vielleicht verwenden die ja nicht PHP, sondern D oder Brainfuck. ;-)

Habt Ihr nix zu tun ... hier muesste mal aufgereumt werden ... ;-)

Nun, äh, das ist zugegebenermaßen der Haken an der Sache. Strenggenommen hätte ich wirklich keine Zeit für sowas, aber es macht halt Spaß. ;-)
Und Don P scheint's da nicht anders zu gehen, sonst wäre uns der Urthread ja auch nicht während einer Arbeitspause ins Archiv entglitten. ;-)

Viele Grüße vom Længlich

[Christoph]

Abend.

var logarithmisch = function(zahl) {

with (Math) { return pow(2,ceil(log(zahl)/log(2))); }
}

  
Versuch mal statt `pow(2,x)`{:.language-javascript} ein `1 << x`{:.language-javascript} beim nächsten Vergleich...  
  
Christoph  
  

[Christoph]

...und wenn du schon dabei bist: ersetze bitte Math.log(2) durch Math.LN2 ;)

Christoph

[Don P]

Hallo,

...und wenn du schon dabei bist: ersetze bitte Math.log(2) durch Math.LN2 ;)

Gute Idee, könnte vom mir sein ;)
Damit läuft's richtig schnell und macht meine Newton-Methode auch für JavaScript überflüssig:

  
var logarithmisch = function(zahl) {  
  
  with (Math) { return 1 << ceil(log(zahl)/LN2); }  
}

Ergebnisse:

60000 Zahlen 1...60001
Newton: 359
Log: 329

60000 Zahlen 89940000...90000000
1. Newton: 344
   Log: 344
2. Newton: 312
   Log: 329

60000 Zahlen 1073681823...1073741823
1. Newton: 313
   Log: 328
2. Newton: 328
   Log: 328

60000 Zahlen 1...60001
1. Newton: 344
   Log: 329
2. Newton: 312
   Log: 329

Gruß, Don P

[Don P]

Hallo,

Versuch mal statt pow(2,x) ein 1 << x beim nächsten Vergleich...

Ja, das ist ein bisschen schneller, kommt aber noch nicht ganz an die Newton -Methode heran:

60000 Zahlen 1...60001
Newton: 343
Log: 375

60000 Zahlen 89940000...90000000
Newton: 328
Log: 360

60000 Zahlen 1073681823...1073741823
Newton: 313
Log: 359

Gruß, Don P

[Christoph]

Versuch mal statt pow(2,x) ein 1 << x beim nächsten Vergleich...

Ja, das ist ein bisschen schneller, kommt aber noch nicht ganz an die Newton -Methode heran:

Sicher? Versuchs mal ohne das with(Math).

Bei meinen Tests ist

  
var logarithmic = function(x)  
{  
 return 1 << Math.ceil(Math.log(x)/Math.LN2);  
};

_wesentlich_ schneller...

Christoph

[Don P]

Hallo,

Bei meinen Tests ist

var logarithmic = function(x)
{
return 1 << Math.ceil(Math.log(x)/Math.LN2);
};

>   
> \_wesentlich\_ schneller...  
  
Bei mir nicht gerade \_wesentlich\_, aber immerhin:  
  
60000 Zahlen 1...60001  
Newton: 344  
Newton: 343  
Log: 313  
Log: 312  
  
60000 Zahlen 89940000...90000000  
Newton: 344  
Newton: 328  
Log: 312  
Log: 313  
  
60000 Zahlen 1073681823...1073741823  
Newton: 313  
Newton: 313  
Log: 297  
Log: 313  
  
Gruß, Don P  

[Længlich]

Shalom!

Folgender PHP-Code ist zumindest schneller als die Newton-Variante (einfach ein $, dann läufts auch schon in PHP *g*):

pow(2,ceil(log($zahl, 2)))

Cool, hätte ich nicht eigentlich gedacht.

Ich auch nicht. Aber PHP und Javascript sind Scriptsprachen und daher naturgemäß etwas langsamer als compilierter Code. Wenn nun solche Built-In-Funktionen wie pow und log schon vorkompiliert sind, wovon ich ausgehe, sind sie wohl deswegen vergleichsweise schneller.

Viele Grüße vom Længlich

[ChrisB]

Hi,

die Optimierungen der Funktionen im weiteren Threadverlauf hab ich jetzt mal aussen vor gelassen - mich interessierte, wie analog zu meinem Vorschlag im anderen Thread in JavaScript wohl die Stringfunktionen abschneiden wuerden ...

var chrisB = function(zahl) {  
 var bin = zahl.toString(2); // Binaerstring erzeugen  
 if(bin.lastIndexOf("1")) {  // wenn nicht erste Stelle (0) die letzte "1" enthaelt  
  return Math.pow(2, bin.length);  // Zwei hoch Stringlaenge  
 }  
 else {  
  return zahl;  
 }  
}

Hier ein paar typische Messergebnisse für jeweils 60000 Berechnungen (JavaScript) in ms:

Beim Messen faellt auf, dass
a) die Ergebnisse sich zwischen mehreren Testlaeufen signifikant unterscheiden koennen (war zu erwarten), bis hin dazu, dass die "Platzierung" der einzelnen Algorithmen wechselt - es sind also immer mehrere Testlaeufe noetig, um eine Tendenz ablesen zu koennen, und
b) je nach Browser unterschiedliche Methoden die schnelleren sind.

(Hab mal nur die letzte Testreihe mit 1073681823 bis 1073741823 ausfuehrlicher getestet.)

Mein Vorschlag kackt im Opera (9.24) deutlich ab (newton < laenglich < donP << chrisB),
im IE 7 ist der donP deutlich am langsamsten (newton < laenglich < chrisB << donP),
im Safari (3.0.4/Win) liegen newton und chrisB etwa gleichauf, laenglich etwas langsamer, donP deutlich abgeschlagen -
und im Firefox (2.0.0.11) "gewinnt" chrisB eigentlich immer vor newton und laenglich, donP auch hier wieder etwas abgeschlagen.

Wie man sieht, haengt es also nicht nur vom Algorithmus ab, sondern auch von der JavaScript-Engine, was wirklich jeweils die schnellste Methode ist.
Welche allgemein ("cross-browser") die performanteste ist, muesste man vermutlich in aufwendigeren Testreihen evaluieren ...

MfG ChrisB

[Don P]

Hallo ChrisB,

mich interessierte, wie analog zu meinem Vorschlag im anderen Thread in JavaScript wohl die Stringfunktionen abschneiden wuerden ...

Ach ja, diesen Vorschlag habe ich mangels PHP-Verständnis nicht in JavaScript umgesetzt, zumal es auch mehr um's Zählen von Bits ging.

Ist aber auch interessant. Deine Funktion lässt sich noch wesentlich beschleunigen, wenn man den Test auf Zweierpotenz der Originalzahl aus der donP-Funktion entlehnt und das Potenzieren aus Christians logarithmischer Lösung:

  
var chrisB_neu = function(zahl) {  
  
  if (!((zahl-1)&zahl)) {return zahl;}  // Für Zweierpotenzen gilt: (n-1)&n === 0  
  return 1 << zahl.toString(2).length;  // Zwei hoch Stringlaenge  
}

Zwei Messungen im IE6 haben ergeben:

Newton: 312
Log: 313
ChrisB: 656
ChrisB neu: 500

Newton: 312
Log: 328
ChrisB: 656
ChrisB neu: 485

Stringfunktionen sind halt relativ teuer, aber gegenüber der donP- und der Længlich-Lösung schneidet die Binärstring-Variante (chrisB_neu) doch deutlich besser ab.

Beim Messen faellt auf, dass
a) die Ergebnisse sich zwischen mehreren Testlaeufen signifikant unterscheiden koennen (war zu erwarten), bis hin dazu, dass die "Platzierung" der einzelnen Algorithmen wechselt - es sind also immer mehrere Testlaeufe noetig, um eine Tendenz ablesen zu koennen, und

Stimmt.

b) je nach Browser unterschiedliche Methoden die schnelleren sind.

Das ist aber nicht gut :-( ...

Mein Vorschlag kackt im Opera (9.24) deutlich ab (newton < laenglich < donP << chrisB),
im IE 7 ist der donP deutlich am langsamsten (newton < laenglich < chrisB << donP),
im Safari (3.0.4/Win) liegen newton und chrisB etwa gleichauf, laenglich etwas langsamer, donP deutlich abgeschlagen -
und im Firefox (2.0.0.11) "gewinnt" chrisB eigentlich immer vor newton und laenglich, donP auch hier wieder etwas abgeschlagen.

Zitat Spock: "Faszinierend!"
Mein Firefox (2.0.0.11) ist deutlich langsamer als der IE6, aber die Rangfolge der versch. Algorithmen bleibt etwa gleich. Allerdings habe ich im FF zur Zeit viele Tabs offen, vielleicht wirkt sich das auch noch aus.

Welche allgemein ("cross-browser") die performanteste ist, muesste man vermutlich in aufwendigeren Testreihen evaluieren ...

Tja, ich hasse diese Browser-Unterschiede :-(( ...
Wann kommt der Tag (St. Nimmerlein?), ab dem jeder Code cross-browser-fähig *und* vergleichbar performant sein wird?

Gruß, Don P