bignum.cpp (3)

Code dưới đây cho phép sử dụng hệ cơ số bất kì.

Bài toán

Xử lý các thao tác +, * trên số lớn.

Cho phép sử dụng hệ cơ số bất kì.

Độ phức tạp

cộng : O(m+n)

nhân : O(m*n)

với m, n là độ dài của hai bignum.

Code này của : Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <string>

#include <iostream>

using namespace std;

int max(int a, int b){ return a>b?a:b; }

/// Big integer

#define LIM 1234

template <int BASE=10000>

struct bigint {

    int a[2309]; // zero-based

    int n;

    int& operator [] (int i){ return a[i]; }

    const int operator [] (int i) const { return a[i]; }

    void resize(int N){ for (int i=n; i<N; i++) a[i]=0; n=N; }

    void trim(){ while ((n>1 && a[n-1]==0) or n>LIM) n--; }

    void normalize(){ for (int i=0; i<n; i++) { a[i+1]+=a[i]/BASE; a[i]%=BASE; } trim(); }

    bigint(int x=0) { a[0]=x; n=1; }

    void operator = (int x);

    void operator = (const bigint &A);

    void operator += (const bigint &A);

    void operator *= (int k);

    void operator *= (const bigint &A);

    string toString() const;

    bigint <10000> toBase10();

};

template <int BASE> void bigint<BASE>::

operator = (int x){ a[0]=x; n=1; }

template <int BASE> void bigint<BASE>::

operator = (const bigint &A){ for (int i=0; i<A.n; i++) a[i]=A[i]; n=A.n; }

template <int BASE> void bigint<BASE>::

operator += (const bigint &A){

    resize(max(n, A.n)+1);

    for (int i=0; i<A.n; i++) a[i]+=A[i];

    normalize();

}

template <int BASE> void bigint<BASE>::

operator *= (int k){

    resize(n+1);

    for (int i=0; i<n; i++) a[i]*=k;

    normalize();

}

template <int BASE> bigint<BASE>

operator * (const bigint<BASE> &A, const bigint<BASE> &B){

    bigint<BASE> R=0;

    int i, j;

    R.resize(A.n+B.n);

    for (i=0; i<A.n; i++)

    for (j=0; j<B.n; j++)

    R[i+j] += A[i]*B[j];

    R.normalize();

    return R;

}

template <int BASE> void bigint<BASE>::

operator *= (const bigint<BASE> &A){

    *this = (*this) * A;

}

template <int BASE> string bigint<BASE>::

toString() const{

    char s[23];

    string r="";

    sprintf(s, "%d", a[n-1]);

    r += s;

    for (int i=n-2; i>=0; i--){ sprintf(s, "%04d", a[i]); r += s; }

    return r;

}

template <int BASE> bigint<10000> bigint<BASE>::

toBase10(){

    bigint<10000> R=0;

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

    { R*=BASE; R+=a[i]; }

    return R;

}

#undef LIM

/// Container

bigint<12345> A, B;

main(){

    A=1024;

    A=A*A*A;

    cout << A.toBase10().toString() << endl;

}

Nhận xét