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