Bignum

Z RNO-Wiki
(Różnice między wersjami)
m (Odejmowanie)
Linia 4: Linia 4:
  
 
==Dodawanie stringów==
 
==Dodawanie stringów==
 
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
 
string add_int(string &A, string &B)
 
string add_int(string &A, string &B)
Linia 48: Linia 44:
 
}
 
}
 
</source>
 
</source>
</td>
 
<td width="140" align="center">
 
<adsense
 
adclient="pub-2033664350513674"
 
adslot="5958906648"
 
adwidth="120"
 
adheight="600"
 
/>
 
</td>
 
</tr>
 
</table>
 
  
 
==Odejmowanie==
 
==Odejmowanie==
 
To działa tylko tylko dla liczb bez znaku.
 
To działa tylko tylko dla liczb bez znaku.
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
 
// Rafał Nowak (http://www.rafalnowak.pl)
 
// Rafał Nowak (http://www.rafalnowak.pl)
Linia 105: Linia 87:
 
}
 
}
 
</source>
 
</source>
</td>
+
 
<td width="140" align="center">
+
==Zmiana systemu z dziesiętnego na d==
<adsense
+
Dla uproszeczenia zakładam, że d jest małe, tzn. 2 <= d <= 9
adclient="pub-2033664350513674"
+
adslot="5958906648"
+
adwidth="120"
+
adheight="600"
+
/>
+
</td>
+
</tr>
+
</table>
+

Wersja z 09:22, 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 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