3. Contest #1: Fibonacci Zahlen

Contest #1: Fibonacci Zahlen

  • W

    Benchmark: Fibonacci-Zahlen zwischen 0 bis 10^1000 ausgeben:

    #include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <ctime>

template<typename T> std::string ToString(T const &in)
{
    std::ostringstream stream;
    stream << in;
    return stream.str();
}

class StringInt
{
    std::string val;

    std::string RemovePendingZeros(std::string const &in);

    public:
    StringInt(int p_val);
    StringInt(std::string p_val);

    StringInt &operator+=(StringInt const &second);
    bool operator==(StringInt const &second);
    bool operator<(StringInt const &second);
    bool operator>(StringInt const &second);

    friend std::ostream &operator<<(std::ostream &stream, StringInt const &val);
};

std::ostream &operator<<(std::ostream &stream, StringInt const &val)
{
    stream << val.val;
    return stream;
}

StringInt::StringInt(int p_val)
  : val(ToString(p_val))
{
}

StringInt::StringInt(std::string p_val)
  : val(RemovePendingZeros(p_val))
{
}

std::string StringInt::RemovePendingZeros(std::string const &in)
{
    size_t first_nonzero = in.find_first_not_of('0');
    if(first_nonzero < in.size()) return in.substr(first_nonzero);
    else return "0";
}

StringInt &StringInt::operator+=(StringInt const &second)
{
    size_t filled_size = std::max(val.size(), second.val.size()) + 1;

    val = std::string(filled_size - val.size(), '0') + val;
    std::string val_2 = std::string(filled_size - second.val.size(), '0') + second.val;

    std::string::reverse_iterator iter_1 = val.rbegin(), iter_2 = val_2.rbegin();

    bool has_add_carry = false;

    for(; iter_1 != val.rend() && iter_2 != val_2.rend(); ++iter_1, ++iter_2)
    {
        int sum = (*iter_1 - '0') + (*iter_2 - '0') + has_add_carry;
        *iter_1 = '0' + sum % 10;
        has_add_carry = sum / 10;
    }

    val = RemovePendingZeros(val);  //remove pending zeros
    return *this;
}

bool StringInt::operator==(StringInt const &second)
{
    return val == second.val;
}

bool StringInt::operator<(StringInt const &second)
{
    size_t filled_size = std::max(val.size(), second.val.size());
    std::string val_2;

    if(filled_size != val.size()) val = std::string(filled_size - val.size(), '0') + val;
    val_2 = std::string(filled_size - second.val.size(), '0') + second.val;

    bool result = val < val_2;
    val = RemovePendingZeros(val);
    return result;
}

bool StringInt::operator>(StringInt const &second)
{
    return !(*this < second) && !(*this == second);
}

template<typename T> void print_fibs_between(T min, T max)
{
    T first_var = 0, second_var = 1;

    while(second_var < max)
    {
        if(second_var > min) std::cout << second_var << "\n";
        first_var += second_var;
        std::swap(first_var, second_var);
    }
}

clock_t wxSkip()
{
    StringInt min = std::string("0"), max = "1" + std::string(1000, '0');
    clock_t start = clock();
    print_fibs_between(min, max);
    return clock() - start;
}

uint32_t const base=1000000000;
size_t const baseMinusOneLen=9;

struct AddResult {
    uint32_t lo;
    bool carry;
};

AddResult add(uint32_t a,uint32_t b,bool carry)
{
    AddResult result;
    result.lo=a+b+carry;
    result.carry=0;
    if(result.lo>=base) {
        result.lo-=base;
        result.carry=1;
    }
    return result;
}

void fiboAddAssign(std::vector<uint32_t>& a,std::vector<uint32_t> const& b)
{
    assert(a.size()==b.size() || a.size()==b.size()-1);
    bool carry=0;
    for(size_t i=0; i!=a.size(); ++i) {
        AddResult r=add(a[i],b[i],carry);
        a[i]=r.lo;
        carry=r.carry;
    }
    if(a.size()!=b.size()) {
        AddResult r=add(*b.rbegin(),0,carry);
        a.push_back(r.lo);
        carry=r.carry;
    }
    if(carry) {
        a.push_back(carry);
    }
}

void fiboWrite(std::vector<uint32_t> const& a)
{
    using namespace std;
    char oldFill=cout.fill('0');
    auto pos=a.rbegin();
    cout<<*pos;
    ++pos;
    while(pos!=a.rend()) {
        cout<<setw(baseMinusOneLen)<<*pos;
        ++pos;
    }
    cout<<'\n';
    cout.fill(oldFill);
}

std::vector<uint32_t> fiboRead(std::string digits)
{
    using namespace std;
    vector<uint32_t> result;
    reverse(digits.begin(),digits.end());
    while(digits.size()%baseMinusOneLen!=0) {
        digits.append("0");
    }
    for(size_t i=0; i!=digits.size(); i+=baseMinusOneLen) {
        int32_t digit=0;
        for(int j=baseMinusOneLen-1; j>=0; --j) {
            digit=digit*10+digits[i+j]-'0';
        }
        result.push_back(digit);
    }
    return result;
}

bool fiboLess(std::vector<uint32_t> const& a,std::vector<uint32_t> const& b)
{
    if(a.size()<b.size()) {
        return true;
    }
    if(a.size()>b.size()) {
        return false;
    }
    size_t i=a.size();
    do {
        --i;
        if(a[i]!=b[i]) {
            return a[i]<b[i];
        }
    } while(i!=0);
    return false;
}

bool fiboLessOrEqual(std::vector<uint32_t> const& a,std::vector<uint32_t> const& b)
{
    return !fiboLess(b,a);
}

clock_t volkard()
{
    using namespace std;
    vector<uint32_t> a;
    a.push_back(0);
    vector<uint32_t> b;
    b.push_back(1);
    vector<uint32_t> lowerBound=fiboRead("0");
    vector<uint32_t> upperBound=fiboRead("1" + std::string(1000, '0'));
    clock_t start = clock();
    while(fiboLessOrEqual(a,lowerBound)) {
        fiboAddAssign(a,b);
        a.swap(b);
    }
    while(fiboLess(a,upperBound)) {
        fiboWrite(a);
        fiboAddAssign(a,b);
        a.swap(b);
    }
    return clock() - start;
}

int main()
{
    clock_t first = wxSkip(), second = volkard();
    std::cout << "wxSkip ticks: " << first << "\nvolkard ticks: " << second << "\n";
}

    Output:
<sehr viele Zahlen>
wxSkip ticks: 6250
volkard ticks: 26979

    Tja, volkard: C-Style-Funktionen, umständlich, länger und langsamer... 🙄

    0
  • 3

    Der Sieger steht im Startpost - Glückwunsch. 🙂

    0
  • W

    Och, wenn du willst, kann ich auch noch ein paar Zeichen weghauen...

    0
  • W

    So, ein wenig Krempel weg, und die Situation ist umgekehrt:

    #include <string>
#include <iostream>

class StringInt
{
    std::string val;

    std::string RemovePendingZeros(std::string const &in);

    public:
    StringInt(std::string p_val);

    StringInt &operator+=(StringInt const &second);
    bool operator==(StringInt const &second);
    bool operator<(StringInt const &second);
    bool operator>(StringInt const &second);

    friend std::ostream &operator<<(std::ostream &stream, StringInt const &val);
};

std::ostream &operator<<(std::ostream &stream, StringInt const &val)
{
    stream << val.val;
    return stream;
}

StringInt::StringInt(std::string p_val)
  : val(RemovePendingZeros(p_val))
{
}

std::string StringInt::RemovePendingZeros(std::string const &in)
{
    size_t first_nonzero = in.find_first_not_of('0');
    if(first_nonzero < in.size()) return in.substr(first_nonzero);
    else return "0";
}

StringInt &StringInt::operator+=(StringInt const &second)
{
    size_t filled_size = std::max(val.size(), second.val.size()) + 1;

    val = std::string(filled_size - val.size(), '0') + val;
    std::string val_2 = std::string(filled_size - second.val.size(), '0') + second.val;

    std::string::reverse_iterator iter_1 = val.rbegin(), iter_2 = val_2.rbegin();

    bool has_add_carry = false;

    for(; iter_1 != val.rend() && iter_2 != val_2.rend(); ++iter_1, ++iter_2)
    {
        int sum = (*iter_1 - '0') + (*iter_2 - '0') + has_add_carry;
        *iter_1 = '0' + sum % 10;
        has_add_carry = sum / 10;
    }

    val = RemovePendingZeros(val);
    return *this;
}

bool StringInt::operator==(StringInt const &second)
{
    return val == second.val;
}

bool StringInt::operator<(StringInt const &second)
{
    size_t filled_size = std::max(val.size(), second.val.size());
    std::string val_2;

    if(filled_size != val.size()) val = std::string(filled_size - val.size(), '0') + val;
    val_2 = std::string(filled_size - second.val.size(), '0') + second.val;

    bool result = val < val_2;
    val = RemovePendingZeros(val);
    return result;
}

bool StringInt::operator>(StringInt const &second)
{
    return !(*this < second) && !(*this == second);
}

template<typename T> void print_fibs_between(T min, T max)
{
    T first = std::string("0"), second = std::string("1");

    while(second < max)
    {
        if(second > min) std::cout << second << "\n";
        first += second;
        std::swap(first, second);
    }
}

int main()
{
    std::string min, max;
    std::cin >> min >> max;
    print_fibs_between(StringInt(min), StringInt(max));
}

    The file wxSkip contains 2033 non-space characters.
    0
  • W

    Diese character-Bewertung ist IMHO völlig unsinnig. Man könnte jetzt genausogut alle Bezeichner auf 1 Buchstabe reduzieren, Templates entfernen, den ostream-Operator<< direkt reincoden usw.

    P.S.: Ich schreibe gerade einen variablen Tokenizer - wenn ich den fertig habe (vielleicht eine Woche noch), könnte ich ihn euch evtl. mit einer C++-Konfiguration und anderen kleinen Abänderungen für die Wettbewerbe zur Verfügung stellen. (oder ihr macht da gleich einen eigenen Wettbewerb draus)

    0
  • V

    wxSkip schrieb:

    Tja, volkard: C-Style-Funktionen,

    Klar. Eine C++-Klasse würde dann diese oder ähnliche Funktionen wrappen.

    wxSkip schrieb:

    umständlich,

    Die Zahlendarstellung rechnet eben schnell, dafür wird sie langsam angezeigt. Daß das nicht so klar wird, wie eine Ziffer pro Arrayelement, habe ich in Kauf genommen. Das war die Einsendung für die Abstimmung. An einem Contest für den kürzesten Code habe ich nicht teilgenommen.

    wxSkip schrieb:

    länger

    Ja, die Ausgabe hat ganz schön reingehauen.

    wxSkip schrieb:

    und langsamer...

    Sie sollte schneller werden, wenn nur ein paar Zahlen bestellt werden, aber viel vorher hochgerechnet werden muß.

    Aber bei mir ist sie überraschenderweise nicht mal soo viel langsamer. Vielleicht mußt Du die Optimierungen noch anmachen?

    localhost testcpp # g++ -O3 -std=c++0x -march=native main.cpp
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 50000
volkard ticks: 50000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 50000
volkard ticks: 50000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 50000
volkard ticks: 50000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 40000
volkard ticks: 60000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 40000
volkard ticks: 60000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 40000
volkard ticks: 50000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 40000
volkard ticks: 60000
localhost testcpp # ./a.out > /mnt/gentoo/test.txt && tail -n 2 /mnt/gentoo/test.txt 
wxSkip ticks: 50000
volkard ticks: 50000
    0
  • 3

    Was meint denn volkard zur Bewertung?

    0
  • W

    Stimmt, das mit dem Rechnen vs. Ausgeben ist eine Frage der Eingabe.

    Wenn ich in eine Datei schreibe, kommt folgendes heraus:

    wxSkip ticks: 157
volkard ticks: 182

    Mir ist allerdings schleierhaft, warum. Man sollte doch annehmen, dass das eigentliche Ausgeben des Strings auf der Konsole bei beiden Funktionen gleich lange braucht und deshalb von den Ticks eine konstante Zeit abgezogen werden müsste, was das Verhältnis nur noch vergrößern würde.

    EDIT: Bei Zahlen zwischen 10^1000 und 10^1500 gewinnst du. Aber nur in der Datei. 😉

    0
  • V

    Wenn ich zwischen 1e10000 und 2e10000 mache, kommt folgendes raus:

    volkard@localhost ~/src/testcpp $ ./a.out | tail -n 2
wxSkip ticks: 3890000
volkard ticks: 90000
    0
  • W

    volkard schrieb:

    Wenn ich zwischen 1e10000 und 2e10000 mache, kommt folgendes raus:

    volkard@localhost ~/src/testcpp $ ./a.out | tail -n 2
wxSkip ticks: 3890000
volkard ticks: 90000

    Das sind auch nur 4-5 Zahlen. (Das andere Extrem der Skala)

    P.S.: Was hast denn du für ein clock()? Rundet das auf 10000-er?

    0
  • V

    314159265358979 schrieb:

    Was meint denn volkard zur Bewertung?

    Ich dachte, Werner sollte noch die Kleinigkeit ändern dürfen. Und dann ab zur Abstimmung. Die drei Ensendungen sind ja quasi alle Quatsch und spannen die Ecken des gerade noch Sinnvollen auf. Wäre interessant, wie sich das Publikum da platziert.

    Für Codelängenvergleich sollten nur Tokens gezählt werden. Das ist viel Arbeit. Naja, viel weniger Arbeit, wenn die Einsendungen auf Codelänge optimiert sind.

    0
  • V

    wxSkip schrieb:

    P.S.: Was hast denn du für ein clock()? Rundet das auf 10000-er?

    Keine Ahnung, was der Quatsch soll.
    Aber das werde ich jetzt nicht reparieren, morgen kommt das letzte Teil für den neuen Rechner.

    0
  • 3

    volkard schrieb:

    314159265358979 schrieb:

    Was meint denn volkard zur Bewertung?

    Ich dachte, Werner sollte noch die Kleinigkeit ändern dürfen. Und dann ab zur Abstimmung. Die drei Ensendungen sind ja quasi alle Quatsch und spannen die Ecken des gerade noch Sinnvollen auf. Wäre interessant, wie sich das Publikum da platziert.

    Für Codelängenvergleich sollten nur Tokens gezählt werden. Das ist viel Arbeit. Naja, viel weniger Arbeit, wenn die Einsendungen auf Codelänge optimiert sind.

    Geht in Ordnung, also Abstimmung? Was soll denn abgestimmt werden?

    0
  • V

    314159265358979 schrieb:

    Da hier im Forum (meiner Meinung nach) etwas Abwechslung fehlt, möchte ich gerne regelmäßig eine Art "Contest" machen.

    Jeder soll in einem gewissen Zeitrahmen ein Programm zur Lösung einer Aufgabe schreiben. Danach wird von den Usern abgestimmt, welches den Contest gewinnt. Es soll das eleganteste Programm bewertet werden, Performance ist nebensächlich.
    Die Abstimmung findet nach der Deadline statt, ihr dürft nicht für euer eigenes Programm stimmen. (wäre ja langweilig 😉 )

    0
  • 3

    Wenn dir diese Definition von elegant reicht, okay 🙂

    0
  • K

    Hmm...
    Es hat ja gar keiner ausgenutzt, dass

    fib(a-1)*fib(b-1) + fib(a)*fib(b) = fib(a+b-1)

    gilt. Damit müsste man die Suche nach dem Anfang beschleunigen können. Also, bei extrem hohen Zahlen, müsste sich das lohnen -- zumindest dann, wenn man die Multiplikation auch effizient implementiert.

    Wer will denn mal den Fibonacci-Iterator, der hier gezeigt wurde, dahingehend erweitern, so dass folgendes funktioniert:

    fibiter a;  for (int i=0; i< 7; ++i) ++a;
fibiter b;  for (int i=0; i<11; ++i) ++b;
fibiter c = indexsum(a,b);
cout << *a << endl; // gibt fib( 7) aus
cout << *b << endl; // gibt fib(11) aus
cout << *c << endl; // gibt fib(18) aus

    ?

    indexsum kann man mit 4 Multiplikationen und 3 Additionen implementieren wenn der Iterator nur ein Paar von aufeinanderfolgenden Fibonaccizahlen speichert. Ich bin ja auch fast geneigt, indexsum nach operator+ umzubennennen, im Sinne der Indizes.

    🙂

    0
  • V

    krümelkacker schrieb:

    Hmm...
    Es hat ja gar keiner ausgenutzt, dass

    fib(a-1)*fib(b-1) + fib(a)*fib(b) = fib(a+b-1)

    gilt. Damit müsste man die Suche nach dem Anfang beschleunigen können. Also, bei extrem hohen Zahlen, müsste sich das lohnen.

    Daran gedacht hatte ich schon. Aber ich sah auch, daß nur die letzte Addition viel kostet. Die vorletzte nur noch 61% davon. Und die davor nur (61%)² davon. Geometrische Reihe. EIne so schnell schrumpende Reihe hat auch nur eine winzige Summe, vielleicht drei- oder viermal den größen Wert. Aber das war ein Denkfehler. Die Werte schrumfen so schnell. Die Stellenzahlen schrumpfen viel langsamer und anders.

    Also mal genauer schludern:
    Unter Vernachlässigung von "wenn man die Multiplikation auch effizient implementiert."

    Φ sei der goldene Schnitt mit 1.618...
    fib(n) ist für große n ungefähr Φ^n.
    fib(n) hat ungefähr 0.21*n Stellen.

    Ohne Deinen Trick:
    So viele Ziffern muß ich addieren für fib(256):
    0.21*1 + 0.21*2 + 0.21*3 + ... + 0.21*256 = 0.21 * 256*257/2 = 6908

    Mit Deinem Trick: fib(128) hat ungefähr 26 Stellen. Mit Schulbuchmultiplikation bräuchte ich ungefähr 26*26 Additionen, sind 576. Du sagst, man brauch 4 davon. 576*4=2304. Und fib(128) zuz bauen, wäre 0.21 * 128*129/2=1733, zusammen 4037.

    Also 40% Einsaprung. Und wenn ich gerade nicht schief gucke, hängen sind überlebenden Ausdrücke proportional zum Quadrat der Stellenzahl, also auch zum Quadrat von n.

    Also konstant 40% Einsparung, interessanterweise nicht "Also, bei extrem hohen Zahlen, müsste...".

    So ist der Trick also noch nichts wert. Ich glaube, man mußte den Trick auch rekursiv machen UND sowas wie die Karatsuba-Multiplikation nehmen, um in eine bessere Komplexitätsklasse zu fallen.

    0
  • K

    Ich hatte das nicht nachgerechnet. Aber mein Gefühl sagte mir, dass das ohne optimierte Multiplikation knapp werden könnte...

    Lass mich mal überlegen ... Wie aufwändig ist es, aus einem Paar von aufeinanderfolgenden Fibonaccizahlen mit jeweils n Stellen ein Paar mit jeweils 2n Stellen zu erzeugen?

    Methode 1 ("Immer nur aufaddieren"):
    Mit Überschlagen komme ich hier auf einen Aufwand von O(n^2)

    Methode 2 ("Trick"):
    1 Addition (n-stellig + n-stellig = n-stellig)
    4 Multiplikationen (zwei n-stellige Zahlen --> 2n-stellige Ergebnisse)
    2 Additionen (2n-stellig + 2n-stellig = 2n-stellig)
    Alle Additionen sind hier in O(n) berechnebar. Die Multiplikationen aber mit O(n^1.58...) für Karatsuba und O(n*log(n)*log(log(n))) für Schönhage-Strassen. Also, insgesamt per Karatsuba sind's hier O(n^1.585) Operationen.

    => Bei genügend großem n ist der "Trick" unter Verwendung von Karatsuba (oder besser) schneller.

    Richtig?

    0
  • V

    krümelkacker schrieb:

    => Bei genügend großem n ist der "Trick" unter Verwendung von Karatsuba (oder besser) schneller.

    Richtig?

    Wenn man sie die vorher benötigten n-stelligen nicht per Iterator besorgt.
    Ich fürchte, sich n-stellige per Iterator zu besorgen, kostet bereits 25% der Zeit, die man für 2-n-stellig per Iterator bezahlen müßte.

    krümelkacker schrieb:

    Wie aufwändig ist es, aus einem Paar von aufeinanderfolgenden Fibonaccizahlen mit jeweils n Stellen ein Paar mit jeweils 2n Stellen zu erzeugen?

    Ja, das flutscht.

    Mal angenommen, die Stellenzahl des Paares würde sich immer genau verdoppeln.
    Das wirft die kleine Frage auf, wie wir ein Paar 61-stelliger Zahlen erzeugen.
    Hmm, man kann ja immer, weil man eh Paare hat, auch das Folgepaar bauen.
    1 2 3 6 7 14 15 30 60 61
    Ja, geht locker. Sogar mit der Garantie, daß mindestens jeder zweite Schritt ein Multiplizier-Schritt mit Stellenverdopplung ist. Ja, das flutscht.

    0
  • W

    Was wird der nächste Contest? Ein Sudoku-Solver? Und wo steckt eigentlich Werner Salomon?

    Kriterien?
    -Lesbarkeit (Abstimmung)
    -Schönheit (Abstimmung)
    -Kürze (Tokens)
    -Performance
    -Ein Mix (Abstimmung)
    -Unleserlichkeit

    0
Anmelden zum Antworten