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

   Из  табл.2 заметим, что при 100тыс. десятичных знаков использовалось 25,2 тыс. знаков в факториальной математике и 10,4 тыс. знаков системы 2³². Число показывает, во сколько раз количество разрядов в системе счисления, основанной на факториалах больше количества разрядов в системе 2³² при длине десятичного представления того же самого числа равного 100тыс.

   При 1000тыс. десятичных знаков получаем коэффициент , которое меньше . 

  Можно предположить, что при длине десятичного  числа намного превосходящего 1млн. знаков коэффициент станет и система счисления, основанная на факториалах, будет выгоднее в плане использования памяти, нежели система 2³². Практически такого десятичного числа не удалось посчитать из-за недостаточного количества оперативной памяти и мощности процессора.

  б.) Производительность операций умножения и деления.

  Проведем несколько тестов на различных системах счисления, в которых будем 1000 раз производить операции умножения, зафиксируем их на графике зависимости времени работы алгоритма от количества десятичных разрядов чисел, участвующих в операции умножения.

рис.3 Произведение

   На  рисунке 3 показана зависимость времени  работы операции умножения от количества разрядов десятичных чисел. Начиная примерно с 1950 десятичных знаков, система счисления на факториалах имеет выигрыш во времени по отношению к десятичной. Но, тем не менее, система счисления 2³² в десятки, а то и в сотни раз работает быстрее.

рис.4 Деление

   Аналогичные действия проводим с операцией деления. Рассмотрим рис. 4. График схож с графиком на рис.3. Видно, что начиная также с 1950знаков факториальная система счисления выигрывает по времени у десятичной, система 2³² по-прежнему выигрывает в разы у остальных.

   Подводя некоторый итог, можно сказать, что  система счисления, основанная на факториалах  имеет преимущество у десятичной, как по используемой памяти, так и по производительности. Система счисления 2³² выгоднее десятичной и факториальной.

 

    Заключение

  В процессе работы над данной темой  был создан класс для работы с  длинными числами, написаны функции  для  основных арифметических операций (для десятичной системы счисления и для факториальной системы счисления), а также две функции перевода чисел из факториальной системы счисления в десятичную и обратно.

  Также была проведена серия тестов, подтверждающая то, что при работе с длинными числами, факториальная система счисления дает выигрыш по времени и объему затрачиваемой оперативной памяти, по сравнению с десятичной системой счисления.

  Было  замечено, что при операциях с  длинными числами в факториальной системе счисления, имеющих 30 разрядов и более, объем, занимаемый этими числами в оперативной памяти меньше объема этих же чисел, представленных в десятичной системе счисления.

 

  Список  использованной литературы

1. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. – М.: «Мир», 1979.
2. Кнут Д. Искусство программирования – M., 2007г. –788с.
3. Кормен Т., Лейзерсон Ч.. Алгоритмы, построение и анализ. – М.: МГУ, 1990.
4. Окулов. С.М. «Длинная» арифметика. [http://comp-science.narod.ru/DL-AR/okulov.htm]: Дидактические материалы по информатике и математике - С.М. Окулов. «Длинная» арифметика: http://comp-science.narod.ru. - Дидактические материалы по информатике и математике (по состоянию на 15.05.2010) 
   Приложение: Class BigInt, функции для работы с классом

  Содержимое файла-заголовка cursovaya.h:

#include "string" 

#define BASE 10

#define MAX_DIG 100000 

using namespace std; 

// The determination of Class BigInt

class BigInt {

public:

      long Size;

      int Coef[MAX_DIG];

      BigInt();

      BigInt(const string&);

      BigInt(int);

      BigInt(const BigInt&);

      virtual ~BigInt(); 

      void zero();

      void update(); 

      BigInt operator =(const BigInt&);

      void random(int);

      BigInt operator +(BigInt);

      BigInt operator ++(int);

      BigInt operator -(BigInt&); 

      BigInt operator *(const int);

      BigInt operator *(BigInt&);

      BigInt operator /(BigInt&);

      BigInt operator %(BigInt&); 

      // Factorial <- Dec

      void FacToDec(); 

      operator long();

}; 

      // Main operations of Factorial Algebra

      bool operator<(BigInt&, BigInt&); 

      bool operator<=(BigInt&, BigInt&);

      bool operator==(BigInt&, BigInt&);

      bool operator!=(BigInt&, BigInt&);

      bool operator>(BigInt&, BigInt&);

      bool operator>=(BigInt&, BigInt&); 

      //Number output

      ostream& operator<<(ostream&, const BigInt&); 

      // Factorial <-> Dec

      BigInt FacToDec(BigInt);

      BigInt DecToFac(BigInt); 

      // The comparison of two numbers: int and BigInt

      short cmp(int &,int &);

      short cmp(BigInt &,BigInt &);

      // Division in DEC system

      BigInt Div_int(const BigInt &, const int);

      int Div_int_rm(const BigInt &, const int);

      // Operations in Fact system

      BigInt Div_Int_Fac(BigInt &,const int);

      int Div_Int_Fac_rm(BigInt &,const int); 

      void Mul(const BigInt&, const BigInt&, BigInt&);

  Содержимое  файла сursovaya.cpp с исходным кодом класса:

#include "cursovaya.h"

#include "math.h"

#include "time.h" 

#define BASE_DIG 1 

short cmp(int &a,int &b){

      if (a==b) return 0;

      if (a>b) return 1;

      if (a<b) return -1;

      return NULL;

} 

short cmp(BigInt &A, BigInt &B){

      if (A==B) return 0;

      if (A>B) return 1;

      if (A<B) return -1;

      return NULL;

}

bool ifnull(BigInt &A){

      if(A.Size==1 && A.Coef[0]==0)

            return true;

      return false;

}

BigInt::BigInt() {

      memset(Coef,0,sizeof(Coef));

      Size = 1;

} 

BigInt::BigInt(const string &str){

      int k=0;

      Size = (long)str.length();

      memset(Coef,0,sizeof(int)*MAX_DIG);

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

            Coef[k] = str[j]-'0';

            k++;

      }

} 

BigInt::BigInt(const BigInt &A) {

      Size = A.Size;

      memcpy(Coef,A.Coef,sizeof(Coef));

} 

BigInt::BigInt(int count){

      memset(Coef,0,sizeof(int)*MAX_DIG);

      this -> Size = count;