Pottenzieren

unskilled

nicht überlauf-sicher, aber eine alternative zum standard-lib-pow, was keine ganzzahlen-überladung besitzt:

int my_pow(int base, unsigned 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;
}

bb

Jochen S.

Das geht aber noch einfacher mit einer for-Schleife:

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

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

    return ret_val;
}

MfG, Jochen

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

unskilled

Jochen S. schrieb:

Das geht aber noch einfacher mit einer for-Schleife:

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

bb

Pottenzieren

BasicMan01

@Potenz ... hast mal die pow in der Klasse complex oder valarray probiert?
Die sind zwar Performancetechnisch etwas langsamer, aber bevor man da anfängt, sich was eigenes zu basteln auch ne gute alternative.

Jochen S.

Das wird ein wenig schwierig mit Potenzen wie z.B. 5.5^1.2.
Den ^-Operator kannst du zum Potenzieren nicht nehmen, das ist nämlich der xor-Operator (10^4 berechnet der Compiler zu 14 und nicht zu 10000). Bei Potenzen wie z.B. 5^4 könntest du natürlich 5*5*5*5 schreiben. Der Compiler würde das dann ausrechnen.

MfG, Jochen.

Jochen S.

unskilled schrieb:

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

Ach, das wird der Compiler schon optimieren...

unskilled

Jochen S. schrieb:

unskilled schrieb:

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

Ach, das wird der Compiler schon optimieren...

aber ja - wenn die zahlen eh compile-zeit-konstanten sind, machts absolut keinen unterschied

Walnut_Burl

Schreib anstatt 5, 1 5.0f, 1.0f .

ipsec

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.

Jochen S.

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

knivil

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

SeppJ

@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.

unskilled

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

SeppJ

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.

Jochen S.

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.

SeppJ

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)

Marc-O

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

Jochen S.

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