Bignum

RNO-Wiki

Spis treści

Arytmetyka długich liczb

W tym artykule omówimy artytmetykę długich liczb. Czyli jak zrealizować podstawowe operacje arytmetyczne na dość długich liczbach, np. 1000 cyfrowych. Oczywiste jest, że standardowe typy danych całkowitoliczbowych (short, int, long long int) nie wystarczą.

Dodawanie stringów

string add_int(string &A, string &B)
{
	int p = 0;
	int i = A.length()-1;
	int j = B.length()-1;
 
	int n = (i>j) ? i : j;
	string s( n + 1 , ' ');
 
	while (i>=0 && j>=0)
	{
		int suma = A[i]-'0' +  B[j]-'0' +  p;
		s[n--] = suma%10 + '0';
		p = suma/10;
		i--; j--;
	}
 
	while (i>=0)
	{
		int suma = A[i]-'0' +  p;
		s[n--] = suma%10 + '0';
		p = suma/10;
		i--;
	}
 
	while (j>=0)
	{
		int suma = B[j]-'0' +  p;
		s[n--] = suma%10 + '0';
		p = suma/10;
		j--;
	}
 
	if (p==1) s.insert(0,"1");
	return s;
}

Odejmowanie

To działa tylko tylko dla liczb bez znaku. 

// Rafał Nowak (http://www.rafalnowak.pl)
string sub_int(string &A, string &B) // returns A-B
{
	if (A == B) return "0";
	if (A.length()<B.length() || (A.length()==B.length() && A<B))
	{
		string s = sub_int(B,A);
		s.insert(0,1,'-'); // wstawia z przodu literę '-' ;  s = "-"+s
		return s;
	}
	int p = 0;
	int i = A.length()-1;
	int j = B.length()-1;
 
	int n = i;
	string s( n + 1 , ' ');
 
	while (i>=0 && j>=0)
	{
		int suma = A[i]-'0' -  (B[j]-'0') -  p;
		s[n--] = (suma+10)%10 + '0';
		p = (suma<0) ? 1 : 0;
		i--; j--;
	}
 
	while (i>=0)
	{
		int suma = A[i]-'0' -  p;
		s[n--] = (suma+10)%10 + '0';
		p = (suma<0) ? 1 : 0;
		i--;
	}
 
	while (s[0]=='0' && s.length()>1) s.erase(0,1); // usuwamy wiodące zera
	return s;
}

Zmiana systemu z dziesiętnego na d

Dla uproszczenia zakładam, że d jest małe, tzn. 2 <= d <= 9. Uwaga: z poniższego programu można łatwo wyciągnąć algorytm realizacji operacji dzielenia i modulo. 

string convert(string number, int d) // 2 <= d <= 9
{
	if (d==10) return number;
	string w;
	while (true)
	{
		// tmp = number / d ;  r = number % d
		string tmp; int r = 0;
		bool zero=true;
		for (int i=0; i<number.size(); i++)
		{
			int l = number[i]-'0' + 10*r;
			if ( !zero || l/d != 0 )
			{
				tmp.push_back('0'+l/d);
				zero = false;
			}
			r = l%d;
		}
		w.push_back('0'+r);
		if (zero) break;
		number = tmp;
	}
	reverse(w.begin(), w.end());
	return w;
}
Źródło: "http://www.rafalnowak.pl/wiki/index.php?title=Bignum"