|
Длинная целочисленная арифметика на динамических массивах
Необходимо реализовать основные операции над длинными числами. Сами числа представить динамическими массивами цифр.
Листинг C++
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
#define forp(i, a, b, c) for (i = (a); (c) > 0 ? i <= (b) : i >= (b); i += (c))
#define forn(i, n) forp (i, 0, (n) - 1, 1)
#define form(i, n) forp (i, (n) - 1, 0, - 1)
#define forv(it, v) for (it = (v).begin (); it != (v).end (); ++ it)
#define uint long long
//--------------------- Defines ------------------------------------------------
#define sint int
#define vsint vector < sint >
#define sz size ()
#define at(v, i) (0 <= (i) && (i) < (v).size () ? v[i] : 0)
#define erase_null(v) while ((v).size () > 1 && (v).back () == 0) (v).pop_back ();
#define next_mod(v, i) if (0 <= (i) + 1 && (i) + 1 < (v).size ()) \
{\
v[(i) + 1] += v[(i)] / 10;\
v[(i)] %= 10; \
}
//--------------------- Shifts, Compare ----------------------------------------
vsint shift_left (vsint s, int k)
{
if (k <= 0) return s;
s.insert (s.begin (), k, 0);
return s;
}
vsint shift_right (vsint s, int k)
{
if (k <= 0) return s;
s.erase (s.begin (), s.begin () + min (k, (int)s.sz));
return s;
}
int cmp (vsint &a, vsint &b)
{
for (int i = max (a.sz, b.sz) + 1; i >= 0; -- i)
{
if (at (a, i) > at (b, i)) return 1;
if (at (a, i) < at (b, i)) return - 1;
}
return 0;
}
//--------------------- Add, Sub, Mul, Div -------------------------------------
vsint add (vsint &a, vsint &b)
{
vsint c (max (a.sz, b.sz) + 1, 0);
for (int i = 0; i < c.sz - 1; ++ i)
{
c[i] += at (a, i) + at (b, i);
next_mod (c, i);
}
erase_null (c);
return c;
}
vsint sub (vsint &a, vsint &b)
{
vsint c (a.sz, 0);
for (int i = 0; i < c.sz; ++ i)
{
c[i] += at (a, i) - at (b, i);
if (c[i] < 0 && i + 1 < c.sz)
{
c[i] += 10;
-- c[i + 1];
}
}
erase_null (c);
return c;
}
void sub_from (vsint &a, vsint &b)
{
for (int i = 0; i < a.sz; ++ i)
{
a[i] -= at (b, i);
if (a[i] < 0 && i + 1 < a.sz)
{
a[i] += 10;
-- a[i + 1];
}
}
erase_null (a);
}
vsint mul (vsint &a, vsint &b)
{
vsint c (a.sz + b.sz + 2, 0);
for (int i = 0; i < a.sz; ++ i)
if (a[i])
for (int j = 0; j < b.sz; ++ j)
if (b[j])
{
c[i + j] += a[i] * b[j];
next_mod (c, i + j);
}
for (int i = 0; i < c.sz; ++ i)
next_mod (c, i);
erase_null (c);
return c;
}
vsint div (vsint &a, vsint &b, vsint &r)
{
r.assign (1, 0);
vsint s (a.sz, 0);
for (int i = a.sz - 1; i >= 0; -- i)
{
r.insert (r.begin (), a[i]);
while (cmp (r, b) >= 0)
{
++ s[i];
sub_from (r, b);
}
}
erase_null (s);
erase_null (r);
return s;
}
//--------------------- Algo ---------------------------------------------------
vsint sqrt (vsint &a)
{
int n = (a.size () + 1) / 2;
vsint x (n, 0);
for (int i = n - 1; i >= 0; -- i)
for (x[i] = 9; x[i] > 0; -- x[i])
{
vsint xx = mul (x, x);
if (cmp (xx, a) <= 0)
break;
}
return x;
}
//---------------------- BigInteger --------------------------------------------
class binteger
{
public:
vsint a;
binteger ();
binteger (int x);
binteger (string s);
string tostr ();
friend int cmp (binteger a, binteger b);
friend binteger operator + (binteger a, binteger b);
friend binteger operator - (binteger a, binteger b);
friend binteger operator * (binteger a, binteger b);
friend binteger operator / (binteger a, binteger b);
friend binteger operator % (binteger a, binteger b);
friend binteger operator >> (binteger a, int k);
friend binteger operator << (binteger a, int k);
};
binteger :: binteger ()
{
a = vsint (1, 0);
}
binteger :: binteger (int x)
{
do
{
a.push_back (x % 10);
x /= 10;
}
while (x);
}
binteger :: binteger (string s)
{
a = vsint (s.sz, 0);
for (int i = s.sz - 1; i >= 0; -- i)
a[a.sz - i - 1] = s[i] - '0';
}
string binteger :: tostr ()
{
string s = "";
for (int i = a.sz - 1; i >= 0; -- i)
s += a[i] + '0';
return s;
}
int cmp (binteger a, binteger b)
{
return cmp (a.a, b.a);
}
binteger operator + (binteger a, binteger b)
{
binteger c;
c.a = add (a.a, b.a);
return c;
}
binteger operator - (binteger a, binteger b)
{
binteger c;
c.a = sub (a.a, b.a);
return c;
}
binteger operator * (binteger a, binteger b)
{
binteger c;
c.a = mul (a.a, b.a);
return c;
}
binteger operator / (binteger a, binteger b)
{
binteger c;
vsint r;
c.a = div (a.a, b.a, r);
return c;
}
binteger operator % (binteger a, binteger b)
{
binteger c;
vsint r;
div (a.a, b.a, r);
c.a = r;
return c;
}
binteger operator >> (binteger a, int k)
{
binteger c;
c.a = shift_right (a.a, k);
return c;
}
binteger operator << (binteger a, int k)
{
binteger c;
c.a = shift_left (a.a, k);
return c;
}
18:47
12.07.2010
По всем вопросам обращаться: rumterg@gmail.com