Ganzzahlige Potenz

VollNoob

Hallo alle miteinander,

eine kurze frage: gibt es eine möglichkeit auch ganzzahlige potenzen einer zahl zu berechnen? pow( double, int ) ist dafür ja nicht so geeignet, oder???
danke schon mal im voraus

dot

Wie wärs mit dem Multiplikationsoperator (*)?

Bashar

VollNoob schrieb:

eine kurze frage: gibt es eine möglichkeit auch ganzzahlige potenzen einer zahl zu berechnen? pow( double, int ) ist dafür ja nicht so geeignet, oder???

Warum soll pow(double,int) dafür nicht geeignet sein?

VollNoob schrieb:

gibt es eine möglichkeit auch ganzzahlige potenzen einer zahl zu berechnen? pow( double, int ) ist dafür ja nicht so geeignet, oder???

Warum nicht? Die nimmt doch als Potenz ein int!

Warum ist das nicht im Standard enthalten?

(pow mit double zu int/long casten gibt Rundungsfehler, pow ausschreiben ist nur zur Compiletime möglich und ausserdem unschön (std::pow<int>(b) wäre da eleganter))

wxSkip

Das einfachste wäre eine Schleife... Ansonsten ist es effizienter, die Zahl immer zu verdoppeln bis unter die Potenz eben...

So sähe das dann optimiert aus: (Ob es in der Praxis effizienter ist, ist wieder eine andere Frage)

int GetUsedBits(unsigned int val)
{
    if(val == 0) return 0;
    int used_bits = 8 * sizeof(unsigned int) - 1;
    while(!(val & (1 << used_bits))) --used_bits;
    return used_bits + 1;

}

double uint_pow(double base, unsigned int exp)
{
    const int size = 8 * sizeof(unsigned int);
    double buffer[8 * sizeof(unsigned int)];
    int used_bits = GetUsedBits(exp);
    buffer[0] = base;
    for(int i = 1; i < used_bits; ++i) //buffer[i] = base ^ (2 ^ i)
    {
        buffer[i] = buffer[i-1] * buffer[i-1];
    }

    double product = 1.0;
    for(int i = 0; i < used_bits; ++i)
    {
        if(exp & (1 << i)) product *= buffer[i];
    }
    return product;
}

double int_pow(double base, int exp)
{
    if(exp == 0) return 1;
    else if(exp > 0) return uint_pow(base, exp);
    else return 1.0 / uint_pow(base, -exp);
}

wxSkip

Kombinierte Lösung:

int GetUsedBits(unsigned int val) //kann evtl. noch optimiert werden
{
    if(val == 0) return 0;
    int used_bits = 8 * sizeof(unsigned int) - 1;
    while(!(val & (1 << used_bits))) --used_bits;
    return used_bits + 1;

}

double uint_pow_raw(double base, unsigned int exp)
{
    const int size = 8 * sizeof(unsigned int);
    double buffer[8 * sizeof(unsigned int)];
    int used_bits = GetUsedBits(exp);
    buffer[0] = base;
    for(int i = 1; i < used_bits; ++i) //buffer[i] = base ^ (2 ^ i)
    {
        buffer[i] = buffer[i-1] * buffer[i-1];
    }

    double product = 1.0;
    for(int i = 0; i < used_bits; ++i)
    {
        if(exp & (1 << i)) product *= buffer[i];
    }
    return product;
}

double uint_pow_raw2(double base, int exp)
{
    double product = 1.0;
    for(int i = 0; i < exp; ++i)
    {
        product *= base;
    }
    return product;
}

double uint_pow(double base, unsigned int exp)
{
    return exp > 45 ? uint_pow_raw(base, exp) : uint_pow_raw2(base, exp);
}

double int_pow(double base, int exp)
{
    if(exp == 0) return 1;
    else if(exp > 0) return uint_pow(base, exp);
    else return 1.0 / uint_pow(base, -exp);
}

wxSkip schrieb:

const int size = 8 * sizeof(unsigned int);
    double buffer[size];

Was ist das denn für eine Sprache?

Ansonsten wäre für dich vielleicht die binäre Exponentiation interessant. Die macht prinzipiell das gleiche wie du, nur ohne VLA-Buffers.

wxSkip schrieb:

const int size = 8 * sizeof(unsigned int);
    double buffer[size];

Obwohl das eine Compile-Zeit Konstante ist, ist das verdammt hässlich. (Und so auch IB)

wxSkip

Hab mir schon überlegt, ob ich std::array (C++11) verwenden soll, aber ich fand diesen Workaround nicht so schlimm (Schließlich ist das kein VLA und der Compiler hat an der Konstante auch auf hoher Warnstufe nichts zu meckern. (Ich habe schon überlegt, CHAR_BIT einzubauen, das war mir dann aber zu viel.)

@Hacker: Was meinst du mit IB?

wxSkip schrieb:

Hab mir schon überlegt, ob ich std::array verwenden soll, aber ich fand diesen Workaround nicht so schlimm (Schließlich ist das kein VLA und der Compiler hat an der Konstante auch auf hoher Warnstufe nichts zu meckern. (Ich habe schon überlegt, CHAR_BIT einzubauen, das war mir dann aber zu viel.)

@Hacker: Was meinst du mit IB?

Laut pumuckl erlaubt das so nur eine Erweiterung des GCC.

wxSkip

Okay, habs jetzt umeditiert (Und: nein, keine Makros, sondern hässliche Redundanz).

knivil

Was soll eigentlich die ganze Sache mit den Arrays? Fuer mich sieht es nach premature optimization aus.

knivil schrieb:

Was soll eigentlich die ganze Sache mit den Arrays? Fuer mich sieht es nach premature optimization aus.

Was zum Teufel hat denn das mit Premature Optimization zu tun? Das ist einfach eine Selbstverständlichkeit und hat mit etwas nachdenken bevor man etwas tut zu tun (schließlich wählst du ja auch nicht einfach so einen std::vector, sondern überlegst welcher Container für deine Zwecke am effizientesten ist (greifst du oft auf Elemente zu, die in der Mitte sind? Fügst du oft Elemente ein?...) damit du nicht immer deinen ganzen Code umschreiben musst).

knivil

Laber Rhabarber. Du hast nicht verstanden. Warum braucht es ein Array, um eine ganzzahlige Potenz zu berechnen?

Ethon

Hacker schrieb:

wxSkip schrieb:

Hab mir schon überlegt, ob ich std::array verwenden soll, aber ich fand diesen Workaround nicht so schlimm (Schließlich ist das kein VLA und der Compiler hat an der Konstante auch auf hoher Warnstufe nichts zu meckern. (Ich habe schon überlegt, CHAR_BIT einzubauen, das war mir dann aber zu viel.)

@Hacker: Was meinst du mit IB?

Laut pumuckl erlaubt das so nur eine Erweiterung des GCC.

Quatsch, das ist definitiv eine Compilezeitkonstante, damit darf man Arrays erzeugen.

Hacker schrieb:

knivil schrieb:

Was soll eigentlich die ganze Sache mit den Arrays? Fuer mich sieht es nach premature optimization aus.

Was zum Teufel hat denn das mit Premature Optimization zu tun? Das ist einfach eine Selbstverständlichkeit und hat mit etwas nachdenken bevor man etwas tut zu tun (schließlich wählst du ja auch nicht einfach so einen std::vector, sondern überlegst welcher Container für deine Zwecke am effizientesten ist (greifst du oft auf Elemente zu, die in der Mitte sind? Fügst du oft Elemente ein?...) damit du nicht immer deinen ganzen Code umschreiben musst).

Ich denke, er meinte eher den ganzen Code.
Würde mal messen, um wie viel das schneller ist als

double uint_pow(double base, unsigned int exp)
{
   double result = base;
   for(unsigned i = 2; i < exp; ++i)
       result *= base;
   return result;
}

double int_pow(double base, int exp)
{
    if(exp == 0) return 1;
    else if(exp > 0) return uint_pow(base, exp);
    else return 1.0 / uint_pow(base, -exp);
}

Edit: Habe es mit 100.000.000 durchläufen getestet, der Exponent immer zwischen 0 und 49 (zufällig), die Basis immer 2. Ergebnis war dass die primitive Variante geringfügig schneller ist. (6.509s vs 6.459s)

Tachyon

Für sehr große Zahlen im Cryptobereich wird oft sowas in der Art genommen:

int ipow(int base, int exp)
{
    int result = 1;
    for(; exp; exp >>= 1)
    {
        (exp & 1) && (result *= base);
        base *= base;
    }
    return result;
}

Edit: Achso, die Basis soll ja FP sein. Okay, dann eben nicht.

berniebutt

double d1=1.5,d2;
int    ip=2;
d2 = pow(d1,ip);

Sollte für d2 etwas anderes als 2.25 herauskommen, müssen wir weiter nachdenken!

SeppJ

Ethon schrieb:

Edit: Habe es mit 100.000.000 durchläufen getestet, der Exponent immer zwischen 0 und 49 (zufällig), die Basis immer 2. Ergebnis war dass die primitive Variante geringfügig schneller ist. (6.509s vs 6.459s)

Dann ist das Ergebnis nicht, dass das zweite schneller ist, sondern dass beide gleich schnell sind.

Ethon

SeppJ schrieb:

Ethon schrieb:

Edit: Habe es mit 100.000.000 durchläufen getestet, der Exponent immer zwischen 0 und 49 (zufällig), die Basis immer 2. Ergebnis war dass die primitive Variante geringfügig schneller ist. (6.509s vs 6.459s)

Dann ist das Ergebnis nicht, dass das zweite schneller ist, sondern dass beide gleich schnell sind.

Mit einer 0 mehr wächst der Unterschied bereits auf knapp 200ms.
Obwohl ich denke dass eine Menge Zeit für random draufgeht.