3. Reihe berechnen nur mit Arithmetik und Logik

Reihe berechnen nur mit Arithmetik und Logik

  • ?

    Stimmt. Dann würde ich es wahrscheinlich so machen:
    map (\n -> sum [1/(2*x+1)^2 | x <- [0..n]]) [0, 1, 2, 530947]

    Also für so etwas sind funktionale Sprachen wirklich gut. Btw.: Welche Sprache ist denn deine, Michael E.?

    0
  • M

    Ruby. Ich muss schon sagen: Deins ist hübsch 🙂 Irgendwann beschäftige ich mich auch mal mit Haskell...

    0
  • ?

    Ruby.

    Ruby? 😮 Das hätte ich jetzt nicht erwartet.

    Deins ist hübsch 🙂 Irgendwann beschäftige ich mich auch mal mit Haskell...

    Ja, ich stecke auch noch ganz am Anfang, aber Haskell (oder funktionale Sprachen im Allgemeinen) ist schon faszinierend. Kann ich nur empfehlen.

    0
  • Mod

    Dieses kleine Juwel darf natürlich auch nicht fehlen:

    #include <iostream>

template<unsigned n> double sum()
{
  return sum<n-1>() + 1./((2*n+1)*(2*n+1));
}

template<> double sum<0>()
{
  return 1.;
}

int main()
{
  std::cout << "0: " << sum<0>() << '\n'
       << "1: " << sum<1>() << '\n'
       << "2: " << sum<2>() << '\n'
       << "530947: " << sum<530947>() << '\n';

}

    Funktioniert für Testfälle einwandfrei. Der Fall mit 530947 compiliert bei mir seit 5 Minuten. Spezielle Compileroptionen sind nötig, um die Rekursionstiefe zu erhöhen. Ich melde mich noch einmal wenn das Übersetzen erfolgreich war (falls mir der Speicher nicht vorher überläuft - der Prozess belegt bereits 200 MB).

    edit: Nach über einer Stunde und einem halben Gigabyte Speicherverbrauch ist der Compiler immer noch nicht fertig. Ich breche die Sache mal ab, da ich keine Lust habe, dass über Nacht eventuell wichtige Prozesse wegen Speichermangels beendet werden. Wenn jemand einen flotten Rechner mit reichlich RAM rumstehen hat, kann er ja mal ausprobieren, wie lange die Übersetzung braucht. Würde mich jedenfalls sehr interessieren.

    0
  • B

    Für den msvc hab ich den Schalter nicht gefunden. mingw hört nach einer halben Stunde ohne Meldung einfach auf. Mit welchem Compiler/Optionen hast du es probiert.

    0
  • Mod

    brotbernd schrieb:

    Für den msvc hab ich den Schalter nicht gefunden. mingw hört nach einer halben Stunde ohne Meldung einfach auf. Mit welchem Compiler/Optionen hast du es probiert.

    Mit g++. Der meldet einem quasi sofort, dass die maximale Rekursionstiefe (500) erreicht wurde und dass man diese mit -ftemplate-depth-NN erhöhen kann.

    Wenn ich 10000 als Templateargument nehme, dauert das Compilieren bei mir so um die 10-20 Sekunden. Aber ich habe das Gefühl, dies geht nicht linear hoch. 20000 ist schon im niedrigen Minutenbereich. Und das ist immer noch ein Faktor 25 kleiner als der gewünschte Parameter. Vermutlich muss man dafür wirklich mal einen Rechner über Nacht stehen lassen.

    Wie lange braucht eigentlich die Haskellversion?

    0
  • B

    -ftemplate-depth-NN hatte ich bei mingw gesetzt. hörte trotzdem einfach auf. Naja, spielerei... 🙂

    0
  • Mod

    brotbernd schrieb:

    -ftemplate-depth-NN hatte ich bei mingw gesetzt. hörte trotzdem einfach auf. Naja, spielerei... 🙂

    Vielleicht Speicher voll? Der Compiler belegt bei der Aktion ganz schön viel.

    0
  • B

    waren noch über 7gb frei 😉

    0
  • P

    SeppJ schrieb:

    Dieses kleine Juwel darf natürlich auch nicht fehlen:

    Oder gleich komplett mit Template-Metaprogrammierung, d.h. alles zur Compilezeit berechnet (ungetestet, mangels Compiler, bei dem die Tiefe einstellbar ist):

    #include <iostream>
typedef unsigned long ul;

//metatyp fuer rationale Zahlen
template <ul zaehler, ul nenner> struct rational; 

//Metafunktionen
template <ul z, ul n> struct kuerzen;       //ergebnis: rational
template <ul a, ul b> struct ggt;           //ergebnis: ul
template <class LHS, class RHS> struct add; //ergebnis: rational, falls LHS, RHS rational 
template <class T> struct to_double;        //ergebnis: double, falls T rational
template <ul n> struct accum;               //ergebnis: rational

//to_double fuer rational
template <ul z, ul n>
struct to_double<rational<z,n> > { static double value; };
template <ul z, ul n>
double to_double<rational<z,n> >::value = (1.*z)/n;

//add fuer rational
template <ul zLHS, ul nLHS, ul zRHS, ul nRHS>
struct add<rational<zLHS, nLHS>, rational<zRHS, nRHS> >
{
  typedef typename kuerzen<zLHS*nRHS+zRHS*nLHS, nLHS*nRHS>::type type;
};

//kuerzen eines bruches. ergebnis: rational
template <ul z, ul n>
struct kuerzen
{
  typedef rational<z/ggt<n,z>::value, n/ggt<n,z>::value> type;
};

//groesster gemeinsamer teiler. 
template <ul a>
struct ggt<a, 0ul>
{
  const static ul value = a;
};
template <ul a, ul b>
struct ggt
{
  const static ul value = (b>a) ? ggt<a, b%a>::value
                                : ggt<b, a%b>::value;
};

//aufsummieren der Reihe
template <>
struct accum<0>
{
  typedef rational<1ul,1ul> type;
};
template <ul n>
struct accum
{
  const static ul mm = (2*n+1)*(2*n+1);
  typedef typename add<typename accum<n-1>::type, 
              rational<1,mm> >::type type;
};

int main()
{
  using namespace std;
  cout << to_double<accum<530947>::type>::value << endl;
}

    als "normales" Programm sähe das so aus:

    #include <iostream>
typedef unsigned long ul;

//typ fuer rationale Zahlen
struct rational
{
  ul zaehler;
  ul nenner;
};

rational kuerzen(ul z, ul n);
ul ggt(ul a, ul b);
rational add(rational lhs, rational rhs);
double to_double(rational t);
rational accum(ul n);

double to_double(rational t)
{
  return (1.*t.zaehler)/t.nenner;
}

rational add(rational lhs, rational rhs)
{
  return kuerzen(lhs.zaehler*rhs.nenner + rhs.zaehler*lhs.nenner, lhs.nenner*rhs.nenner);
}

rational kuerzen(ul z, ul n)
{
  rational erg;
  erg.zaehler = z/ggt(n,z);
  erg.nenner = n/ggt(n,z);
  return erg;
}

ul ggt(ul a, ul b)
{
  if (b==0) return a; //(template-Spezialisierung)

  return (b>a) ? ggt(a, b%a) : ggt(b, a%b);
}

rational accum(ul n)
{
  if (n==0) //(template-Spezialisierung)
  {
    rational eins = {1ul, 1ul};
    return eins;
  }
  rational summand;
  summand.zaehler = 1;
  summand.nenner = (2*n+1)*(2*n+1);
  return add(accum(n-1), summand);
}

int main()
{
  using namespace std;
  cout << to_double(accum(530947)) << endl;
}

    edith meint, dass das aber vermutlich irgendwo auf Überläufe stoßen wird 😞

    0
Anmelden zum Antworten