Bignum

Z 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 typu danych całkowitoliczbowych (short, int, long long int) nie wystarczą.

Dodawanie stringów

string add_int(string &A, string &B)
{
	int i,j,n,suma,p;
 
	p = 0; n=0;
	i = A.length()-1;
	j = B.length()-1;
 
	n = (i>j) ? i : j;
	string s( n + 1 , ' ');
 
	while (i>=0 && j>=0)
	{
		suma = A[i]-'0' +  B[j]-'0' +  p;
		s[n--] = suma%10 + '0';
		p = suma/10;
		i--; j--;
	}
 
	while (i>=0)
	{
		suma = A[i]-'0' +  p;
		s[n--] = suma%10 + '0';
		p = suma/10;
		i--;
	}
 
	while (j>=0)
	{
		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
{
	int i,j,n,suma,p;
 
	if (A.compare(B)==0) 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;
	}
	p = 0; n=0;
	i = A.length()-1;
	j = B.length()-1;
 
	n = i;
	string s( n + 1 , ' ');
 
	while (i>=0 && j>=0)
	{
		suma = A[i]-'0' -  (B[j]-'0') -  p;
		s[n--] = (suma+10)%10 + '0';
		p = (suma<0) ? 1 : 0;
		i--; j--;
	}
 
	while (i>=0)
	{
		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 uproszeczenia zakładam, że d jest małe, tzn. 2 <= d <= 9

Osobiste