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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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