✔ Korrektes Potenzieren durch Divide&Conquer

[Jellysheep]

Wozu brauchst du denn noch die Variable potenz?
Sie ist nie in Gebrauch.

 

[Vereth]

Außerdem kannst du den Code etwas straffer und übersichtlicher gestalten, indem du die Fälle n==0 und n==1 als eigenständiges if implementierst; du schreibst dann also

if ( n == 0 ) return 1;
if ( n == 1 ) return x;
if ( n%2 ...

// EDIT: Bis 2^1023 geht in double bei mir rein, long double ist bei mir leider als double definiert. (WARUM?)

Das hat mit der Maschinenabhängigkeit der Compiler-Implementierung zu tun. Auf manchen Systemen ist ein int so groß wie ein short, auf anderen kann er so groß sein wie ein long. Es steht jedem Übersetzer frei, short und long so zu interpretieren, wie es für seine Maschine sinnvoll ist. Eigentlich kann man sich nur darauf verlassen, dass short nicht länger ist als long. Für die Fließkommatypen gilt das entsprechend.

@Jellysheep: Ich wüßte gerne, wie meine iterative Implementierung in deinem Geschwindigkeitstes abschneidet.
Zu Erinnerung, hier ist nochmal der Code

double potenz ( double x, unsigned int n )
{
  double erg = 1;
 
  for ( ; n != 0; n >>= 1, x *= x )
  { if ( (n&1) == 1 ) erg *= x; }
 
  return erg;
}

 

[Jellysheep]

@Vereth:
Danke für die Erklärung, so ähnlich hatte ich es auch in Erinnerung.
Deine Variante braucht für den Test ca. 440 ms und ist damit ein kleines bisschen langsamer als pow(), und sie ist doppelt so schnell wie der vorgestellte Algorithmus (mit i ).

 

[deepthroat]

@Vereth:
Danke für die Erklärung, so ähnlich hatte ich es auch in Erinnerung.
Deine Variante braucht für den Test ca. 440 ms und ist damit ein kleines bisschen langsamer als pow(), und sie ist doppelt so schnell wie der vorgestellte Algorithmus (mit i ).

Das ist natürlich stark Compiler und System-abhängig.

Bei meinen Tests auf einem Intel Core 2 Duo ist eine mit dem MinGW GCC 4.4.0 kompilierte (mit -O3 optimierte) Version der rekursiven Funktion schneller als die iterative Funktion (auch mit -O3 kompiliert). [OS: Windows XP SP3]

Testcode:

for(int j = 0; j<100000; j++){
        for(int i = 0; i<1024; i++){
            x = pow((double)2, i);
            //x = potenz_dc(2, i);
        }
    }

Ergebnisse (in der Bash per time), gemittelt aus 10 Durchläufen (nach 2 Anfängsdurchläufen)

pow: 10.8725s
potenz_iterativ:  5.1s
potenz_rekursiv: 4.4847s

D.h. die pow() Version ist ungefähr doppelt so langsam, verwendet allerdings auch den Typ double als Exponenten.

Unter Linux auf einem AMD Athlon 64 X2 stellt sich die Situation etwas anders dar:

pow: 14.211s
potenz_rekursiv: 5.9292s
potenz_iterativ:  5.547s

Welchen Compiler benutzt du denn? Welches Betriebssystem? Wie hast du die Zeit gemessen?

Gruß

 

[Jellysheep]

Hi,
ich habe auf XP mit Visual Studio 2008 per clock() (von time.h) gemessen.
Das war aber die Debug-Version. Daher kommt vermutlich der Unterschied.
Release:

pow: 1,47 s
iteratov: 1,50 s
rekursiv: 1,32 s

 

[Vereth]

Und wenn man es ganz schnell haben möchte, extrahiert man den Exponenten per &-Maske, multipliziert diesen mit dem übergebenen n, und fügt das Ergebnis als neuen Exponenten wieder in die double-Zahl ein.

 

[Jellysheep]

Interessant. Funktioniert das?
Kannst ja mal ein Beispiel programmieren.

 

[deepthroat]

Hi.

Hi,
ich habe auf XP mit Visual Studio 2008 per clock() (von time.h) gemessen.

Bei einer Messung mit so wenigen Iterationen kannst du clock() völlig vergessen. Du mußt schon zusehen das der Workload etwas größer ist, so das die Ungenauigkeit von clock() nicht so ins Gewicht fällt. Hast du außerdem darauf geachtet, das die Testschleife nicht "wegoptimiert" wird? Das sieht anhand der Daten nicht so aus... Oder wieviel Iterationen der äußeren Schleife hast du durchgeführt?

Das war aber die Debug-Version. Daher kommt vermutlich der Unterschied.
Release:

Ich habe es gerade auch einmal mi VS 2008 probiert. Es hatte mich nämlich stutzig gemacht wie du auf diese Werte gekommen bist, da pow(double, double) langsamer hätte sein sollen.

Dabei habe ich auch den C++ Compiler verwendet (da der C Compiler ziemlich unbrauchbar ist, kein C99 unterstützt) und dabei festgestellt: in math.h ist pow überladen: pow(double, int).

Es findet sich dort folgendes Template:

template<class _Ty> inline
        _Ty _Pow_int(_Ty _X, int _Y)
        {unsigned int _N;
        if (_Y >= 0)
                _N = (unsigned int)_Y;
        else
                _N = (unsigned int)(-_Y);
        for (_Ty _Z = _Ty(1); ; _X *= _X)
                {if ((_N & 1) != 0)
                        _Z *= _X;
                if ((_N >>= 1) == 0)
                        return (_Y < 0 ? _Ty(1) / _Z : _Z); }}

Hm. Kommt mir irgendwie leicht bekannt vor.

Ergebnisse mit VS 2008, /Ox (max. Optimierung), Win XP 2008:

std::pow(double, int) 4.9863s
iterativ: 4.5632s
rekursiv: 9.6167

Hier ist die Version von Vereth am schnellsten, wobei diese nicht mit neg. Exponenten umgehen kann.

An der Zeit für die rekursive Variante erkennt man ziemlich gut wie schlecht der MS Compiler manchmal optimiert.... ;-]

Gruß