Автор: Пользователь скрыл имя, 24 Декабря 2010 в 10:28, курсовая работа
Цель моей курсовой работы заключается в реализации структур и алгоритмов для работы с «длинными» числами для последующего использования их в вычислениях. Скорость работы алгоритмов сильно зависит от выбора основания системы счисления (BASE).
Введение 3
1. Структуры, алгоритмы классических «длинных» чисел 5
1.1 Структура класса «BigInt» 6
1.2 Операции над большими числами 7
2. Структуры и алгоритмы факториальной длинной арифметики 10
2.1 Структура факториальной длинной арифметики 10
2.2 Функции и операции над числами факториальной арифметики 11
3. Сравнение систем счисления 15
3.1 Набор необходимых для сравнения инструментов 15
3.2 Сравнение систем счисления 16
Заключение 20
Список использованной литературы 21
Приложение: Class BigInt, функции для работы с классом 22
};
void BigInt::random(int count){
this -> Size = count;
srand((unsigned int)time(0));
for(int i = 0; i < count; i++){
this->Coef[i]
= rand() % (i + 1);
}
if (this->Coef[count-1] == 0) this->Coef[count - 1] = 1;
}
BigInt::~BigInt(){}
void BigInt::zero(){
memset(Coef,0,sizeof(int
Size = 1;
}
void BigInt::update(){
Size = 1;
for(int i=MAX_DIG-1; i>=0;i--)
if (Coef[i]!=0){
Size=(i+1);
break;
}
}
BigInt::operator long() {
long tmp=0;
for(int i=0; i<Size; i++) {
tmp += Coef[i]*(long)pow(BASE, (double)i);
}
return tmp;
}
BigInt BigInt::operator =(const BigInt &A){
Size=A.Size;
memcpy(Coef,A.Coef,sizeo
return *this;
}
bool operator==(BigInt &A, BigInt &B){
if(A.Size == B.Size) {
unsigned int n=0;
for (int i=A.Size-1;i>=0;i--)
if(A.Coef[i]
n++;
if(n==A.Size) return true;
}
return false;
}
bool operator!=(BigInt &A, BigInt &B){
if(A.Size == B.Size) {
unsigned int n=0;
for (int i=A.Size-1;i>=0;i--)
if(A.Coef[i]
n++;
else return true;
if(n==A.Size) return false;
}
return true;
}
bool operator<(BigInt &A, BigInt &B){
if(A.Size < B.Size) return true;
else if (A.Size == B.Size) {
int i=A.Size-1;
while(i+1)
if (A.Coef[i] < B.Coef[i]) return true;
else if (A.Coef[i] > B.Coef[i]) return false;
else i--;
}
return false;
}
bool operator<=(BigInt &A, BigInt &B){
if(A.Size < B.Size || A==B) return true;
else if (A.Size == B.Size) {
int i=A.Size-1;
while(i+1)
if (A.Coef[i] < B.Coef[i]) return true;
else if (A.Coef[i] > B.Coef[i]) return false;
else i--;
}
return false;
}
bool operator>(BigInt &A, BigInt &B){
if(A.Size > B.Size) return true;
else if (A.Size == B.Size) {
int i=A.Size-1;
while(i+1)
if (A.Coef[i] > B.Coef[i]) return true;
else if (A.Coef[i] < B.Coef[i]) return false;
else i--;
}
return false;
}
bool operator>=(BigInt &A, BigInt &B){
if(A.Size > B.Size || A==B) return true;
else if (A.Size == B.Size) {
int i=A.Size-1;
while(i+1)
if (A.Coef[i] > B.Coef[i]) return true;
else if (A.Coef[i] < B.Coef[i]) return false;
else i--;
}
return false;
}
BigInt BigInt::operator +(BigInt B){
BigInt C;
int i
int temp=0;
const int *b=B.Coef;
int *c=C.Coef, carry = 0;
C.Size = max(Size,B.Size);
for(i=0;i<C.Size;i++){
temp = temp + Coef[i] + b[i];
c[i] = temp % (i + 2);
temp = temp / (i + 2);
}
if(temp) {
c[i] = temp % (i + 2);
temp = temp / (i + 2);
}
if(c[C.Size]) C.Size++;
return C;
}
BigInt BigInt::operator -(BigInt &B){
// работает для BASE=n!
BigInt C;
const int *b=B.Coef;
int *c=C.Coef;
long i;
long temp, carry=0;
if( Size < B.Size ) printf("BigSub: Size error");
for( i=0; i<B.Size; i++ ){
temp = Coef[i] - b[i] + carry;
if(temp<0) {
c[i] = (int)(temp + i+2);
carry = -1;
} else {
c[i] = (int) temp;
carry = 0;
}
}
for(; i<Size; i++) {
temp = Coef[i] + carry;
if ( temp < 0 ) {
c[i] = (int)(temp + i+2);
carry = -1;
} else {
c[i] = (int)temp;