Ознакомление с простейшими арифметическими алгоритмами и методами оценки их сложности (Практическое занятие № 2)

Практическое занятие №2 (ТСО).

Цель занятия :Ознакомиться с простейшими арифметическими алгоритмами и методами оценки их сложности.

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

где  - ² наиболее значимая половина ²  числа , а  - ² наименее значимая половина ²; подобным же образом , .

Например: Представим в подобной форме число .

 Теперь мы имеем .

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

Если - время, необходимое для выполнения умножения  - разрядных чисел, то мы имеем

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

,

если выбрать - достаточно большим, с тем , чтобы это неравенство выполнялось при , получим

То есть время, затрачиваемое на умножение, можно сократить с величины порядка  до величины порядка , и, конечно, при большом

этот алгоритм гораздо быстрее.

Похожий, но более сложный метод выполнения умножения с временем порядка

 был впервые предложен А. Карацубой.

Время выполнения можно сократить еще больше, если заметить, что только что расмотренный метод является частным случаем (при  ) более общего метода, который дает

 

для любого фиксированного . Этот более общий метод можно получить следующим образом. Разобьем

    и     

на  частей:

            

где каждое  и каждое  являются  разрядными числами. Рассмотрим многочлены

,   

и положим

.

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

Этого можно достичь вычисляя

.

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

Теорема.

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

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

Прежде чем рассмотреть алгоритм Тоома-Кука, разберем один пример. На этом примере нельзя увидеть эффективность метода, поскольку мы имеем дело с небольшими числами. Но можно увидеть некоторые полезные упрощения, которые применимы в общем случае.

Пример.

Предположим, нам нужно умножить   на . В двоичной системе счисления  на . Пусть . Многочлены  ,     .

Отсюда находим :

(4.1)

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

Для нахождения коэффициентов многочлена

 при заданных значениях  можно воспользоваться одним интересным небольшим алгоритмом. Сначала запишем

, где

 и где  неизвестны, равно как и . Теперь

, и по индукции находим, что для всех

Обозначая левую часть выражения через  мы видим, что

и .

Таким образом, коэффициенты можно вычислить с помощью очень простого метода, который можно продемонстрировать для многочлена , определенного соотношениями (4.1):

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

В общем виде можно записать

эта формула показывает, каким образом из коэфициентов  можно получить коэффициенты :

Последовательно получаются коэффициенты многочленов  и т.д.

Согласно последней таблице мы имеем

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

На этой идее основан алгоритм Тоома-Кука. Этот алгоритм позволяет существенно улучшить оценку сложности.

Теорема.

Существует константа , такая, что время выполнения алгоритма С меньше циклов.

Задание. Найти методом Карацубы произведение двух чисел  и , где  - номер по журналу. Оценить сложность вычислений.