Bignum

Z RNO-Wiki
(Różnice między wersjami)
(Zmiana systemu z dziesiętnego na d)
m (Arytmetyka długich liczb)
Linia 1: Linia 1:
 
== Arytmetyka długich liczb ==
 
== 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.
 
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ą.
+
Oczywiste jest, że standardowe typy danych całkowitoliczbowych (short, int, long long int) nie wystarczą.
  
 
==Dodawanie stringów==
 
==Dodawanie stringów==

Wersja z 09:27, 3 kwi 2009

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 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 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;
	int r;
	string q, w, tmp;
	while (true)
	{
		// tmp = number / d ;  r = number % d
		tmp = ""; 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;
}
Osobiste