3. Pottenzieren

Pottenzieren

  • I

    Potenz schrieb:

    Kann ich nicht auch einfach den Compiler die Zahl berechnen lassen? Denn es ist eh eine Konstante.

    Das geht mit Template-Metaprogrammierung. In etwa so:

    template<int base, unsigned int exp>
struct pow
{
	static const int value = base * pow<base, exp-1>::value;
};

template<int base>
struct pow<base, 0>
{
	static const int value = 1;
};

// ...

cout << pow<5,4>::value << endl;    // Ausgabe: 625

    Dabei gehen aber als "Parameter" wirklich nur zur Complilezeit auswertbare Integer-Konstanten.

    0
  • J

    unskilled schrieb:

    vom code her kürzer, aber von der laufzeit länger 😛

    Hier, hab ich gerade Programmiert:

    #include <iostream>
#include <windows.h>
using namespace std;

int my_pow1(int base,int exp)
{
  if(exp == 0)
    return 1;

  int ret_val = 1;

  while(exp > 1)
  {
    if(exp%1)
    {
      --exp;
      ret_val *= base;
      continue;
    }

    base *= base;
    exp /= 2;
  };

  return ret_val * base;
} 

int my_pow2(int base,int exp)
{
    if(exp == 0) return 1;
    int ret_val = 1;

    for(int c=1;c<=exp;c++)
    {
        ret_val*=base;
    }

    return ret_val;
} 

int main()
{
	int c,d,e;
	c=50000000;
	d=4;
	e=5;
	DWORD dwStartTime = clock();
	for(int i=0;i<c;i++)my_pow1(d,e);
	DWORD dwEndTime = clock();
	cout << "Zeit 1: " << dwEndTime-dwStartTime << " ms" << endl;
	dwStartTime = clock();
	for(int i=0;i<c;i++)my_pow2(d,e);
	dwEndTime = clock();
	cout << "Zeit 2: " << dwEndTime-dwStartTime << " ms" << endl;
	getchar();
	return 0;
}

    Ausgabe:

    Zeit 1: 640 ms
Zeit 2: 358 ms

    Laut Ausgabe ist meine Version schneller 😛

    0
  • K

    Super Vergleiche ... bei mir wird Version 2 komplett wegoptimiert.

    0
  • Mod

    @Jochen S. Deine Funkmtionen ergeben unterschiedliche Werte für 4 hoch 5. my_pow1 ist 256, my_pow2 rechnet richtig.

    Außerdem: Optimierungen ausgeschaltet? Bei mir ergeben nämlich beide Null weil eine Schleife deiner Form einfach wegoptimiert wird. Und wenn ich dafür sorge, dass die Schleife nicht wegoptimiert wird, dann wird die Funktion zu 1024 (bzw. zu 256) wegoptimiert. Erst wenn ich alles von der Benutzereingabe abhängig mache, bekomme ich ein brauchbares Ergebnis:

    int main()
{
    long int c,d,e;
    cin >> c;
    cin >> d;
    cin >> e;
    int counter=0;
    for(long int i=0;i<c;i++) counter+=my_pow1(d,e);
    // for(long int i=0;i<c;i++) counter+=my_pow2(d,e);
    cout<<counter<<endl;
    return 0;
}

    Dann braucht die (falsche) Version von my_pow1 gute 14.5 s für 1 Gigadurchlauf. my_pow2 braucht dafür gute 12 s.

    0
  • U

    ich dussel... xD

    entweder if(exp&1) oder if(exp%2)
    ja gut - zur geschwindigkeit:
    bei kleinen exponenten ist nat. deine version schneller
    bei höheren sollte meine schneller sein

    bb

    0
  • Mod

    unskilled schrieb:

    ich dussel... xD

    entweder if(exp&1) oder if(exp%2)
    ja gut - zur geschwindigkeit:
    bei kleinen exponenten ist nat. deine version schneller
    bei höheren sollte meine schneller sein

    bb

    Jo, jetzt stimmt das Ergebnis. Bei 0.1 Gigadurchläufen(ist sehr viel langsamer als 4^5) für pow(2,30) (das größte was in einen int passt ohne Überlauf) habe ich:
    2.5 s für Variante 1
    5.1 s für Variante 2

    Jetzt müsste man noch ausmessen welches wann schneller ist und eine Kombifunktion schreiben die das jeweils günstigste wählt, je nach Exponent.

    0
  • J

    SeppJ schrieb:

    Jetzt müsste man noch ausmessen welches wann schneller ist und eine Kombifunktion schreiben die das jeweils günstigste wählt, je nach Exponent.

    Da würde für die Auswahl der passenden Funktion aber auch wieder einges an Zeit draufgehen. 😉

    Was jetzt mal interessant wäre: Ein Diagramm, das die Geschwindigkeiten der beiden Funktionen in Abhängigkeit der Exponenten darstellt.

    0
  • Mod

    Jochen S. schrieb:

    Da würde für die Auswahl der passenden Funktion aber auch wieder einges an Zeit draufgehen. 😉

    Hmm stimmt. if-Abfragen sind zwar nur eine Anweisungen bringen aber möglicherweise das prefetching moderner Prozessoren durcheinander. Müsste man ausprobieren.

    Was jetzt mal interessant wäre: Ein Diagramm, das die Geschwindigkeiten der beiden Funktionen in Abhängigkeit der Exponenten darstellt.

    Wenn du nicht an genauen Zahlen interessiert bist: Variante 1 geht wie ein Logarithmus, Variante 2 geht linear. (Die Informatiker mögen mich korrigieren falls meine Laufzeitanalyse falsch ist)

    0
  • M

    Mal ne andere Frage und was passiert wenn man pow(0, 0) eingibt?

    Nicht dran gedacht oder? 😉

    SeppJ schrieb:

    Was jetzt mal interessant wäre: Ein Diagramm, das die Geschwindigkeiten der beiden Funktionen in Abhängigkeit der Exponenten darstellt.

    Wenn du nicht an genauen Zahlen interessiert bist: Variante 1 geht wie ein Logarithmus, Variante 2 geht linear. (Die Informatiker mögen mich korrigieren falls meine Laufzeitanalyse falsch ist)

    Bin da der selben Meinung, zumindest so in etwa.

    Mfg Marco

    0
  • J

    Wenn der Exponent 0 ist, ist das Ergebnis 1. Das machen die Funktionen schon richtig.

    Edit: Gut, 0^0 ist nicht definiert, aber wenn die Funktionen diesem Fall noch prüfen sollen und dann noch eine Exception werfen sollten, wären sie ja noch viel langsamer. 😃

    Die Logarithmusfunktion scheint vom Verlauf her passend zu sein.
    (Einen Beweis kann ich jetzt nicht aus dem Ärmel schütteln, bin halt nicht die große Mathe-Leuchte)

    MfG, Jochen

    0
  • Mod

    Jochen S. schrieb:

    Die Logarithmusfunktion scheint vom Verlauf her passend zu sein.
    (Einen Beweis kann ich jetzt nicht aus dem Ärmel schütteln, bin halt nicht die große Mathe-Leuchte)

    Es wird nach jedem Durchgang exp durch zwei geteilt bis exp Null ist, daher werden ~log_2(exp) Durchläufe gemacht.

    0
  • U

    das continue war auch noch unnötig. wieder ein takt gespart... 😉
    damit dein fehler auch noch abgedeckt ist:

    int my_pow(int base, unsigned int exp)
{
  assert(base != 0 && "pow(0, x) is not defined");

  if(exp == 0)
    return 1;

  int ret_val = 1;

  while(exp > 1)
  {
    if(exp%2)
    {
//      --exp; -- auch noch unnötig, wird eh bei der division abgeschnitten
      ret_val *= base;
    }

    base *= base;
    exp /= 2;
  };

  return ret_val * base;
}

    ja, es ist nen logikfehler, deshalb reicht das assert ;o)

    bb

    0
  • J

    Da gibt es aber noch einen Fehler: 0^x ist schon definiert, solange x ungleich 0 ist.
    Wo wir gerade bei der Effizienz sind:
    Ich würde das 0^0-Problem so lösen:

    int my_pow(int base, unsigned int exp,bool* pOut = NULL)
{

  if(pOut&&!exp&&!base){*pOut = true;return 0;}
  if(exp == 0)
    return 1;
//...
}

// So könnte dann der Aufruf aussehen:

bool var = false;
pow(0,0,&var);
if(var){/*Fehler beim Potenzieren.*/}

    Wenn ich bei google 0^0 eingebe, kommte als Ergebnis: 0^0 = 1 😮

    MfG, Jochen

    0
  • J

    Noch was zur Effizienz: 😃

    Man könnte die Zeile 12

    if(exp%2)

    doch auch ersetzen durch

    if(exp&1)

    Die Bit-Operationen müssten eigentlich schneller sein als eine Division.

    0
  • U

    hmm... mir auch egal - wenn man etwas undefiniertes bekommen möchte, bekommt man auch was undefiniertes^^

    also hier ist meine variante jetzt bei einem exponenten von >= 3 schneller
    bei einem exponenten von 2 ist der unterschied nur minimal.

    int my_pow(int base, unsigned int exp)
{
  if(exp == 0)
    return 1;

  int ret_val = 1;

  for(; exp > 1; exp /= 2)
  {
    if(exp%2)
      ret_val *= base;

    base *= base;
  };

  return ret_val * base;
}

int other_pow(int base, unsigned int exp)
{
	if(exp == 0)
		return 1;

	int ret_val = 1;

	for(unsigned int i=0; i < exp; ++i)
		ret_val *= base;

	return ret_val;
}

    gemessen habe ich so:

    #include "my/timer.h"

#include <cstdlib>
using std::size_t;
#include <iostream>

int main()
{
	const size_t iterations = 100*1000*1000;

	int base;
	std::cin >> base;
	unsigned int exp;
	std::cin >> exp;

	int rubbish = 0x12345;

	my::timer_t timer;
	for(size_t i(0); i != iterations; ++i)
	{
		++rubbish;
		rubbish ^= my_pow(base+i, exp);
	}
	std::cout << timer() << std::endl;

	timer.reset();
	for(size_t i(0); i != iterations; ++i)
	{
		++rubbish;
		rubbish ^= other_pow(base+i, exp);
	}
	std::cout << timer() << std::endl;

	std::cin.ignore();
	std::cin.get();
	std::cout << "\t\t" << rubbish << std::endl;
}

    ihr müsst halt nur timer entsprechend eures betriebssystems basteln 😉
    ich habs mit QueryPerformanceFrequency (WinAPI) gemacht.

    ich hatte es zwischenzeitlich schon fast aufgegeben, den compiler überlisten zu wollen(egal, was ich probiert hab, er hat zu viel optimiert^^) - dann ist mir doch noch eingefallen, dass man die basis ja pro schleifenaufruf verändern kann.. : D

    bb

    edit: Jochen: So dumm ist kein Compiler - ich ersetze doch auch nicht die Division durch nen rechtshift. Habe mir aber gerade mal den asm-code angeguckt, ich seh zumindest nen rechtsshift um eins.

    ;	{
;		++rubbish;
;		rubbish ^= my_pow(base+i, exp);
00E41217  mov         edx,dword ptr [esp+18h] 
00E4121B  inc         ebp  
00E4121C  lea         eax,[esi+edx] 
00E4121F  mov         ecx,edi 
00E41221  mov         edx,1 
00E41226  test        edi,edi 
00E41228  je          main+97h (0E41247h) 
00E4122A  cmp         edi,edx 
00E4122C  jbe         main+94h (0E41244h) 
00E4122E  mov         edi,edi 
00E41230  test        cl,1 
00E41233  je          main+88h (0E41238h) 
00E41235  imul        edx,eax 
00E41238  mov         ebx,eax 
00E4123A  shr         ecx,1 
00E4123C  imul        eax,ebx 
00E4123F  cmp         ecx,1 
00E41242  ja          main+80h (0E41230h) 
00E41244  imul        edx,eax 
00E41247  inc         esi  
00E41248  xor         ebp,edx 
00E4124A  cmp         esi,5F5E100h 
00E41250  jne         main+67h (0E41217h) 
;	}

    und statt %2 &1 eingesetzt:

    01341217  mov         edx,dword ptr [esp+18h] 
0134121B  inc         ebp  
0134121C  lea         eax,[esi+edx] 
0134121F  mov         ecx,edi 
01341221  mov         edx,1 
01341226  test        edi,edi 
01341228  je          main+97h (1341247h) 
0134122A  cmp         edi,edx 
0134122C  jbe         main+94h (1341244h) 
0134122E  mov         edi,edi 
01341230  test        cl,1 
01341233  je          main+88h (1341238h) 
01341235  imul        edx,eax 
01341238  mov         ebx,eax 
0134123A  shr         ecx,1 
0134123C  imul        eax,ebx 
0134123F  cmp         ecx,1 
01341242  ja          main+80h (1341230h) 
01341244  imul        edx,eax 
01341247  inc         esi  
01341248  xor         ebp,edx 
0134124A  cmp         esi,5F5E100h 
01341250  jne         main+67h (1341217h)

    freund und helfer war wie immer der msvc9

    bb

    0
  • D

    Ein weiterer Kandidat:

    #include <iostream>

typedef long PowNumType;

inline PowNumType NewSq(PowNumType a)
{
	return a * a;
}

PowNumType NewPow(PowNumType a, PowNumType b)
{
	if (b == 0)
	{
		return 1;
	}
	else if (b == 1)
	{
		return a;
	}
	else if (b % 2 == 0)
	{
		return NewSq(NewPow(a, b / 2));
	}

	return a * NewPow(a, b - 1);
}

int main()
{
	std::cout << NewPow(14, 8) << "\n";

	return 0;
}

    Für größere Zahlen müsste das sehr gut performen. Aber kann gerade keine konkrete Vergleichszeit messen.

    0
  • V

    Dummie schrieb:

    Für größere Zahlen müsste das es sehr gut performen. Aber kann gerade keine konkrete Vergleichszeit messen.

    Warum soll das besser als my_pow unskilled 09 Jun 2010 00:22 sein?

    0
  • D

    volkard schrieb:

    Dummie schrieb:

    Für größere Zahlen müsste das es sehr gut performen. Aber kann gerade keine konkrete Vergleichszeit messen.

    Warum soll das besser als my_pow unskilled 09 Jun 2010 00:22 sein?

    Ich hatte den Algorithmus irgendwo mal aufgeschnappt und hatte einfach gedacht, dass er vielleicht mithalten kann.
    Aber die Begeisterung ist wohl nicht so groß 🤡

    0
  • O

    SeppJ schrieb:

    Es wird nach jedem Durchgang exp durch zwei geteilt bis exp Null ist, daher werden ~log_2(exp) Durchläufe gemacht.

    Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!

    Um ganz genau zu sein ist Variante 1 deswegen O(2^n). Bei einer Eingabe der Größe n-Bits braucht der Algorithmus 2^n Rechenschritte. Der andere Algorithmus hingegen ist O(n), da er bei jedem Schritt exakt 1 Bit abarbeitet.

    0
  • Mod

    otze schrieb:

    SeppJ schrieb:

    Es wird nach jedem Durchgang exp durch zwei geteilt bis exp Null ist, daher werden ~log_2(exp) Durchläufe gemacht.

    Niemals vergessen: Es gilt nicht der eingegebene Zahlenwert für die Laufzeitberechnung, sondern die Größe der Eingabe, also wird in Bits gemessen!

    Um ganz genau zu sein ist Variante 1 deswegen O(2^n). Bei einer Eingabe der Größe n-Bits braucht der Algorithmus 2^n Rechenschritte. Der andere Algorithmus hingegen ist O(n), da er bei jedem Schritt exakt 1 Bit abarbeitet.

    Tatsächlich? Mal wieder was gelernt.

    Du hast bei der Analyse jedoch Variante 1 und 2 verwechselt.

    0
Anmelden zum Antworten