Оценка эффективности быстрых алгоритмов для вычисления некоторых классов трансцендентных функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК СССР ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ

На правах рукописи

КАРАЦУБА Екатерина Анатольевна

ОЦЕНКА ЭФФЕКТИВНОСТИ БЫСТРЫХ АЛГОРИТМОВ ДЛЯ ВЫЧИСЛЕНИЯ НЕКОТОРЫХ КЛАССОВ ТРАНСЦЕНДЕНТНЫХ ФУНКЦИЙ

01.01.09 — Математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва —1991

зшюиишь в Imtutjm пр*$1«м ккб«рг*?ж*г

Лхад«мяж Наук CCCF.

Нкучж«?» яуяввадггмь - дахт*р фвзкке-жтшатЕчосих ,

пр#$всеср E.rt, Г]:40яя»кб»

йфжцгшаыгиз »пгши»ак~ xeiv»¡.f фяякки'-тякттжчшяа« шя/х,

ар*$*сп$р B.D. 1илк*л

КЛВДЯДМ фн9ЯК*-Ы*Т«М»ТвИвСЕ!« tlft, ст. кжучмШ «труд*« &.В. Зубвк

Еед/аьа оргыкаиша - Явсаосту» пргбм» пьрвдачи юаф»р«|Щ*а

kttatatBSí Вс^в ССС?

Злчктк двее*£*ацяя сьотокге* " " QlkLQ Ь|оЗ 1991 г. в i-^f í>2 Místt* адевдакгв Сп«чаалиэз{мгв.1яявгг С»лет?» К 003.78.01 прх Института tipejreir с*5срк«тя|ся Aï CCCF п* идрйсуг II73I2V Itatxiat, ji. Вши«»,. 37,-

С дже»ртздж»Я мкжв «эвакшаие* к бабмстска nacwsïjTA.

Автореферат: pastease "30я OKíVj fp^ Í991

г.

Учйаив аякрвт&рь Смцмдж4>[иамш№г& Саз*».

У

А. 3. Кхмуз ждав**

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность rem. Метода быстрого вычисления значений функций включают в себя метопу (тозволятапие вычислить заданную <$у]гкютю о заданной точностью, используя как можно меньшее число элементарных операций. Эти метода, реали: впнныа на электронно-вычислительных машинах не только программным, но и аппаратным образом, позволяют значительно увеличить производительность ЭШ.

Цель работы. Построение алгоритма, с помощью которого можно вычислить быстро значения функций из широкого класса как простейших, так и еыспих трансцендентных функций, а также классических констант Ч- , ¡7Г и <f и некоторых степенных рядов. Получение опенок сложности вычисления заданной функция или числа с заданной точночтыо, близких к окончательным.

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

Практическая ценность. Результаты диссертации расширяют возможности-применения методов быстрого вычисления значений широкого класса функций. Они могут быть использовании при разработке программного и аппаратного обеспечения ЭШ.

Апробация работы. Результаты диссертации докладывались в ИПК на семинаре профессора Е.А.Гребеявхова по методйм математического моделирования, в ИППИ на семинаре профессора Я.А.Бас-салнго по теории информации, на Всесоюзных школах по теории передачи информации и ее приложениям - в г. Теберда в 1989 г. (15-ая школа) и в г. Алма-Ата в 1990 т. (16-ая школа), на 3-ей Всесоюзной школе по супер ЭШ в г. Одессе в 1991 г.

Публикации. Результаты диссертации опубликованы в работах / I/, / 2 / / 3 /.

Научная ковузнэ. Разработан новый алгоритм вычисления значений простейших трансцендентных функций, высших трансцендентных функций, классических констант и степенных рядов.

Структура и о(W^m работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем работы - 95 машинописных страниц, список литературы«включает 35 названий.

' СОДЕРЖАНИЕ РАБОТУ

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

' Начиная с i960 г., когда A.A. Кврацубой бшг обнаружен метод быстрого умножения для двух п, -значных чисел, многие авторы предлагали те или иные методы быстрого вычисления различных функций. Наиболее значительными ореди работ втото направления были работы Шёнхате и Штрассена, построивших елторитм быстрого умножения с опенкой сложности, близкой к окончательной, Ю.Бен-дерского, давшего алгоритм быстрого вычисления значений элементарных алгебреических функпий и Р.Брента, построившего итерационный алгоритм быстрого вычисления простейших трансцендентных функций.-,

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

близка к окончательной.

Далее считаем, что числа записаны з двоичной системе исчисления. Через л, ) обозначим количество элементарных операций, достаточное для вычисления функггаи £ ( 2 ) о точностью 2~а (сложность вычисления футшии ^ ( 2 )), 2 - здесь и далее, комплексное число.

Из шгеггерэчиответных работ для элементарных алгебраических фушшвЯ имеем:

Простейшими трансцендентными фушшиями будем называть функ-*

ти £ , йл X и т.д., их суперпозиции, футшии, обратные к ним, в суперпозиции обратных фу ним Я.

Глава I "Быстрые вычисления значений простейших трансцендентных функций" посвящена доказательству утверждения, что любую простейшую трансцендентную функцию при любом значения аргумента из области определения этой функции мохяо вычислить быстро. Тлава состоит из четырех параграфов. В § I доказываются три основные леммы о быстром вычислении спепиального вида суш, в которых, по существу, и раскрываются особенности нового алгоритма. _ -

Леша I. Пусть ы - гг -значков число. ъ - натуральное число,

и целое число & определяется равенством:

а-г!^, I - 1 *

о1_

Тогда для вычисления а, достаточно

операшй.

Лемма 2. Цусть о£. число, целые числа

- "I -знатное целое число, г - натуральное й. и -ё определяются равенствами:

а = 1)! «2. 5 >

> а. _ <Х 1 • 4 е/ , а-

I = .1!а« -зтря~* ... С-1)(Я7Т)Гатгт^ ,

& -- Лг! ^ т

г

Тогда для вычисления <Х и ^ достаточно

О (г (гч. + ^ г) а Родгп. Со^ гт. )

операций. •

Лемма 3. Цусть ог.; , , I ^ е I, 2, г - /п. -знач-ные целые числа, и целые числа Л и $ определяются равен-

ством г

.а с Г"1 Ь 6;

I I

Тогда для вычисления а и Ь достаточно 1Н г £о<11т. £о<1 гш ) операций. • .

В § 2 доказывается тесрока о быстром вычислении значений функции ^ - е , х - здесь и далее вещественное число. Теорема I.

ос '

Пуста ^ = ^ ( х ) = е . Тогда справедливо соотношение

(п) » Ос п. вод Чй^ п )

В § 3 доказывается георема о быстром вычисления значений функций у = ¿иг X и у = СЯХ .

Теорема 2.

Пусть у = ас иди = с<я ос . Тогда справедливо соотношение

В § 4 доказываются теоремы о быстром вычислении знача ¡гай

- простейшей трансцендентной функции вещественной переменней;

- функции ;

- функций ^ = &п £ и у = 631 £ ;

- простейшей трансцендентной функции комплексной переменной.

Теорема 3.

Пусть у в дс ) - простейшая трансцендентная функция.

Тогда

Теорема 4. .

Пусть у = ^ ( * ) » ■ е * .. Тогда .

ОСп-Оо^л^Еоуп. )

Теорема 5.

Пусть ^ = |(£) = Яп2 или | ( 2- ) = Ом г •

= )

Теорема 6.

Пусть у = ) - проотейшая трансцендентная функция.

Тогда

= 0(л л )

Глава 2 "Вютрые вычисления классических констант" посвящена доказательству утверждения, что классические константы , и константу Эйлера Г"" ,

Л- у „ -4-

Г -- а + ... + ~Ы "

моено вычислить быстро. Здесь и далее считаем, что 5а( п. ) -сложность вычисления константы о, о точностью 2~ а . Глава состоит из трех параграфов.

6 § I доказывается теорема о быстром вычислении числа е .

Теорема 7.

$4<л) = ОспЬ^п Ноу^п)

В § 2 доказывается теорема о быстром вычислении числа от •

Теорема 8.

Vго " 0(п ёо^п СеуРоц п.)

Б § 3 доказывается теорема о быогром вычиолеыии числа у .

• Теорема 9.

.^(л.) ~ 0 (аЯос^п (од я )

Глава 3 "Шстрые вычисления значений высших трансцендентных функций в степенных рядов специального вида" посвящена доказательству утверждений, что при помощи предложенного метода при алгебраических значениях параметров и аргумента можно вычислить быстро:

- р -функции, гипергеоыегричеокую функцию и вырожденцу» гипергеометричвсвдх) функцию;

. . - любую специальную фунщию, которая выражается посредством

?

арифметические операций через простейшие трансцендентные функции, классические константы и через Г7 -функцию и гипергеометрическую функцию или через Р -функцию и вырожденную гипергео-матрическую функцию (к ним относятся, например, шаровые и цилиндрические функции, интегралы от цилиндрических функций и от Фунх-цийпараболичэского цилиндра, интеграл вероятности и т.д.);

- степенные ряды специального вица.

Глава состоит из четырех параграфов.

В § I доказывается теорема о быстром вычислении значений функции ^ = Р( х ) при рациональных значениях аргумента ОС и сформулирована теорема о быстром вычислении значений функции Р( * ), l=oC+tp , ci и р - рациональные числа.

Теорема 10.

Пусть ij = Р С х ). Тогда для рациональных значений аргумента ос справедливо соотношение:

Spin.) - Oin- toc^n-tog tocj ъ) . Теорема II.

Пусть ^ = Pi jt ), 2- = di + . Тогда для рациональных cL и р оправедливо соотношение

■Sp ( it) s 0 (а. &><j &>cj а )

В § 2 доказывается теорема о быстром вычислении значений функции ^ = Р{ X ) при алгебраических значениях аргумента . ,

. Теорема 12. ,

Пусть у «* Р { х ), ос = oL - алгебраическое чиоло. Тогда справедливо соотношение .

5Р (а) - &><j я )

.8

В § 3 показывается следующая теорема.

Теорема 13.

Пуоть у = р(а#£,С.,г ) - гипергеоматричвскея функция; а. > & V С • i - комплексные чиола о рациональными вещественной и мнимой частями t ¡21 < i . Тогда справедливо соотношение

Sp(n-) = 0 (п.&>^3п во^Оорп)

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

Теорема 14.

Пусть t| = P(ü..S,e,fc)- тшергеоыетричеокая функция; а . & , С , я - аягебреические числа, Jil<l . Тогда справедливо соотношение

S_ (п.) = О ( rv а п. )

Теорема 15.

Пуоть вырожденная гидаргеометри-

чзекая функция; ol , jr, i - алгебраические числа, Iii <1 -Тогда справедливо соотношение

¿„(М s О (п. п. £o<j to<J п.)

Напомним, что по определению

F<a,€,cf* > - i + jreb + __p-ar ♦ , <I>, s _ , . st jSl + «tun) z1 4

ru,r,0 - i + r i'. rTfHTÄT •••

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

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

Теорема 16.

Пусть ^ . fru J-П т ,

П'О

О- ( ) > "é < п. 3 — целые чиола, £ - алгебраическое чиоло, причем )üCn.)|¿rt-A , D ¿ l$>(n)i ¿ пА , А - постоянная; Сл .

Г1 * Ä ) - día) 7J ,

Cin), oi ( a,) - целые числа, £ - алгебраическое число, причем |cU)| ¿ h 6 , О -С loi(n)¡ ¿a , ß - постоянная. Тогда справедливы ооотношения

п. )

Sjaín.). ~ 0 (п. &<j-(o£n. )

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

Список работ, содержащих результата диосертации:

1. Карацуба Е.А. О новом методе быстрого вычисления трансцендентных функций. Успехи Мат. Фук, 199Г, т.46, вып.2{278), с.219-220.

2. Карацуба Е.А. О быстром вычзолезии трансцендентных функций, Докл.AJÍ СССР, 1991, т. 218, Я 2, с. 278-279.

3. Карацуба Б.А. Быстрые вычисления трансцендентных фунх-. ций. Проблемы Пар. Инфор., 1991, * 4, o.Sí 'iiO