3. Contest #1: Fibonacci Zahlen

Contest #1: Fibonacci Zahlen

  • W

    Gibt's auch eine Auswertung?

    0
  • 3

    Gibt doch keine Lösung bisher, was soll ich denn da auswerten?

    0
  • W

    314159265358979 schrieb:

    Gibt doch keine Lösung bisher, was soll ich denn da auswerten?

    Meine?

    0
  • V

    314159265358979 schrieb:

    Gibt doch keine Lösung bisher, was soll ich denn da auswerten?

    Ich dachte, ich habe Dir über's Profil eine Lösung geschickt.

    0
  • 3

    Ups, ganz übersehen, sorry. 🤡
    Poste sie einfach hier in den Thread.

    0
  • 3

    @volkard: dann hätte ich eine email, oder?
    Bekommen habe ich keine.

    0
  • W

    Also gut:

    #include <string>
#include <iostream>
#include <sstream>

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);
    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);
    }
}

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

    P.S.: Hast du meine E-Mail in deinem Postfach gesehen? (das war der gleiche Code)

    0
  • 3

    Ah ich seh schon, ich hab hier meine andere Email Addy eingetragen, wo ich selten reinsehe. Ist beides angekommen. 🙂

    0
  • W

    314159265358979 schrieb:

    Ah ich seh schon, ich hab hier meine andere Email Addy eingetragen, wo ich selten reinsehe.

    Wozu gibt es E-Mail-Clients wie Thunderbird?

    0
  • V
     

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

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()
{
	using namespace std;
	vector<uint32_t> result;
	string digits;
	if(!(cin>>digits)) {
		throw "A deamon arises and mourns \"All your nose are belong to us.\"";
	}
	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);
}

int main ()
{
	using namespace std;
	vector<uint32_t> a;
	a.push_back(0);
	vector<uint32_t> b;
	b.push_back(1);
	vector<uint32_t> lowerBound=fiboRead();
	vector<uint32_t> upperBound=fiboRead();
	while(fiboLessOrEqual(a,lowerBound)) {
		fiboAddAssign(a,b);
		a.swap(b);
	}
	while(fiboLess(a,upperBound)) {
		fiboWrite(a);
		fiboAddAssign(a,b);
		a.swap(b);
	}
}
    0
  • 3

    Hab die Addy da nicht eingetragen, da normalerweise Spam-Mail 🤡

    0
  • 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
Anmelden zum Antworten