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

  Остаток от деления является последним перенесенным остатком.

   г) Печать длинного числа

   С++ допускает перегрузку операторов ввода-вывода, которой воспользуемся для удобства последующего использования.

   Для вывода при помощи этой функции необходимо, чтобы основание BASE было степенью 10, например, BASE = 1000 = 10³. Тогда количество цифр в одном знаке числа будет равно этой степени, а реализация алгоритма – тривиальной.

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

   Для удобства и гибкости класса зададим количество цифр в коэффициенте заранее константой BASE_DIG

   2. Структуры и алгоритмы факториальной длинной арифметики

   2.1 Структура факториальной длинной арифметики

   Длинная арифметика повсеместно используется для работы с большими числами. Возникает  вопрос: какую систему счисления  выбрать, чтобы по минимуму «разместить» длинные числа в памяти и потом  производить расчеты наиболее эффективно, с наименьшими временными затратами? Для ответа на этот вопрос рассмотрим систему счисления, основанную на факториалах позиций цифр в числе. В такой системе счисления с ростом разрядов в разы увеличивается число, представленное по BASE = 10, т.е. например, 3_! = 6₁₀ , а 4_! = 24₁₀ что в 4 раза больше.

   Структура класса полностью совпадает со структурой класса «длинных» чисел, за исключением  того, что BASE, т.е. основание системы счисления меняется в зависимости от разряда числа. Например, число 54321_! в этой интерпретации будет иметь вид:

  54321_! = 1*1! + 2*2! + 3*3! + 4*4! + 5*5! (BASE=n!).

   Заметим следующую закономерность: что разряд «единиц» может колебаться от 0 до 1, «десятков» – от 0 до 2 и т.п. Таким  образом, например, разряд с порядковым номером «30» может колебаться от 0 до 30. Простым представлением длинного числа не обойтись, а через класс BigInt можно, выводя каждый из «сложных» (которые больше 9) коэффициентов по отдельности. происходит бинарным поиском коэффициентов и условием того, что каждый i-й коэффициент частного, умноженный на делитель не превосходит делимого. Сложность алгоритма деления равна O(n²*log₂ n): проверка коэффициентов и бинарный поиск.

 

  2.2 Функции и операции  над числами факториальной арифметики

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

  1. перевод числа в факториальную систему счисления

  Функция DecToFac(BigInt A), возвращающая BigInt, но уже в нужном «факториальном» представлении.

  Перевод в факториальную систему счисления  осуществляется за счет деления A на очередную компоненту, при этом остаток от деления на эту компоненту заносится в массив коэффициентов.

  2. перевод числа из факториальной системы счисления в десятичную.

  Функция FacToDec(BigInt A), где А – «факториальное» представление числа, возвращает BigInt по основанию BASE

  Пробегаемся по всей длине числа (i=n-1;0) и записываем в переменную типа BigInt значение соответствующего коэффициента, умноженного на его номер, умноженной на A.Coef[i] и суммируем со следующим значением. (Для реализации вводим две функции: сложение длинного числа с простым целым  умножение длинного числа на простое целое в десятичном виде).

  3. Процедуры сложения/вычитания аналогичны, что и при BASE=10, только на каждом шаге итерации нужно учитывать возможность переноса в следующий разряд, при этом увеличив BASE на единицу.

   При сложении цифры складываются слева направо, т.к. они хранятся в обратном порядке. Если зафиксировано переполнение и при сложении получена цифра, большая максимально возможной в факториальной системе счисления, то происходит “перенос” в следующий разряд. При этом ведется учет, что BASE c каждым последующим разрядом увеличивается.

   Для вычисления C = A+B, перегружен оператор сложения.

   temp играет роль “временной” цифры,  до выполнения переноса. Возможно, temp > BASE. Для быстрого доступа к коэффициентам и улучшенного понимания кода объявляются временные указатели.

   Вычитание осуществляется аналогично вычитанию при BASE = 10, разница лишь в том, что основание нашей системы счисления с каждым более старшим разрядом увеличивается на единицу. Поэтому двигаясь от младшего разряда к старшему, мы увеличиваем BASE.

   4.Умножение длинного числа на число базового типа: цикл от нуля до длины числа типа BigInt, в котором в temp записываем произведение соответствующего коэффициента длинного числа на наш множитель базового типа и добавляем перенос, если таковой присутствует; дальше находим перенос и соответствующий коэффициент произведения на данной итерации.

   Если  после выполнения цикла перенос carry равен нулю, то длина числа-произведения равна длине исходного длинного числа (множителя).

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

   Длина числа-произведения равна количеству итераций, потребовавшихся для выполнения циклов, описанных выше.

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

   На  вход подаются два длинных числа. Создаем длинное число res и обнуляем его. Запускаем цикл по длине первого множителя, начиная со старшего разряда, в котором заполняем число-результат:

1. Умножаем второй множитель на i-ый коэффициент первого.
2. Добавляем получившийся результат к res.
3. Умножаем res на i.

   В итоге res и будет являться произведением двух чисел.

   5. Деление длинного числа на число базового типа: описано функцией  
void Div_fac(const BigInt& A, const BigInt& B, BigInt& Q, int& R),  
где A – делимое, B – делитель, Q – частное, R – остаток.

  В цикле проходим по коэффициентам делимого, начиная со старшего разряда. Для каждого пройденного коэффициента делаем следующее: делим его на В, целая часть результата добавляется в конец общего частного, остаток переносится и принимает участие в обработке следующего коэффициента. После выполнения цикла подсчитывается размер длинного частного Q.

  В R записывается последний промежуточный остаток от деления.

  Теперь  перейдем к реализации деления длинных чисел, основанных на факториальной системе счисления. Данную реализацию осуществляет функция void Div_fac(BigInt& A, BigInt& B, BigInt& Q, BigInt& R);

  Сначала создадим вспомогательное число  fact = 0, у которого только один коэффициент по ходу алгоритма не должен быть нуль, примем R = A.  
Учитывая то, что , двигаясь  
в цикле от старшего разряда делимого к младшему, бинарным поиском находим коэффициенты частного. Промежуточным остатком будет R = R – B * fact.

  После выполнения цикла в Q вернется целая часть от деления, в R – остаток от деления.

  Для удобства пользования классом BigInt перегружены «operator /», «operator %», которые возвращают Q и R соответственно как в функции void Div_Fac(…).

  6. Реализованный класс BigInt имеет перегруженные операторы сравнения длинных чисел, основанных на факториалах, которые незамысловато реализуются.

 

  3. Сравнение систем  счисления

  3.1 Набор необходимых  для сравнения инструментов.

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

  Возьмем класс длинной арифметики, с основанием 2³². Каждый разряд числа, записанного в этом классе, колеблется от 0 до 4 294 967 296, операции сложения, вычитания, умножения и деления выполняются быстро за счет сдвига на низком уровне.

 

   3.2 Сравнение систем счисления

   а) Рассмотрим десятичное представление числа: посмотрим, сколько разрядов будут занимать числа в факториальной и 2³² системах счисления в зависимости от увеличения числа в десятичной системе счисления.

   

    
табл.1 Изменение количества разрядов в зависимости от BASE (1)

рис.1 Зависимость разрядов BASE от десятичных разрядов (1)

   На  рис.1 рассмотрены десятичные числа  длиной от 1 до 65, числовые характеристики занесены в табл.1. Видно, что с  ростом числа десятичных разрядов растут разряды в других системах счисления, причем кривая 2³² ближе к оси абсцисс, нежели двух других кривых. Факториальная система счисления совершенно не выгодна для десятичных чисел длиной меньше 22, а дальше начинает выигрывать у десятичной системы счисления.

   Продолжим дальше увеличивать длину десятичных чисел до миллиона. Посмотрим изменения:

   

   табл.2 Изменение количества разрядов в зависимости от BASE (2)

рис.2 Зависимость разрядов BASE от десятичных разрядов (2)

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