bignum.cpp

Nội dung này không còn phù hợp, bạn nên đi sang trang này https://sites.google.com/site/kc97ble/requests/bignum-voi-cac-phep-toan

Đã có code bignum cho các bài toán đơn giản ở bên dưới.

Bài toán

Xử lý các phép toán +,* trên số lớn

Độ phức tạp

cộng : O(n+m)

nhân : O (n*m)

Code này của : Đỗ Ngọc Khánh

#include<iostream>

#include<cstring>

#include<cstdio>

#include<iomanip>

#include<vector>

#include<algorithm>

#include<sstream>

#include<cmath>

using namespace std;

template<int BASE, int MAX_LEN> class BigInteger {

    private:

        int d[MAX_LEN], n;

    public:

        BigInteger(int x = 0) {

            memset(d, 0, sizeof d); n = 0;

            for(; x != 0 && n < MAX_LEN; x /= BASE)

                d[n++] = x % BASE;

        }

        void fix() {

            int rem = 0;

            for(int i = 0; i < n; ++i) {

                int temp = rem + d[i];

                d[i] = temp % BASE;

                rem = temp / BASE;

            }

            while(rem != 0 && n < MAX_LEN)

                d[n++] = rem % BASE, rem /= BASE;

            while(n > 0 && d[n-1] == 0) --n;

        }

        bool operator == (const BigInteger &a) const {

            if(n != a.n) return false;

            for(int i = 0; i < n; ++i)

                if(d[i] != a.d[i]) return false;

            return true;

        }

        void operator += (const BigInteger &a) {

            n = max(n, a.n);

            for(int i = 0; i < n; ++i)

                d[i] += a.d[i];

            fix();

        }

        BigInteger operator * (const BigInteger &a) const {

            BigInteger res;

            for(int i = 0; i < n; ++i) {

                res.n = max(res.n, min(i + a.n, MAX_LEN));

                for(int j = 0; j < a.n && i + j < MAX_LEN; ++j)

                    res.d[i+j] += d[i] * a.d[j];

                res.fix();

            }

            return res;

        }

        string toBase10() const {

            BigInteger<10000, 17> res, mul (1);

            for(int i = 0; i < n; ++i) {

                res += mul * BigInteger<10000, 17>(d[i]);

                mul = mul * BigInteger<10000, 17>(BASE);

            }

            return res.toString(4);

        }

        string toString(const int &baseDigit) const {

            if(n == 0) return "0";

            stringstream res;

            res << d[n-1];

            for(int i = n - 2; i >= 0; --i)

                res << setfill('0') << setw(baseDigit) << d[i];

            return res.str();

        }

};

int main() {

    BigInteger<10, 100> a (15), b(1390); // He co so 10, luu toi da 100 chu so

    cout << (a * b).toString(1) << "\n";

    a += b;

    cout << a.toString(1) << "\n";

    return 0;

}

Nhận xét

Cảm ơn bạn Đỗ Ngọc Khánh đã giúp tôi hoàn thành bài viết này.