begrenzte größe von datentypen

f0rc3

hallo leute!
hoffentlich habe ich den titel richtig gewählt. mein problem ist folgendes: eine aufgabe von meiner ausbildung besteht darin, hohe potenzen von zahlen auszurechnen. also z.B.: 2^128. allerdings ist kein datentyp in der lage die komplette zahl zu fassen. welche möglichkeit habe ich, diese aufgabe zu lösen?

schon mal vielen dank

volkard

f0rc3 schrieb:

hallo leute!
hoffentlich habe ich den titel richtig gewählt. mein problem ist folgendes: eine aufgabe von meiner ausbildung besteht darin, hohe potenzen von zahlen auszurechnen. also z.B.: 2^128. allerdings ist kein datentyp in der lage die komplette zahl zu fassen. welche möglichkeit habe ich, diese aufgabe zu lösen?

schon mal vielen dank

Einen Langzahltyp selber schreiben. Im einfachsten Fall ein Array of char mit den Ziffern drin.
Und eine Addierfunktion schreiben, die zwei solche Arrays addieren kann.
Und das in eine 128-er Schleife packen.

Falls es nicht um 2^128, sondern um 2^128%17 geht, kannste bei Mini-Zahlen bleiben, indem bei jedem Zwischenergebnis schon %17 ausgeführt wird.

knivil

Oder aber eine Bibliothek nutzen wie gmp.

f0rc3

erst einmal vielen dank für die schnellen antworten. wie gehe ich da vor wenn ich einen eigenen langzahltyp schreiben will? das scheint mir auch für zukünftige projekte ganz sinnvoll zu sein.

_matze

Auf codeproject.com gibt's solche Klassen auch, z.B. die hier:

http://www.codeproject.com/KB/cpp/lint.aspx

Keine Ahnung, ob die gut ist, ich habe sowas noch nie gebraucht. Jedenfalls gibt es genug Implementationen im Internet, falls du es nicht selbst machen willst.

volkard

Ich habe eine alte Funktion gefunden, die eine solche Zahl verdoppelt.

class BigNum
{
private:
	u8 *data;
	size_t len;
	size_t size;
...
	void dup()
	{
		u8 carry=0;
		for(size_t i=0;i<len;++i)
		{
			data[i]*=2;
			data[i]+=carry;
			if(data[i]<10)
			{
				carry=0;
			}
			else
			{
				data[i]-=10;
				carry=1;
			}
		}
		if(carry)
		{
			if(len==size)
				grow(2*size);
			data[len]=1;
			++len;
		}
	}
...
	void printAt(ostream &out)
	{
		size_t i=len-1;
		do
		{
			out<<char('0'+data[i]);
		}while(i--);
	}