Математические основы алгоритмов используемых в работе

При создании программы возник вопрос: каким образом представлять большие числа? Решение было принято о том что число можно занести в массив типа unsigned char в который помещается два шестнадцатеричных числа, которые обрабатываются как 256-разрядные:

Это позволяет значительно упростить функции.

Размещение значений в массиве обратное, т.е. число “FF AB C4” в массиве будет представлено как: unsigned char a[3]={0xC4, 0xAB, 0xFF};

Все функции в программе предназначены для работы с 256-битными значениями.

Алгоритмы арифметики целых чисел и полиномов во многом похожи, поскольку представление целого числа а в системе счисления с основанием B в виде:

 где 0 < a_i < В, аналогично представлению полинома .

Ниже описаны алгоритмы, используемые в программном продукте. Алгоритм представлен по следующей структуре: теоретические основы и листинг программы.

 

Сложение и вычитание

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

Пусть неотрицательные целые числа а и b   заданы в системе счисления с основанием В:

где 0 <a_i; b_i<B. Для удобства считаем, что оба числа имеют равную длину, при необходимости старшие разряды меньшего числа заполняем нулями.

Сложение выполняется «в столбик».

Алгоритм 1. Сложение целых чисел, [Молдовян Н.А. и др., 2004].

Вход. Целые числа , .

Выход. Сумма .

1.    Положить

2.    Для i = 0, 1, ...,п- 1 выполнить следующие действия.

2.1. Вычислить

2.2. Положить , .

3.    Положить с_п = s.

4.    Результат: .

Переменная s означает перенос в старший разряд и всегда принимает значение 0
(при a_i+b_i+s < B)или 1 (при a_i+b_i+s ≥ B). На шаге 2.1 Может произойти не более одного переноса. Действительно:

a_i+b_i+1 < (B-1)+(B-1)+1 < 2B-1<2B.

Вычитание аналогично сложению изменение только в шаге 2.1. .

В этом случае если t отрицательное то у следующего элемента занимается 1.

Сложность алгоритма сложения и вычитания равна О(п).

Код функции summa(сумма):

 

for (i=0;i<=32;i++){

s=a[i]+b[i]+buf; //Общее значение

c[i]=s;//число заносимое в ячейку

buf=(s)>>8;//остаток

}

Код функции sub(разность) c = a-b:

 

for(i=0;i<=31;i++){

       s=a[i]-b[i]+buf;

       buf=s>>8;

       c[i]=s;

 }