3. Endlosschleife beim Potenzrechnen

Endlosschleife beim Potenzrechnen

  • M

    oh ja danke.
    Vermutlich habe ich mir dieses zu oft angeschaut.

    Viele Grüße
    MM

    0
  • U

    so?

    template<int expo>
double power(int basis)
{ 
    switch(expo) 
    { 
        case -1: 
            return 1.0 / basis; 
        case 1: 
            return basis; 
        case 0:
            return 1.0; 

        default:
            if(i < 0)
              return power<expo+1>(basis) * (1.0/basis);
            else
              return power<expo-1>(basis) * basis; 
    } 
}

    bb

    0
  • S

    Das ist irgendwie nix halbes und nix ganzes. So würde man die Funktion schreiben, wenn sie KEIN Template wäre. Sie ist es aber (aus irgendeinem Grund). Wenn ich also power<50> benutzen will, generiert der Compiler auch alle anderen Funktionen power<N> für 0<=N<=50. Wie Banane ist das? Außerdem müsste man mal testen, ob der durchschnittliche Compiler so schlau ist, das ganze switch/case Zeug zu eliminieren. expo ist ja zur Compilezeit bekannt. Um da auf Nummer sicher zu gehen und die Zahl der zu instanziierenden Templates zu reduzieren könnte man es so machen:

    #include <iostream>

template<int Power, int Case>
struct powr { // Fall Power>0 und Power gerade
  static inline double doit(double base) {
    return powr<(Power/2),((Power/2)%2)>::doit(base*base);
  }
};
template<int Power>
struct powr<Power,1> { // Fall Power>0 und Power ungerade
  static inline double doit(double base) {
    return powr<(Power/2),((Power/2)%2)>::doit(base*base)*base;
  }
};
template<int Power>
struct powr<Power,-1> { // Fall Power<0
  static inline double doit(double base) {
    return 1.0/powr<(-Power),((-Power)%2)>::doit(base);
  }
};
template<int Case>
struct powr<0,Case> { // Fall Power==0
  static inline double doit(double base) {
    return 1.0;
  }
};

template<int Expo>
double power(double base) {
  return powr<Expo,( Expo<0 ? -1 : Expo%2 )>::doit(base);
}

int main()
{
	std::cout << power<5>(2) << '\n';
}

    (Square-And-Multiply Algorithmus)

    Wenn hier power<50> aufgerufen wird, werden nur powr<50,0>, powr<25,1>, powr<12,0>, powr<6,0>, powr<3,1>, powr<1,1>, powr<0,0> instanziiert.

    Gruß,
    SP

    0
  • M

    Sebastian Pizer du bist Freund der theo. Inf. richtig?

    Der Square-And-Multiply Algorithmus kommt mir noch schwer bekannt vor 😉

    Viele Grüße
    MM

    0
  • U

    MrMilk schrieb:

    Sebastian Pizer du bist Freund der theo. Inf. richtig?

    Der Square-And-Multiply Algorithmus kommt mir noch schwer bekannt vor 😉

    Viele Grüße
    MM

    Ich hab mich auch scho ab und an gefragt^^

    pizer.wordpress.com/about/ schrieb:

    Me: I studied computer science (MSc) with an emphasis on models, algorithms and math. I learned a lot about digital signal processing and data compression over the past 10 years (mostly self-tought).

    Blog: This blog is about programming, DSP, math, etc. Stuff you can’t talk about with your neighbour or most real-life friends.

    mehr hab ich dann aber auch nicht gefunden 😉

    bb

    0
  • M

    Hallo,

    da mir die Lösung von SP ganz gut gefällt, habe ich ich einmal dazu entschlossen sie nach zu programmieren. Allerdings mit der Änderung, dass keine Funktionen genutzt werden, da ich später den Wert innerhalb einer Struktur benötige. Bis jetzt ist folgendes herausgekommen:

    template
<
	int Basis,
	int Expo
>
struct Power
{
	static const double value = (Expo %2 == 1)?
			(
				Basis * Power <Basis,(Expo < 0)? Expo+1: Expo-1>::value
			)
			:
			(
				Power<Basis, Expo/2>::value * Power<Basis, Expo/2>::value
			);
};

template
<
	int Basis
>
struct Power<Basis, 0>
{
	static const double value = 1.0;
};

template
<
	int Basis
>
struct Power<Basis,-1>
{
	static const double value = Basis;
};

template
<
	int Basis
>
struct Power<Basis, 1>
{
	static const double value = Basis;
};

template
<
	int Basis,
	int Expo
>
struct power_
{
	static const double value = (Expo < 0)?  (1.0/ Power<Basis, Expo>::value) : (Power<Basis, Expo>::value) ;

};

    Leider bekomme ich etwas vom Compiler auf die Ohren, sobald ich folgendes aufrufe:

    cout << power_<2,3>::value << endl;

    Und zwar mit dieser Fehlermeldung:

    Undefined symbols:
    "power_<2, 3>::value", referenced from:
    __ZN6power_ILi2ELi3EE5valueE$non_lazy_ptr in BaTest.o
    ld: symbol(s) not found
    collect2: ld returned 1 exit status

    Könnt ihr mir hier weiterhelfen?

    Viele Grüße
    MM

    0
  • V

    Klappt denn

    double x=power_<2,3>::value;
cout << x << endl;

    ?

    0
  • M

    Ne, leider auch nicht bekomme hier ebenfalls:

    Undefined symbols:
    "power_<2, 3>::value", referenced from:
    __ZN6power_ILi2ELi3EE5valueE$non_lazy_ptr in Test.o

    Viele Grüße
    MM

    0
  • Mod

    Da scheinen mir die Definitionen deiner statischen Datenmember zu fehlen.

    0
  • S
     

    struct foo{
  static const int blah = 3;
}

    ...ist nur eine Deklaration von blah und keine Definition. Es wird also nirgens Speicher dafür angelegt. Für "konstante Ganzzahltypen" (integral types) wird aber eine "Initialisierung" in der in-class Deklaration erlaubt. Solange nur der Wert von blah benutzt wird und zB nicht die Adresse von blah benötigt wird, ist auch keine Definition von blah nötig.

    Bei Dir soll value aber vom Typ double sein. Für double gilt die Ganzzahltypen-Sonderregel natürlich nicht.

    Das folgende Programm wird gnädigerweise vom G++ (3.4.5) erfolgreich, auch ohne Linker-Fehler, übersetzt:

    #include <iostream>

template<int Base, int Power>
struct powr
{
   static const double value =
      powr<(Base*Base),(Power/2)>::value
    * powr<      Base ,(Power%2)>::value;
};

template<int Base>
struct powr<Base,1>
{
   static const double value = Base;
};

template<int Base>
struct powr<Base,0>
{
   static const double value = 1.0;
};

template<int Base>
struct powr<Base,-1>
{
   static const double value = 1.0/Base;
};

int main()
{
  double const x = powr<2,3>::value;
  std::cout << x << '\n';
}

    Es ist aber nicht Standard-konform. Der Comeau C/C++ Online-Compiler sagt dazu folgendes:

    Comeau C/C++ 4.3.10.1 (Oct  6 2008 11:28:09) for ONLINE_EVALUATION_BETA2
Copyright 1988-2008 Comeau Computing.  All rights reserved.
MODE:strict errors C++ C++0x_extensions

"ComeauTest.c", line 6: error: a member of type "const double" cannot have an
          in-class initializer
     static const double value =
                               ^

"ComeauTest.c", line 14: error: a member of type "const double" cannot have an
          in-class initializer
     static const double value = Base;
                               ^

"ComeauTest.c", line 20: error: a member of type "const double" cannot have an
          in-class initializer
     static const double value = 1.0;
                               ^

"ComeauTest.c", line 26: error: a member of type "const double" cannot have an
          in-class initializer
     static const double value = 1.0/Base;
                               ^

4 errors detected in the compilation of "ComeauTest.c".

    Recht hat er.

    Warum schreibst Du nicht einfach std::pow(2,3)? Der GCC rechnet das, soweit ich weiß, trotzdem zur Compilezeit aus. Dieses Verhalten wird zwar nicht vom C++ Standard garantiert, zeichnet aber einen guten Compiler meiner Meinung nach aus.

    Gruß,
    SP

    P.S: Ja, ich habe Informatik mit Schwerpunkt "Modelle & Algorithmen" studiert.

    0
Anmelden zum Antworten