|
Реализация длинной арифметики (с использованием массивов)
Нужно реализовать операции сложения, вычитания, умножения, деления и сравнения над числами большой длины
Листинг C++
const int MaxLength = 600 + 10;
class ubig
{
public :
int a[MaxLength];
int n;
ubig (int p = 0);
ubig (char *s);
void print ();
int cmp (ubig p);
ubig operator + (ubig p);
ubig operator - (ubig p);
ubig operator * (ubig p);
ubig operator / (ubig p);
ubig operator % (ubig p);
ubig operator << (int k);
ubig operator >> (int k);
ubig last (int k);
ubig karatsuba_mul (ubig p);
int cmp (int a[], int na, int b[], int nb);
void add (int a[], int b[], int c[], int &n);
void sub (int a[], int b[], int c[], int &n);
void sub2 (int a[], int b[], int &n);
void mul (int a[], int na, int b[], int nb, int c[], int &nc);
void divmod (int a[], int na, int b[], int nb, int d[], int &nd, int r[], int &nr);
};
// begin main functions
#define delete_zero(a, na) while (na > 1 && a[na - 1] == 0) -- na;
int ubig :: cmp (int a[], int na, int b[], int nb)
{
if (na > nb) return 1;
if (nb > na) return - 1;
for (int i = na - 1; i >= 0; -- i)
{
if (a[i] > b[i]) return 1;
if (a[i] < b[i]) return - 1;
}
return 0;
}
void ubig :: add (int a[], int b[], int c[], int &n)
{
int i;
for (i = 0; i < n; ++ i)
{
c[i] += a[i] + b[i];
c[i + 1] = c[i] / 10;
c[i] %= 10;
}
delete_zero (c, n);
}
void ubig :: sub (int a[], int b[], int c[], int &n)
{
int i;
for (i = 0; i < n; ++ i)
{
c[i] += a[i] - b[i];
if (c[i] < 0)
{
-- c[i + 1];
c[i] += 10;
}
}
delete_zero (c, n);
}
void ubig :: sub2 (int a[], int b[], int &n)
{
int i;
for (i = 0; i < n; ++ i)
{
a[i] -= b[i];
if (a[i] < 0)
{
-- a[i + 1];
a[i] += 10;
}
}
delete_zero (a, n);
}
void ubig :: mul (int a[], int na, int b[], int nb, int c[], int &nc)
{
int i, j;
nc = na + nb;
for (i = 0; i < na; ++ i)
for (j = 0; j < nb; ++ j)
c[i + j] += a[i] * b[j];
for (i = 0; i < nc; ++ i)
if (c[i] >= 10)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
delete_zero (c, nc);
}
void ubig :: divmod (int a[], int na, int b[], int nb, int d[], int &nd, int r[], int &nr)
{
int i, j;
nd = na;
nr = 1;
for (i = na - 1; i >= 0; -- i)
{
if (nr != 1 || r[0] != 0)
{
for (j = nr; j > 0; -- j)
r[j] = r[j - 1];
++ nr;
}
r[0] = a[i];
while (cmp (r, nr, b, nb) >= 0)
{
++ d[i];
sub2 (r, b, nr);
}
}
delete_zero (d, nd);
delete_zero (r, nr);
}
// end
// class functions
ubig :: ubig (int p)
{
for (int i = 0; i < MaxLength; ++ i)
a[i] = 0;
n = 0;
do
{
a[n ++] = p % 10;
p /= 10;
}
while (p);
}
ubig :: ubig (char *s)
{
int i;
for (i = 0; i < MaxLength; ++ i)
a[i] = 0;
for (n = 0; s[n] != 0; ++ n);
for (i = 0; i < n; ++ i)
a[i] = s[n - i - 1] - '0';
}
void ubig :: print ()
{
for (int i = n - 1; i >= 0; -- i)
printf ("%d", a[i]);
}
int ubig :: cmp (ubig p)
{
return cmp (a, n, p.a, p.n);
}
ubig ubig :: operator + (ubig p)
{
ubig s;
s.n = max (n, p.n) + 1;
add (a, p.a, s.a, s.n);
return s;
}
ubig ubig :: operator - (ubig p)
{
ubig s;
s.n = max (n, p.n);
if (cmp (p) >= 0)
sub (a, p.a, s.a, s.n);
else
sub (p.a, a, s.a, s.n);
return s;
}
ubig ubig :: operator * (ubig p)
{
if (n + p.n < 1000)
{
ubig s;
mul (a, n, p.a, p.n, s.a, s.n);
return s;
}
else
return karatsuba_mul (p);
}
ubig ubig :: operator / (ubig p)
{
ubig s;
ubig r;
divmod (a, n, p.a, p.n, s.a, s.n, r.a, r.n);
return s;
}
ubig ubig :: operator % (ubig p)
{
ubig s;
ubig r;
divmod (a, n, p.a, p.n, s.a, s.n, r.a, r.n);
return r;
}
ubig ubig :: operator << (int k)
{
ubig s;
s.n = n + k;
for (int i = s.n - 1; i >= 0; -- i)
s.a[i] = (i >= k ? a[i - k] : 0);
return s;
}
ubig ubig :: operator >> (int k)
{
ubig s;
s.n = n - k;
for (int i = k; i < n; ++ i)
s.a[i - k] = a[i];
return s;
}
ubig ubig :: last (int k)
{
ubig s;
s.n = k;
for (short i = 0; i < k; ++ i)
s.a[i] = a[i];
return s;
}
ubig ubig :: karatsuba_mul (ubig p)
{
int k = max (n, p.n) / 2;
ubig a = (*this).last (k);
ubig b = (*this) >> k;
ubig c = p.last (k);
ubig d = p >> k;
ubig ac = a * c;
ubig bd = b * d;
ubig abcd = (a + b) * (c + d);
ubig res = ((abcd - ac - bd) << k) + (bd << (k << 1)) + ac;
return res;
}
15:20
06.08.2009
По всем вопросам обращаться: rumterg@gmail.com