Длинная арифметика

Автор: Пользователь скрыл имя, 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

Работа содержит 1 файл

Длинная арифметика.doc

— 185.50 Кб (Скачать)

      if (!carry) C.Size = Size;

      while (carry) {

            temp = carry % (i+2); //BASE

            carry = carry / (i+2);

            c[i] = temp; //BASE

            i++;

      }

      C.update();

      return C;

} 

void BigInt::FacToDec(){

      BigInt res;

      int i=0;

      for(int i = Size-1; i >= 0; i--){

            Mul_Int_Dec(res, (i + 2), res);

            Add_Int_Dec(res,Coef[i],res);

      }

      *this = res;

} 

BigInt FacToDec(BigInt A){

      BigInt res;

      int i=0;

      for(int i = A.Size-1; i >= 0; i--){

            Mul_Int_Dec(res, (i + 2), res);

            Add_Int_Dec(res,A.Coef[i],res);

      }

      return res;

} 

void Div_fac(const BigInt &A, const int B, BigInt &Q, int &R) {

      int r=0, *q=Q.Coef;

      const int *a=A.Coef;

      long i, temp;

      for ( i=A.Size-1; i>=0; i--) {

            temp = r*(i+2) + a[i];

            q[i] = temp / B;

            r = temp - q[i]*B; //r – промежуточный остаток на предыдущей итерации

      }

      R = r;

      i = A.Size-1;

      while ( (i>0) && (q[i]==0) ) i--; //подсчитываем длину частного

      Q.Size = i+1;

} 

int operator%(const BigInt &A, const int B){

      BigInt Q;

      int r=0, *q=Q.Coef;

      const int *a=A.Coef;

      long i, temp;

      for ( i=A.Size-1; i>=0; i--) {

            temp = r*(i+2) + a[i];

            q[i] = temp / B;

            r = temp - q[i]*B; //r – промежуточный остаток на предыдущей итерации

      }

      return r;

} 

BigInt Div_int(const BigInt &A, const int B) {

      BigInt Q;

      int r=0, *q=Q.Coef;

      const int *a=A.Coef;

      int i, temp;

      for ( i=A.Size-1; i>=0; i--) { 

            temp = r*BASE + a[i];

            q[i] = temp / B;  

            r = temp - q[i]*B;

      } 

      i = A.Size-1;

      while ( (i>0) && (q[i]==0) ) i--;

      Q.update();

      return Q;

} 

int Div_int_rm(const BigInt &A, const int B) {

      BigInt Q;

      int r=0, *q=Q.Coef;

      const int *a=A.Coef;

      int i, temp;

      for ( i=A.Size-1; i>=0; i--) {

         temp = r*BASE + a[i];

            q[i] = temp / B;

            r = temp - q[i]*B;

     }

      return r;

} 

BigInt Div_Int_Fac(BigInt &A, const int B) {

      BigInt C;

      const int *a=A.Coef;

      int res = a[A.Size-1];

      for(int i=A.Size-1;i>=0;i--){

            C.Coef[i] = res / B;

            if (i) res = (res % B) * (i+1) + a[i-1];

      }

      C.update();

      return C;

} 

int Div_Int_Fac_rm(BigInt &A, const int B) {

      const int *a=A.Coef;

      int temp, rm, res = a[A.Size-1];

      for(int i=A.Size-1;i>=0;i--){

            temp = res / B;

            if (i) res = (res % B) * (i+1) + a[i-1];

            else rm = res % B;

      }

      return rm;

} 

void Div_fac(BigInt& A, BigInt& B, BigInt& Q, BigInt& R){

      BigInt fact, temp;

      R = A;

      int i;

      for(i = A.Size - 1;i >= 0;i--)

      {

            int from = 0, till = i + 1; 

            fact.Size = i + 1; 

            while (from < till)

            {

                  int x = (from + till + 1) / 2;

                  fact.Coef[i] = x;

                  temp = B * fact;

                  if ( temp <= R)

                        from = x;

                  else till = x - 1;

            } 

            fact.Coef[i] = from;

            temp = B * fact;

            R = R - temp;

            Q.Coef[i] = from; 

            fact.Coef[i] = 0;

      }

} 

BigInt BigInt::operator /(BigInt& B){

      BigInt Q,R;

      if( Size < B.Size ){

            return 0; //Вернем нуль, т.е. делимое меньше делителя

      }

      else Div_fac(*this,B,Q,R);

      Q.update();

      return Q;

} 

BigInt BigInt::operator %(BigInt& B){

      BigInt Q,R;

      if(Size < B.Size) return B;

      else Div_fac(*this,B,Q,R);

      return R;

} 

BigInt BigInt::operator ++ (int){ 

      int i=0, temp = 1;

      while(temp){

            temp = temp + this -> Coef[i] ++;

            this -> Coef[i] = temp % (i + 2);

            temp = temp / (i + 2);

            i++;

      }

      if(temp) {

            Coef[i] = temp % (i + 2);

            temp = temp / (i + 2);

      }

      if(Coef[Size]) Size++;

      return *this;

} 

Содержимое файла  программы main.cpp:

#include "cursovaya.h"

#include "conio.h"

#include "iostream"

#include "fstream"

#include "time.h"

#include "stdio.h" 

void analyze(){

      ofstream out("analyze.txt");

      BigInt A;

      A.Coef[0]=1;

      BigInt B;

      for(long i = 1; i<101;i++){

            A = A * (int)i;

            out<<i<<"\t"<<A.Size;

            B=FacToDec(A);

            out<<"\t"<<B.Size<<endl;

            cout << i << endl;//}

      }

      out.close();

} 

int main(){

      BigInt A,B;

      int n,m,s;

      cout<<"Enter n,m:"; cin>>n>>m;

      A.random(n); B.random(m);

Информация о работе Длинная арифметика