C++ Biginteger effizienter machen

[datalukas]

Hallo liebe Community,

da ich viel mit Project Euler arbeite und man dafür teilweise auch sehr große Zahlen benötigt, und es mit VC++ etwas schwierig ist, für die aktuelle Version passende Bibliotheken zu finden, habe ich mir (auch aus Übungszwecken) mal selber eine Biginteger-Bibliothek geschrieben, die alle Methoden enthält, die ich bis jetzt brauchte (ist also bei weitem nicht vollständig).
Am Beispiel von Problem 25 bei Project Euler wird aber klar, wie langsam diese Umsetzung arbeitet. Die Bruteforce-Lösung dauert wahrscheinlich eine halbe Stunde (hab es nicht ganz durchrechnen lassen bis jetzt):

#include "stdafx.h"
#include <iostream>
#include "Biginteger.h"


int _tmain(int argc, _TCHAR* argv[])
{
	vector<Biginteger> fibonacci(2);
	fibonacci[0] = 1;
	fibonacci[1] = 1;
	while (fibonacci[1].getSize() < 1000)
	{
		fibonacci.push_back(fibonacci[1] + fibonacci[0]);
		fibonacci.erase(fibonacci.begin());
	}
	system("Pause");
	return 0;
}

Die dafür nötigen Funktionen:
Add (per übeladenem +-Operator aufgerufen):

Biginteger Biginteger::add(Biginteger firstsummand, Biginteger secondsummand)
{
	Biginteger sum;
	sum.setSize(firstsummand.getSize() > secondsummand.getSize() ? firstsummand.getSize() : secondsummand.getSize()); //Summe die Größe des größeren Summanden zuweisen
	for (int i = 0; i < (firstsummand.getSize() > secondsummand.getSize() ? firstsummand.getSize() : secondsummand.getSize()); i++) //Schleife läuft bis zur letzten Ziffer des größeren Summanden
	{
		if (i >= (firstsummand.getSize() < secondsummand.getSize() ? firstsummand.getSize() : secondsummand.getSize())) //Falls i größer als der kleiner Summand ist wird, bekommt sum einfach die Ziffern des größeren zugewiesen
		{
			sum[i] += firstsummand.getSize() > secondsummand.getSize() ? firstsummand[i] : secondsummand[i];
		}
		else //Ansonsten werden jeweils die Ziffern zusammengezählt
		{
			sum[i] += firstsummand[i] + secondsummand[i];
		}
		if (sum[i] >= 10) //Zehnerstelle merken, falls das Ergebnis größer als 10 ist
			carryAddMul(i, sum);
	}
	return sum;
}

carryAddMul (für das "Merken von Ziffern"):
 void Biginteger::carryAddMul(int position, Biginteger& number)
{
	if (number.getSize() <= position + 1) //Testen, ob number groß genug ist
		number.push_back(0);
	number[position + 1] += number[position] / 10;		 //Höherer Ziffer den Zehntel des gegebenen Wertes zuweisen
	number[position] -= (number[position] / 10) * 10;	//Zweite Ziffer der niederwertigen Ziffer entfernen
	if (number[position + 1] >= 10)						//Testen, ob höherwertige Ziffer mehr als eine Stelle hat
		carryAddMul(position + 1, number);				//rekursiv aufrufen, um die Stelle auf die jeweils höherwertige Ziffer zu übertragen
}

Zugrunde liegt der vector "digits" als Klassenvariable:

void Biginteger::setValue(vector<int> value)
{
	digits = value;
}

Wie kann man den Algorithmus noch verbessern?
Außerdem könnt ihr ruhig auch Verbesserungsvorschläge für den allgemeinen Programmierstil geben (Bezeichnungen, Algorithmen etc.).
Falls es jemanden interessiert, könnt ihr im Anhang die gesamte Bibliothek finden.

Abgesehen davon habe ich noch eine Frage zum Thema Programmiererfahrung. Im Moment bin ich 17, also in meiner Entscheidungsphase. Empfohlen werden ja hauptsächlich Aufgaben wie die bei Project Euler, aber fehlen hier für die Arbeit an einem kleinen Projekt, was hier auch oft zur Übung empfohlen wird, nicht noch "handfeste" Dinge wie die Kommunikation mit dem Betriebssystem oder GUI-Entwicklung?
Welche Dinge könnte man noch lernen, die einem den klassischen Programmieralltag näherbringen (dass das Studium sehr mathematisch und theoretisch ist, ist mir bewusst)?

Gruß
Datalukas

 

[Arzaiel]

Also auf den ersten flüchtigen Blick würde ich sagen, dass es bestimmt effizienter ist, deine BigIntegers dual und nicht dezimal abzuspeichern. Das spart Speicherplatz und du könntest duale Operationen benutzen, welche sich um einiges schneller durch spezielle Prozessor-Befehle bewerkstelligen lassen.

 

[Flup]

Nur mal ein paar Punkte zu deiner Add-Funktion:

- Warum eine extra Funktion? Definier doch gleich damit die Addition mit einen + -> operator+
- Du änderst die übergeben Parameter nicht -> Call-by-Reference
- ++i statt i++ in der Schleife
- Nicht bei jedem for das komplette Statement auswerten lassen sondern nur einmal berechnen
- Für dein Carry reicht ein simples static flag

 

[|FAT|Punisher]

https://gmplib.org

 

[daemon777]

Es geht doch um einen not-bruteforce-Algorithmus dachte ich

Die Fibonacci-Folge lässt sich wesentlich einfacher berechnen, wenn man die Eigenwerte/Eigenvektoren der Vorschrift berechnet. Da diese aber bekannt sind kann man sich diesen Schritt auch fast schon sparen.
Jedenfalls lässt sich mit solchen Mitteln die Laufzeit ziemlich drücken (Ergebnis lässt sich fast direkt berechnen).

 

[asdfman]

Tom St.Denis hat ein Buch über seine Bibliothek (libtommath) geschrieben, in dem er ihr Design im Detail erklärt. Dabei hat er besonders auf Performance wert gelegt.
Google hat eine Leseprobe, die vielleicht bei einer Kaufentscheidung hilfreich sein könnte.

http://books.google.de/books?id=dHOsq2TD_v8C

 

[Jiub]

Ich finde das Buch von Stroustrup The C++ Programming Language (C++11) sehr gut. Da lernt man dann auch CodeDesign und nicht "C mit Klassen" wie es sonst sehr üblich ist.
Ohne genau hinzuschauen, nehme ich auch stark an, dass dein + Operator ein copy und kein move constructor ist. Das wird auch schon eine Menge ausmachen..

 

[antred]

Ohne genau hinzuschauen, nehme ich auch stark an, dass dein + Operator ein copy und kein move constructor ist.

Wie meinst du das denn?

 

[datalukas]

Danke für die Antworten bis jetzt zunächst mal!
@Arzaiel Dauerhaft würde ich mir dann evtl. überlegen, sowas zu machen.
@deamon777 Ja, ich weiß, dass es eine viel schnellere Lösung für dieses Problem gibt. Jetzt ging es aber erst mal um die Performance der Biginteger-Bibliothek.

Nur mal ein paar Punkte zu deiner Add-Funktion:
- Du änderst die übergeben Parameter nicht -> Call-by-Reference

Ist Call by Reference schneller? Eigentlich muss doch eine Funktion, die den +-Operator ändert, einen Wert zurückliefern, dadurch muss dieser nicht geändert werden, oder?

- Nicht bei jedem for das komplette Statement auswerten lassen sondern nur einmal berechnen

Meinst du sowas in der Hinsicht:

Biginteger operator+ (const Biginteger& firstsummand, const Biginteger& secondsummand)
{
	Biginteger sum;
	Biginteger larger = firstsummand.getSize() > secondsummand.getSize() ? firstsummand : secondsummand;
	sum.setSize(larger.getSize());
	for (int i = 0; i < larger.getSize(); ++i)
	{
		if (i >= (firstsummand.getSize() < secondsummand.getSize() ? firstsummand.getSize() : secondsummand.getSize()))
		{
			sum[i] += larger[i];
		}
		else
		{
			sum[i] += firstsummand.at(i) + secondsummand.at(i);
		}
		if (sum[i] >= 10)
			Biginteger::carryAddMul(i, sum);
	}
	return sum;
}

Was du mit dem static-Flag meinst, ist mir nicht ganz klar. Meinst du das Schlüsselwort static?

 

[antred]

Zu deinen Operatoren hätte ich ein paar Dinge zu sagen, hier mal am Beispiel von operator + . Normalerweise macht man das so, daß man ein mal die Logik im operator += ausdefiniert und dann operator + per Aufruf von operator += bewerkstelligt. Ich benutze in dem Beispiel mal die Kürzel lhs (left hand side, linksseiter Operand) und rhs (right hand side, rechtsseiter Operand).

// Zusätzliche at-Implementierung für const-Zugriffe, die für Indizes >= digits.size() einfach 0 liefert. Erspart uns in operator +=
// einen if-else-Tanz.
int Biginteger::at(int position) const
{
	if (position >= digits.size())
	{
		return 0;
	}

	return digits[position];
}

// Die kanonische Form für operator+= sollte eine Referenz, keinen Wert, zurückgeben, damit chaining wie erwartet funktioniert.
Biginteger& Biginteger::operator += (const Biginteger& rhs)
{
	// Größe des größeren der beiden Operanden ermitteln.
	// Für std::max den <algorithm> Header inkludieren.
	const int maxSize = std::max(rhs.getSize(),this->getSize());

	if (this->getSize() < maxSize)
	{
		this->setSize(maxSize);
	}
	
	for (int i = 0; i < maxSize; i++)
	{
		(*this)[i] += rhs.at(i);
		
		if ((*this)[i] >= 10)
		{
			carryAddMul(i, *this);
		}
	}
	return *this;
}

Biginteger operator+ (const Biginteger& lhs, const Biginteger& rhs)
{
	// Nun für operator+ einfach bereits vorhandenen operator+= nutzen.
	Biginteger result( lhs );
	result += rhs;
        return result;
}

Ich hoffe mal, ich habe da jetzt auf die Schnelle keinen dummen Fehler eingebaut.

Des weiteren solltest du mehr auf const-correctness achten. getSize(), getValue(), equalsone() könnten alle const sein, da sie die Biginteger-Instanz, an der sie aufgerufen werden, nicht verändern.

Deine setSize() und getSize()-Methoden sollten auch eher std::size_t als int verwenden (genau wie die Container aus der STL das auch tun).

Die ganzen add(), substract(), etc. Methoden würde ich auch rausschmeißen und direkt mit den Operatoren arbeiten.

Ergänzung (28. Oktober 2014)

Noch was. Wenn in deinem Programm viele temporäre Biginteger-Objekte erstellt werden, kann die Tatsache, daß jede Biginteger-Instanz einen std::vector im Bauch hat, eventuell ein Performance-Problem darstellen, da jeder vector intern eine new-Allokierung nutzt und new/delete recht kostspielig ist.
Da gibt es diverse Ansätze, die man verfolgen kann, um das Problem abzumildern.

1. Du könntest einen move constructor für Biginteger implementieren.
2. Du könntest für den vector einen anderen allocator als std::allocator verwenden. Zum Beispiel einen stack allocator, der sich aus einem bereits vorhandenen Stackbereich bedient ... das ist allerdings ein sehr fortgeschrittenes Thema, was du nur angehen solltest, wenn sich die Performance als unakzetabel erweist.
3. Du könntest deine Berechnungen so formulieren, daß dabei möglichst wenige temporaries entstehen.

Hinweis zum letzten Punkt:

Biginteger a = ...
Biginteger b = ...
Biginteger c = ...

// Hier entstehen 2 vermeidbare temporaries (erst eine aus dem Term a + b; dann eine weitere aus Result_von_a_plus_b * c).
Biginteger result = ( a + b ) * c;

// Weniger schön aber eventuell effizienter da ohne temporaries:
Biginteger result = a;
result += b;
result *= c;

 

[convexus]

int8_t anstelle von int sollte etwas an Geschwindigkeit bringen. Dadurch reduzierst du den Speicherbedarf und in der Konsequenz kann der Cache besser arbeiten. int8_t ist im Header cstdint enthalten.

 

[daemon777]

Das mit dem int8_t leuchtet mir jetzt noch nicht ein. Der hat ja auch nur eine Breite von 8bit, was mir jetzt für eine Bigint-Klasse nicht der richtige Weg zu sein scheint. Ein Vielfaches von 8bit passt doch genauso gut in den Cache und ich habe weniger Arbeit, um Overflows zu behandeln.

 

[antred]

Das mit dem int8_t leuchtet mir jetzt noch nicht ein. Der hat ja auch nur eine Breite von 8bit, was mir jetzt für eine Bigint-Klasse nicht der richtige Weg zu sein scheint. Ein Vielfaches von 8bit passt doch genauso gut in den Cache und ich habe weniger Arbeit, um Overflows zu behandeln.

Er meint, daß die interne Datenhaltung statt vector<int> besser mit vector<int8_t> geschehen sollte. Jedes vector-Element repräsentiert ja hier eh bloß eine Ziffernposition (also 10 verschiedene Werte).

 

[convexus]

@antred, daemon:Ja, genau das meinte ich.

Ohne Gewähr eine auf die Fibonacci-Aufgabe bezogene Source. Der Quellcode enthält nur die für Fibonacci erforderlichen Funktionalitäten und implementíert auch einen Bruteforce-Ansatz. Laufzeit ist auf meinem System in Sekundenbereich. Damit will ich nicht angeben, sondern nur das Einsparpotential aufzeigen.

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;


typedef vector<int8_t> Biginteger;


namespace { // anonymer namespace 

	inline Biginteger& add_helper(Biginteger& x, const Biginteger& y) {
		// Voraussetzung: x.size() >= y.size() !!
		int carry = 0;
		size_t n=y.size();
		for (size_t i = 0; i < n; ++i) {
			int8_t z = carry+x[i]+y[i];
			carry = z / 10;
			x[i] = z%10;
		}
		
		size_t m = x.size();
		while(n < m && carry!=0) {
			x[n] = (x[n]+carry) % 10;
			carry = (x[n]+carry)/10;
                        ++n;
		}
		if(carry) 
			x.push_back(1);
		return x;
	}
}

Biginteger operator+ (const Biginteger& lhs, const Biginteger& rhs) {
	if(lhs.size() >= rhs.size()) {
		Biginteger result(lhs);
		return add_helper(result, rhs);
	}
	else {
		Biginteger result(rhs);
		return add_helper(result, lhs);
	}
}

int main() {
	Biginteger fib0({1});
	Biginteger fib1({1});
	int nbr = 2;
	while(fib1.size() < 1000) {		
		Biginteger tmp =  fib0 + fib1;
		fib0.swap(fib1);
		fib1 = tmp;
		++nbr;
	}
	
	cout << "Erste Fibinacci-Zahl mit >= 1000 Stellen ist die Nummer :" << nbr << endl;
	for(int j=fib1.size()-1; j>=0; --j)
		cout << static_cast<char>(fib1[j]+'0');
	cout << endl;
	
	return 0;
}

 

[disassembler]

Och ich hab mich schon auf intensives Profilen gefreut, aber jetzt weiß ich nicht wo das Problem liegt, denn bei mir läuft das Programm von datalukas äußerst schnell durch, auch bei abgeschalteten Compileroptimierungen:
mit -O0
real 0m0.293s
user 0m0.291s
sys 0m0.000s
mit -O3
real 0m0.046s
user 0m0.044s
sys 0m0.001s
Alles weniger als eine Sekunde, von einer halben Stunde weit entfernt. Und mein Core 2 Q6600 ist jetzt auch nicht gerade die ultimative Rennmaschine. Deswegen: Kopfzerbrechen über Performance Optimierungen abgebrochen aufgrund akkuten Mangels von Langsamkeit...

Ich hoffe der Fehler liegt nicht darin, dass das Programm von datalukas keinerlei Ausgabe hat und er dann wegen system("PAUSE") vergeblich auf das Ende seines Programms wartete, obwohl der Prozessor längst Däumchen drehte.

 

[daemon777]

Er meint, daß die interne Datenhaltung statt vector<int> besser mit vector<int8_t> geschehen sollte. Jedes vector-Element repräsentiert ja hier eh bloß eine Ziffernposition (also 10 verschiedene Werte).

Ich hab mir den Code jetzt nicht angeguckt, aber sollte das so sein, dann ist das doch sowieso die ineffizienteste Art eine Big-Integer-Klasse zu schreiben. Viel besser wäre es doch einen möglichst großen Datentyp zu nutzen, um dann nicht mehr so viel selbst rumrechnen zu müssen.

 

[datalukas]

Da muss ich mich korrigieren, bei mir geht es so auch ziemlich schnell. Ich habe nur Zwischenergebnisse per cout anzeigen lassen und hätte nicht damit gerechnet, dass die das ganze so extrem in die Länge ziehen.
Zur Optimierung:
Ich werde mir das nun mal genauer anschauen, nachdem ich in der letzten Zeit nicht dazu gekommen bin. Also Vielen Dank für die Verbesserungsmöglichkeiten!

 

[datalukas]

Hab mich jetzt mal ein bisschen mit der Move-Semantik beschäftigt. Mir ist aber nicht ganz klar, wie ich das auf das Beispiel übertragen soll. So was in der Art wäre jetzt mein Ansatz für einen move constructor, ist aber wahrscheinlich nicht vollständig, da hier ja kein Speicher frei wird. Bei den ganzen Beispielen waren die Klassenvariablen Pointer, bei dieser Klasse habe ich aber einen vector.

Biginteger::Biginteger(Biginteger&& number)
{
	digits = number.getValue();
}

Move-Assignement:

Biginteger& Biginteger::operator=(Biginteger&& number)
{
	digits = number.getValue();
	return *this;
}

Würde evtl. noch std::move etwas bringen?

 

[antred]

Würde evtl. noch std::move etwas bringen?

So is'es.

 

[Miuwa]

Da du intern bereits einen vektor zur verwaltung der Daten nutzt kannst du einfach die default Copy/Move - Konstruktor/Assignemnt operatoren verwenden, die der Compiler automatisch für dich anlegt. Deine manuelle Implementierung ist also unnötig. Move ist übrigens auch das Standardverhalten für den Rückgabewert.