3. Pottenzieren

Pottenzieren

  • 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
  • V

    otze schrieb:

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

    Es gilt die Größe für die Laufzeitberechnung, die man angibt. Die Größe der Eingabe in Bits ist da nicht unüblich. Kann sein, muß aber nicht.

    0
  • ?

    otze schrieb:

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

    Das kann man machen, wie man will. Du kannst die Laufzeit in Abhängigkeit der Eingabelänge angeben oder einfach in Abhängigkeit des Wert des Exponenten. Hauptsache, es ist klar, was gemeint ist.

    Nur für den Fall, dass das noch nicht erwähnt worden ist: Der eine Algorithmus heißt "square and multiply".

    kk

    0

  • Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...

    0
  • Mod

    DocShoe schrieb:

    Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...

    Ach, dann kann man auch noch kommen, dass jemand komplexe Exponenten will. Oder Matrixexponenten. Oder einen Tensor 15-ter Stufe über den Quaternionen. Mit einer hyperkomplexen Basis. 😃

    Lassen wir das Problem doch erstmal einfach.

    0
  • U

    DocShoe schrieb:

    Ich möchte an dieser Stelle mal einwerfen, dass der Exponent auch negativ sein darf...

    ich hab extra unsigned davor geschrieben, um deutlich zu machen, dass er das nicht sein kann(darf^^) ;P

    bb

    0
Anmelden zum Antworten