I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы




Скачать 264.68 Kb.
НазваниеI. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы
страница1/4
Дата28.11.2012
Размер264.68 Kb.
ТипДокументы
  1   2   3   4
 

 

БЫСТРЫЕ АЛГОРИТМЫ И МЕТОД БВЕ



Е.А. Карацуба

 

 

I. БЫСТРЫЕ АЛГОРИТМЫ.

 

 

Область вычислительной математики, которая называется быстрые алгоритмы, появилась в 1960 году.

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

 

Опр.1. Запись знаков 0 , 1 , плюс, минус, скобка; сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.

 

Быстрые алгоритмы — это область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций. Тем самым, алгоритмы, которые можно назвать быстрыми, являются реальными алгоритмами. Такие алгоритмы, реализованные на ЭВМ в программном (а иногда и аппаратном) обеспечении позволяют существенно увеличить производительность работы компьютера, а иногда и решить задачи, размер которых не позволял найти решение путём применения обычных методов вычисления. Вопрос о размере задачи, которую можно решить за некоторое время с помощью данного компьютера, приводит нас к понятию сложности вычисления.

Первые постановки задач о битовой сложности вычислений (1956 г.) принадлежат А.Н. Колмогорову http://mech.math.msu.su/probab/Kolmogorov/kolmogorov.html [36], [37], который в то же время подчёркивал, что "цикл моих работ по теории информации был создан под большим влиянием публикаций Норберта Винера http://erudite.nm.ru/WienerNorbert.htm и Клода Шеннона http://www.astronet.ru/db/msg/1187395 ."

Прежде чем ввести понятие сложности вычисления, определим, что значит вычислить функцию в заданной точке. Рассмотрим наиболее простой пример вычисления вещественной функции y = f(x) вещественного переменного x , a ≤ x ≤ b .

Пусть f(x) на (a,b) удовлетворяет условию Липшица порядка α , 0 < α < 1 , так что при x1, x2 (a,b) :

|f(x1) - f(x2)| ≤ | x1 - x2 |α .

 

Пусть n — натуральное число.

Опр.2. Вычислить функцию y = f(x) в точке x = x0(a,b) с точностью до n знаков, значит найти

такое число A, что

 

| f(x0) – A | ≤ 2⁻ⁿ.

 

Опр.3. Количество битовых операций, достаточное для вычисления функции f(x) в точке x = x0 с точностью до n знаков посредством данного алгоритма, называется сложностью вычисления f(x) в точке x = x0.

 

Таким образом, сложность вычисления f(x) в точке x = x0 есть функция n; а также f(x) и x = x0 . Эту функцию обозначают символом

sf(n) = sf,x0 (n).

 

Ясно, что sf зависит также от алгоритма вычисления и при разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается "временной" функцией T(n) [35].

Вопрос о поведении sf(n) при n → ∞ для класса функций или конкретной функции f, был впервые поставлен А.Н. Колмогоровым около 1956 года. Поскольку при вычислениях в первую очередь используются четыре арифметических действия: сложение, вычитание, умножение и деление, то прежде всего нужно знать количество битовых операций, достаточное для выполнения этих действий. Из определений 2 и 3 следует, что числа x0 и A можно представить в виде целой части и n двоичных знаков после запятой, т.е.

A = [A] + 0,ν1ν2 ν3 …νn,

x0 = [x0] + 0,μ1μ2μ3 …μn,

 

где νj , μj = 0 или 1 , j = 1, 2, … , n.

Так как целые части [A] , [x0] — фиксированные величины, а n → ∞ , то действия производятся по существу с n -значными числами. Отсюда прежде всего возникает вопрос о сложности вычисления суммы, разности, произведения и частного двух n -значных чисел a и b. Заметим, что деление (с остатком) сводится к сложению, вычитанию и умножению чисел.

Для записи чисел a и b требуется по меньшей мере 2n битовых операций. Следовательно, сложность сложения (вычитания) a и b не меньше 3n битовых операций, и не больше (если делать это обычным способом), чем 4n битовых операций. Таким образом, порядок количества битовых операций, необходимых и достаточных для выполнения сложения (вычитания), один и тот же.

В дальнейшем для краткости, будем называть "битовые операции" просто "операциями".

Следующим вопросом является вопрос о количестве операций, достаточных для вычисления произведения ab, или о сложности умножения. Функция сложности умножения получила специальное обозначение M(n).

Перемножая два n -значных числа обычным школьным способом "в столбик," мы при этом фактически складываем n n -значных чисел. Так что для сложности этого "школьного" или "обычного" метода мы имеем оценку сверху M(n) = O(n²).

В 1956 г. А.Н.Колмогоров высказал гипотезу, что нижняя оценка M(n) при любом методе умножения есть также величина порядка n² (так называемая "гипотеза n² Колмогорова"). На правдоподобность "гипотезы n²" указывал тот факт, что метод умножения "в столбик" известен не менее 4-х тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден.

В 1960 А.А. Карацуба http://www.mi.ras.ru/~karatsuba/ [19], [20], [21] (см. также [35]) нашёл новый метод умножения двух n -значных чисел с оценкой сложности

 

M(n) = O(nlog 23 ), log 2 3 = 1,5849… ,

 

и тем самым опроверг “гипотезу n².” Этот метод впоследствии был назван

"Divide and Conquer" ("Разделяй и властвуй"); другие, используемые в настоящее

время названия этого метода — "Binary Splitting", "Принцип Дихотомии" и т. п.

С момента появления "Divide and Conquer" начала развиваться теория быстрых вычислений.

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

продолжены рядом авторов (среди них были Тоом http://www.de.ufpe.br/~toom/

[48], Кук http://www.cs.toronto.edu/~sacook/

[15], Шёнхаге http://www.informatik.uni-bonn.de/~schoe/index.html

[43]), и в 1971 г. Шёнхаге

и Штрассен http://www.mathe.uni-konstanz.de/mitarbeiter/strassen.html

[44], [45] построили алгоритм с наилучшей на настоящее время оценкой для M(n),

 

M(n) = O(n log n log log n).

 

При построении этого алгоритма кроме "Divide and Conquer" они использовали идею выполнения

арифметических действий по модулю чисел Ферма 22 +1, а также быстрое преобразование Фурье.

На основе "Divide and Conquer" были построены алгоритмы быстрого умножения матриц. Первый

такой алгоритм в 1970 г. нашёл Штрассен [47], в дальнейшем эти исследования были продолжены

Коперсмитом http://www.research.ibm.com/people/c/coppersmith/, Виноградом

http://researchsmp2.cc.vt.edu/DB/db/indices/a-tree/w/Winograd:Shmuel.html [16], Паном

http://comet.lehman.cuny.edu/vpan/ [41] и др.

Приблизительно в это же время стали появляться и первые быстрые алгоритмы для вычисления

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

с остатком, т.е. вычисление чисел q и r в формуле

 

a = qb + r , 0 ≤ r < b,

 

сводится к сложению, вычитанию и умножению, и если a и b являются n -значными числами,

то сложность деления O(M(n)).

Самый простой алгоритм деления заключается в вычислении методом Ньютона обратной величины

1/b с точностью до n знаков с последующим умножением на a по алгоритму быстрого умножения.

Пусть надо вычислить x = 1/b, где 1/2 ≤ b ≤ 1 (если это не так, то умножая или деля b на 2N

получим выполнение указанного условия). Возьмём в качестве начального приближения x0 = 3/2 и

вычисляем по формуле

 

xn+1 = 2xn - bxn².

 

Этот метод обеспечивает достаточно быструю сходимость к 1/b, поскольку из равенства xn = 1/b - ε,

следует, что xn+1 = 1/b - bε².

Для извлечения корня k -ой степени из числа, т.е. для вычисления a1/k можно также воспользоваться

методом Ньютона. Пусть k ≥ 2 — целое число и надо вычислить x = a1/k, где a ≥ (k+1)k. Вычисляем x

по формуле:

 

xn+1 = xn(k+1)/k - xnk¹/(ka).

 

Заметим, что умножением или делением на 2kN можно всегда добиться выполнения для a условия

a ≥ (k+1)k.(иногда это условие оказывается лишним, т.е. указанный процесс быстро сходится и при

других a).

За начальное приближение можно взять, например, одно из двух чисел d или d+1, где

d — целое число, удовлетворяющее условию dk < a ≤ (d+1)k. Тогда одно из чисел |d - z1/k| или

|d + 1 - z1/k| не превосходит 1/2.

Сложность вычисления этим методом будет O(M(n)).

Первые быстрые алгоритмы для вычисления элементарных алгебраических функций, основанные

на методе Ньютона, появились в работах Кука [15], Бендерского http://www.bisguard.com/ [8] и Брента

http://web.comlab.ox.ac.uk/oucl/people/richard.brent.html [11] (см. также [35]).

Используя метод Ньютона можно доказать следующую теорему [11] :

 

Теорема. Если уравнение f(x) = 0 имеет простой корень ζ ≠ 0, f(x) непрерывна по Липшицу

в окрестности ζ , и мы можем вычислить f(x) с точностью до n знаков за O(M(n)j(n)) операций ,

где j(n)положительная , монотонно возрастающая функция, для любого x из окрестности ζ ,

то ζ можно вычислить с точностью до n знаков также за O(M(n)j(n)) операций.

 

В 1976 г. Саламин http://www.ams.org/mathscinet-getitem?mr=53+%237928 [41] и Брент [11]

предложили первый алгоритм быстрого вычисления константы π, основанный на АГС -методе Гаусса

(см., например, [13], [14]). Используя также восходящие преобразования Ландена

http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Landen.html [38], Брент [11]

предложил первые АГС -алгоритмы для быстрого вычисления простейших трансцендентных функций. В

дальнейшем исследование и использование АГС –алгоритмов было продолжено многими авторами,

среди которых были братья Джонатан http://www.cs.dal.ca/~jborwein/

и Питер http://www.cecm.sfu.ca/~pborwein/ Борвайны, написавшие книгу "The Pi and the AGM"

("Пи и АГС") [9], где собрано наибольшее число АГС -алгоритмов.

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

алгоритмы для вычисления некоторых высших трансцендентных функций (гамма-функции Эйлера,

например). Чтобы вычислить такие функции с точностью до n знаков с помощью описанных в книге

алгоритмов требуется

 

O(n3/2 log3 n log log n)

 

операций.

 

О других результатах, связанных с "Divide and Conquer" и быстрыми вычислениями, см. [1], [2], [3], [6],

[7], [17], [18], [35], [40].

 

 

 

 

II. МЕТОД БВЕ.

 

 

Введение. Определение быстрого алгоритма.

 

 

 

Будем называть "быстрым" такой алгоритм вычисления функции f = f(x), что для этого алгоритма

 

sf(n) = O(M(n) logc n) ,

 

где c есть константа. Здесь и далее предполагаем, что для M(n) справедлива оценка Шёнхаге-Штрассена

. Ясно, что для любого алгоритма и любой функции f, выполняется неравентство:

 
  1   2   3   4

Похожие:

I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconОб одном подходе к верификации компьютерных игр
Подход включает метод описания и верификации компонентной модели игры, совместности и сбалансированности правил игры. Расчёт вычислительной...
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconПрограмма дисциплины избранные алгоритмы вычислительной математики и информатики
Вопросы построения оптимальных по сложности и по времени работы вычислительных устройств занимают важное место в технической кибернетике...
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconРеферат по информатике и икт по теме: «Алгоритмы»
Я выбрал тему учебно-методического комплекса «Алгоритмы», так как она является одной из главной тем в информатике
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconНовости на 29. 02. 2012
Строительство малоэтажек обеспечивает застройщикам быстрые продажи, окупаемость инвестиций от года до пяти в зависимости от используемых...
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconВ. В. Быкова Сибирский федеральный университет, Институт математики
Следовательно, с алгоритмом a можно связать числовую функцию t – функцию временной сложности, которая устанавливает время работы...
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconРеферат по информатике и икт по теме: “ Разветвляющиеся алгоритмы”
Я выбрал тему: «Разветвляющиеся алгоритмы», потому что они очень часто применяются в алгоритмизации и программировании. Без знания...
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconРабочая программа по дисциплине "Структуры и алгоритмы обработки данных" специальности 230105 (220400) "Программное обеспечение вычислительной техники и автоматизированных систем"

I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconПрограмма курса лекций «алгоритмы дискретной оптимизации»
Алгоритмы вставки и удаления за константное время. Применение стеков для вычисления последовательности операций в обратной польской...
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconМетодические указания по выполнению контрольной работы №1 по дисциплине Информатика На тему: Линейные алгоритмы. Разветвляющиеся алгоритмы для студентов II курса заочного отделения специальности
Контрольная работа — это самостоятельная работа студента по дисциплине «Информатика»
I. быстрые алгоритмы. Область вычислительной математики, которая называется быстрые алгоритмы iconВыпускная работа по основам информационных технологий
Объем генетической информации, накапливаемой в банках данных, начал увеличиваться с возрастающей скоростью после того, как были разработаны...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница