Реализация длинной арифметики (с использованием массивов)



Нужно реализовать операции сложения, вычитания, умножения, деления и сравнения над числами большой длины



Листинг 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