Алгоритм умножения

            }

            for (int i = 0; i < first_summand.Length; i++)

            {

                sum += (int.Parse(first_summand[i].ToString()) + int.Parse(second_summand[i].ToString()) + dop) % 10;

                dop = (int.Parse(first_summand[i].ToString()) + int.Parse(second_summand[i].ToString()) + dop) / 10;

                if (i == first_summand.Length - 1 && dop != 0)

                {

                    sum += dop;

                }

            }

            reverse(sum, ref sum);

        }

 

 

 

 

 

 

 

 

 

 

 

 

5 ОПЕРАЦИИ НАД ДЛИННЫМИ ЧИСЛАМИ

 

 

Прежде всего, необходимо уточнить интерфейс. Можно определить операторы как части класса, и  это будет достаточно удобно в  использовании. Однако при вычислении C=A+B  оператор не сможет получить доступ к числу C. Поэтому придется создавать  временное число Temp = A+B, которое затем будет скопировано в C. Лишних операций и использования дополнительной памяти можно избежать, если записывать результат в C напрямую. Исходя их этого, в качестве интерфейса выберем внешние функции, которые принимают в качестве параметров исходные данные и число для записи результата.

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

 

Схема для сложения такова: складываем цифры слева направо (цифры хранятся в обратном порядке). Если зафиксировано переполнение (т.е. при сложении получена цифра, большая максимально возможной в данной системе счисления), то происходит “перенос” (carry) в следующий разряд

 Вычисление C = A+B, работает вызов вида Add (A, B, C).Максимальный размер C должен быть достаточен для хранения суммы

 

static void Add(BigInt A,BigInt B, ref BigInt C)

{

 ulong i;

int temp; // temp здесь и  далее играет роль “временной”  цифры,

           // до выполнения переноса. Возможно, temp > BASE.

 C.Coef = new int[A.Size+1];

short carry = 0;

// Добиваемся B.Size ≤ A.Size.

if (A.Size < B.Size)

{  

  Add(B, A, ref C);

  return;

}

// Теперь B.Size ≤ A.Size.

 // Складываем два числа, i - номер текущей цифры

 for (i = 0; i < B.Size; i++)

{

  temp=A.Coef[i]+B.Coef[i]+carry;

  if (temp >= Base)  // переполнение. Перенести единицу.

  {

   C.Coef[i] = temp - Base; carry = 1;

  }

  else

  {

   C.Coef[i] = temp; carry = 0;

  }

}

// Меньшее число кончилось

for (; i < A.Size; i++)

 {

  temp = A.Coef[i] + carry;

  if (temp >= Base)  // переполнение. Перенести единицу.

  {

   C.Coef[i] = temp - Base; carry = 1;

  }

  else

  {

   C.Coef[i] = temp; carry = 0;

  }

}

// Если остался перенос  – добавить его в дополнительный  разряд

 if (carry == 1)

{

  C.Coef[i] = carry; C.Size = A.Size + 1;

}

else C.Size = A.Size;

}

 

Вычитание осуществляется аналогично, с той лишь разницей, что осуществляется перенос “заимствования”. Мы работаем с положительными числами, поэтому если вычитаемое большое по размеру – происходит выход.

Если длины одинаковы, но одно больше другого – это  приведет к тому, что в конце  процесса останется неиспользованное заимствование, а результат будет дополнением до Base^B.Size. Например, при обычном вычитании 35 – 46 = -11, при описанном выше 35 – 46 = 89, так как выполняется равенство 89 = 100 – 11 (89 – это дополнение 11 до 100).

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

5.2 Умножение

 

1. Обнулить C.

2. Обнулить i.

3. Вычислить временный результат, соответствующий умножению i-й цифры A на число B, в процессе вычисления сразу прибавлять его к C, начиная с i-ой позиции. Если получившаяся цифра C больше Base – сделать перенос.

4. Если A не кончилось, увеличить i на единицу и идти на шаг 3.

5.3 Деление

 

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

Рассмотрим действия, совершаемые при делении A=68971 на B=513 (рисунок 1.5.1). Здесь n=5, m=2.

 

Рисунок 1.5.1 Пример деления длинных чисел

(горизонтальные линии  проводятся между шагами)

 

1. i = (индекс старшего коэффициента A) = 4

1. «Угадываем» q[0] = 1.

1.2 Вычитаем сдвинутое B*1 = 513 из A (на бумаге при этом пишем только значимую для следующего шага часть A)

2. i = 3.

1. «Угадываем» q[1] = 3.

2. Вычитаем сдвинутое B*3 = 1539 из A.

3. i = 2.

1. «Угадываем» q[3] = 4.

2. Вычитаем сдвинутое B*4 = 2052 из A.

4. i < m = 2, процесс закончен. То, что осталось от A после вычитаний, является остатком деления.

Все очевидно, за исключением  одного “творческого” шага – «угадывания». Как заставить компьютер генерировать правильное частное q? Или хотя бы достаточно близкое к нему число?

Пусть очередной шаг  представляет собой деление некоторого U = (u₀, u₁, …, u_n) на B=(b₀, b₁, …, b_n-1). Если b_n-1 ≥Base/2, то можно доказать следующие факты.

1. Если положить qGuess = (u_n*Base + u_n-1)/b_n-1, то qGuess-2 ≤ q≤qGuess. Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного, но может быть больше на 1 или 2.

2. Если же дополнительно выполняется неравенство qGuess*b_n-2 > Base*r + u_n-2, где r – остаток при нахождении qGuess и qGuess ≠ Base (условие 2), то qGuess-1 ≤ q ≤ qGuess, причем вероятность события qGuess = q+1 приблизительно равна 2/Base.

Таким образом, если b_n-1 ≥ Base/2, то можно вычислить qGuess = (u_n*Base + u_n-1) / b_n-1 и уменьшать на единицу до тех пор, пока не станут выполняться условия (2). Получившееся значение будет либо правильным частным q, либо, с вероятностью 2/Base, на единицу большим числом.

 

 

 

 

 

 

 

 

 

 

6 ПРОБЛЕМЫ В ХОДЕ ВЫПОЛНЕНИЯ КУРСООЙ РАБОТЫ

 

 

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

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

Изначально результаты деления  и умножения чисел  на 2 сразу записывались в listbox (в  процессе подсчета) и после каждой следующей операции дописывались туда из-за чего умножение длинных чисел происходило значительно дольше из-за того, что вывод информации на экран занимает относительно много времени (речь идет о долях секунд и даже меньше, но при большем объеме вывода информации это очень заметно) !

После долгих экспериментов, я нашла, наконец решение проблемы. А именно: записывать результаты вычислений в строку (в тип string) - это позволяет не тратить лишнее время. А после всех вычислений надо было вывести эту строку.

Кодовая часть решения  проблемы:

 

public void div_2_1(string a, ref int count, ref int[] chetn)

        {

            count = 0;

            string b = "";

            string[] str = { a };

            string div2 = "";

            int k = 0, q = 1, q1 = 0;

            if (int.Parse(a[a.Length - 1].ToString()) % 2 == 1)

            {

                Array.Resize(ref chetn, chetn.Length + 1);

                chetn[0] = 0;

                q1++;

            }

            delenie_na_2.Text = str[0] + "\n";

            while (a.ToString() != "1")

            {

                a = div_2(a, k, b);

                Array.Resize(ref str, str.Length + 1);

                a = delete_0(angel);

                str[q] = a;

                if (int.Parse(a[a.Length - 1].ToString()) % 2 == 1)

                {

                    Array.Resize(ref chetn, chetn.Length + 1);

                    chetn[q1] = q;

                    q1++;

                }              

                //delenie_na_2.Text += str[q] + "\n";  было

                div2 += str[q] + "\n"; //стало

                q++;

                count++;

            }

            delenie_na_2.Text = div2;  //стало

        }

 

 

 

 

 

 

 

 

 

 

ВЫВОДЫ

 

 

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

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

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

В общем, это очень  интересный и оригинальный способ, показывающий нам, что не все свойства чисел до конца исследованы человеком.

Этот метод умножение  положил начало к вычислению больших чисел, а это, прошу заметить, не только очень важно для наук, но и интересно даже для людей далеких от математики.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ЛИТЕРАТУРЫ

 

 

1.  Липский, В.  Перестановки // Комбинаторика для программистов [Текст]. – М.: «Мир», 1988. – С. 214.

2. Морозова, О. И. Применение ЭВМ для решения задач математической логики и теории алгоритмов [Текст]: учеб. пособие / О. И. Морозова, Ю. К. Чернышев.; Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2010.- С. 71.

3.  Генерация перестановок в лексикографическом порядке // «Генерация перестановок в лексикографическом порядке» [Электронный ресурс] / Режим доступа: \www/ URL: http://fit.nsu.ru/data_/courses/niu/daio_komb_alg_uchpos.pdf - 14.05.13.

 

4. Томас Кормен, Чарльз Лэйзерстон, Рональд Ривест «Алгоритмы построения и анализ» // Алгоритмы и структуры данных, анализ алгоритмов [Электронный ресурс] / Режим доступа: \www/ URL: http://e-maxx.ru/bookz/files/cormen.pdf - 10.04.13.