Автор: Пользователь скрыл имя, 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
carry = 0;
}
}
i = Size - 1;
while ( (i>0) && (c[i] == 0) ) i--;
C.Size = i+1;
return C;
}
BigInt BigInt::operator *(BigInt& A){
BigInt C;
int i;
int res=0;
for (i = Size; i > 0; i--){
C = (C + (A * Coef[i-1])) * i;
}
return C;
}
void Add(const BigInt &A, const BigInt &B, BigInt &C){
// работает для стандартной BASE
long i;
long temp;
const int *a=A.Coef, *b=B.Coef;
int *c=C.Coef, carry = 0;
if( A.Size < B.Size ){
Add(B,A,C);
return;
}
for(i=0; i<B.Size; i++) {
temp = a[i] + b[i] + carry;
if( temp>=BASE ) {
c[i] = (int)temp - BASE;
carry = 1;
} else {
c[i] = (int)temp;
carry = 0;
}
}
for(; i<A.Size; i++) {
temp = a[i] + carry;
if( temp >= BASE ) {
c[i] = (int)temp - BASE;
carry = 1;
} else {
c[i] = (int)temp;
carry = 0;
}
}
if (carry) {
c[i] = carry;
C.Size = A.Size +1;
}
else C.Size = A.Size;
}
int Sub (const BigInt& A, const BigInt& B, BigInt& C){
// работает для стандартной BASE
const int *a=A.Coef, *b=B.Coef;
int *c=C.Coef;
long i;
long temp, carry=0;
if( A.Size < B.Size ) printf("BigSub: Size error");
for( i=0; i<B.Size; i++ ){
temp = a[i] - b[i] + carry;
if(temp<0) {
c[i] = (int)(temp + BASE);
carry = -1;
} else {
c[i] = (int) temp;
carry = 0;
}
}
for(; i<A.Size; i++) {
temp = a[i] + carry;
if ( temp < 0 ) {
c[i] = (int)(temp + BASE);
carry = -1;
} else {
c[i] = (int)temp;
carry = 0;
}
}
i=A.Size - 1;
while ( (i>0) && (c[i] == 0) ) i--;
C.Size = i+1;
return carry;
}
void Mul(const BigInt& A, const BigInt& B, BigInt& C) {
int i, j;
const int *a=A.Coef, *b=B.Coef;
int *c=C.Coef;
int temp, carry;
for (i=0;i<=A.Size + B.Size;i++)
c[i]=0;
for (i=0;i<A.Size;i++){
carry = 0;
for (j=0;j<B.Size;j++){
temp=a[i]*b[
carry=temp/
c[i+j]=temp-
}
c[i+j]=carry;
}
i=A.Size + B.Size-1;
if (c[i]==0) i--;
C.Size = i+1;
}
ostream& operator<<(ostream& os, const BigInt& A) {
long j;
int Pow, Dec, Coef;
os
<< A.Coef[A.Size-1];
for (long i=A.Size-2; i>=0; i--) { // Цикл вывода коэффициентов
Pow = BASE/10;
Coef = A.Coef[i];
for (j=0; j<BASE_DIG; j++) { // Цикл, выводящий каждый коэффициент
Dec = Coef/Pow;
Coef -= Dec*Pow;
Pow /= 10;
os << Dec;
}
}
return os;
}
BigInt DecToFac(BigInt ost){
BigInt big;
int i=0,j=2;
while(!((ost.Size == 1) && (ost.Coef[0]==0))){
big.Coef[i] = Div_int_rm(ost,j);
i++;
big.Size++;
ost = Div_int(ost,j);
j++;
}
big.update();
return big;
};
void Add_Int_Dec(BigInt &A, int &B, BigInt &C){
long i=0;
int temp=B;
const int *a=A.Coef;
int *c=C.Coef, carry = 0;
while (B>0){
temp = a[i] + (B % BASE) + carry;
B /= BASE;
if( temp>=BASE ) {
c[i] = (int)temp - BASE;
carry = 1;
} else {
c[i] = (int)temp;
carry = 0;
}
i++;
}
for(; i<A.Size; i++) {
temp = a[i] + carry;
if( temp >= BASE ) { //BASE
c[i] = (int)temp - BASE; //BASE
carry = 1;
} else {
c[i] = (int)temp;
carry = 0;
}
}
if (carry) c[i] = carry;
C.update();
}
void Mul_Int_Dec(BigInt &A,const int B, BigInt &C) {
int i, temp;
const int *a=A.Coef;
int *c=C.Coef, carry=0;
for (i=0; i<A.Size;i++) {
temp = a[i]*B + carry;
carry = temp / BASE; //BASE
c[i] = temp - carry * BASE; //BASE
}
if (!carry) C.Size = A.Size;
while (carry) {
temp = carry % BASE; //BASE
carry = carry / BASE;
c[i] = temp; //BASE
i++;
}
C.update();
}
BigInt BigInt::operator *(const int B) {
BigInt C;
int i, temp;
const int *a=Coef;
int *c=C.Coef, carry=0;
for (i=0; i<Size;i++) {
temp = a[i] * B + carry;
carry = temp / (i+2); //BASE
c[i] = temp - carry * (i+2); //BASE
}