Ganzzahlige Potenz

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.

krümelkacker

wxSkip schrieb:

...

*knivel-zustimm*

Das ist nur eine ganz kompliziert aufgeschriebene Version eines eigentlich sehr simplen Algorithmus': "square and multiply".

Ein Array braucht man dafür nicht.

double pow(double base, int exp)
{
  if (exp<0) return pow(1.0/base,-exp);
  double result = 1;
  while (exp) {
    if (exp & 1) result *= base;
    base = base * base;
    exp >>= 1;
  }
  return result;
}

Aber ob das jetzt schneller als std::pow(double,int) ist, wage ich zu bezweifeln ...

Ethon

Kann eine x86 CPU nicht sowieso hardwarebeschleunig potenzieren, dh. alles Selbstgebaute ist sowieso langsamer und man sollte Insintrics nutzen?

SeppJ

Ethon schrieb:

Kann eine x86 CPU nicht sowieso hardwarebeschleunig potenzieren, dh. alles Selbstgebaute ist sowieso langsamer und man sollte Insintrics nutzen?

Nicht dass ich wüsste. Es gibt jedoch 8087-Assemblerbefehle für y*log(x) und 2^x-1, was natürlich enorm hilfreich ist. Aber die sind auch nicht gerade trivial. Also nix was nur einen Takt braucht.

Weiß nicht, ob es das auch für SSE gibt, vermutlich wird es was ähnliches geben. Aber man kann die Mathematik nicht austricksen. pow(real, real) ist keine triviale Operation, das braucht immer ordentlich Rechenaufwand.

berniebutt

Die ersten PCs hatten keinen CoProzessor für Fliesskomma (xx87) oder dieser musste für ordentlich Geld nachgerüstet werden. Ohne CoProzesor wurde alles langsam mit Emulatoren (in einer library) gemacht. Seht euch den Code dieser Emulatoren (wahrscheinlich Assembler) an und vergesst dieses Thema!

berniebutt schrieb:

Die ersten PCs hatten keinen CoProzessor für Fliesskomma (xx87) oder dieser musste für ordentlich Geld nachgerüstet werden. Ohne CoProzesor wurde alles langsam mit Emulatoren (in einer library) gemacht. Seht euch den Code dieser Emulatoren (wahrscheinlich Assembler) an und vergesst dieses Thema!

AFAIK hatten die Fließkomma-Zahl Berechnungen durch komplexe Ganz-zahl Berechnungen gelöst; heute gibt es natürlich die FPU.