Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 21
Текст из файла (страница 21)
Важность коэффициента качества в том виде, в каком он определен выше, заключается в том, что можно ответить на вопрос об эффективности математического обеспечения или целесообразности его улучшения. Степени числа 2 Подпрограмма вычисления величин М(!) = 2', заимствованная из приложения 1, имеет вид 2000 1 5иьгаи»пе: Се! во нега оГ 2 2010 01М М(Р) 2020 1 0 2030 М(0)И1 2040 М(1+1)=М(1)+М(1) 2050 1 1+1 2000 17 1<Р тнйй СОТО 2040 2070 ИЕТСИИ Переменной Р = !ой, Уэ', для которой предварительно дается описание, должно быть присвоено ее числовое значение в операторе 107 размерности; например„ если Р = 10, то оператор размерности будет иметь вид 2010 Р1М М (1О).
Однако в строке 2060 может быть использован символ Р. В результате данная подпрограмма осуществляет присвоение конкретных значений элементам М(0), М(1), ..., М(Р). Например, если Р = 5, то элементам массива М( ) будут присвоены следующие значения: и!г! О ! ! 2 2 4 3 8 4 16 5 32 Первый элемент этой таблицы, а именно М(0) = 1, определяется оператором строки 2010, а последующие элементы получаются удвоением очередного значения. Удвоение осуществляется сложением, а не умножением на 2, так как сложение реализуется быстрее, чем умножение. После каждого присвоения обеспечивается возврат к операции удвоения, что повторяется до тех пор, пока количество циклов не окажется равным Р. Затраты времени на эту процедуру должны быть пропорциональны Р.
Поэтому после нормировки относительно г!Р вертикальный уровень полоски, соответствующей степени числа 2 (рис. 8.4), монотонно убывает до минимального уровня по закону А! '. Как видно на полосковой диаграмме, предварительное составление таблицы степеней числа 2 для последовательностей большой длины требует пренебрежимо малых затрат времени по сравнению с суммарным временем счета. Тригонометрические функции Для последовательности данных длиной А/ требуются синусы и косинусы, представляющие собой функции всех аргументов, являющихся целочисленными кратными (1/Ж)-й части окружности.
Поэтому при заданном /!/ целесообразно составить таблицу, элементами которой будут являться эти заранее вычисленные значения. Один из методов выполнения этой процедуры иллюстрируется в приведенной в приложении 1 программе ЕНТВАЕ: ЗОБО С(1) СОЗ(А) 3070 ИЕХТ 1 3030 ЕЕТОЕИ В результате того, что эти величины рассчитываются раз и навсегда, исключается какое-либо повторное выполнение процедуры предварительного вычисления.
Однако полосковая диаграмма показывает, что на вычисление тригонометрических функций затрачивается значительная доля общего времени счета; число этих рассчитываемых значений существенно превышает степени числа 2, пропорциональные Ж, а не Р. После нормировки относительно произведения ХР график для соответствующей полосы монотонно убывает по закону Р ', но не до нуля, поэтому большое внимание уделяется сокращению временных затрат. Многое при этом зависит от самой ЭВМ, так как вычисление тригонометрических функций осуществляется в ЭВМ различными методами в зависимости от реализуемой точности и других факторов.
При этом один из наиболее эффективных методов расчета заключается в вычислении в первую очередь тангенса, обозначаемого ц а затем в получении косинуса и синуса соответственно по формулам (1+!з) пя и !(1+ !') "'. Естественно, это необязательно знать пользователю, и может оказаться неожиданностью выявление того факта, что синус и косинус могут быть вычислены гораздо быстрее в результате замены вышеприведенных строк подпрограммы следующими: 3030 ЕОЕ 1 ! ТО И/4 3040 А А+И ЗОБО С(1) СОЗ(А) ЗОБО З(1) ТАИ(А)вС(1) 3070 ИЕЕТ 1 Результаты могут быть получены с гораздо более высокой скоростью с помощью фуццаментального метода, уходящего корнями к Клавдию Птолемею. Этот метод вообще не зависит от реализуемых тригонометрических функций.
Метод этого вида представлен в при- 3000 ! ЗвЬговв1вв: Ое! я!вев впв севглев 3010 И 2*81/И 3020 А О 3030 ЕОЕ 1 ! ТО И 3040 А А+И ЗОБО З(1) 318(А) !08 Рнс. 8.5. Геометрическая интерпретация коэффициентов С н 3„, лля в = !6. 109 ложении 1 в виде части подпрограммы ! НТЯ/В, которая может быть включена в программы общего характера. Знание величин соя(2лл/М) и з!п(2лл/М) для целочисленных значений л, изменяющихся от 0 до М вЂ” 1, равноценно наличию информации о координатах М точек, равномерно распределенных вдоль окружности единичного радиуса, как это показано на рис. 8.5,а. Однако если известны координаты этих точек только в пределах одного октанта (рнс.
8.5, б), то могут быть восстановлены координаты и всех остальных точек. С другой стороны, оказывается достаточным знание только координат точек в пределах одного квадранта (рис. 8.5, в). Быстрое вычисление синусов Табулнрование синусов, аргументы которых составляют долю окружности единичного радиуса, не является достижением сегодняшнего дня, а было достаточно развито еще 1800 лет назад Птолемеем. Более эффективная процедура вычисления синусов по сравнению с использованием встроенных программ, реализуемых разработчиками ЭВМ, может быть изучена исходя из опыта предыдущих столетий. Идея Птолемея заключалась в переходе от грубого к точному разбиению окружности.
Из теории правильных многоугольников известно, что длины хорд, стягивающих дуги с центральными углами 60 и 72', соответственно равны сЬ60* = 1 и сЬ72' = 1,17557, где сЬО = 2з!п(0/2) — длина хорды, стягивающей дугу с центральным углом О, для окружности единичного радиуса. Согласно изящной теореме Птолемея, длина хорды, соответствующей разности задан,ных центральных углов, может быть получена из соотношения сЬ(а — (3) = сЬасЬ(л — (3) — сЬ(л — а)сЬ(1, эквивалентного выражению з!п(а — (3) = я!пасоя(3 — сояаз!пб. По известным значениям сЬ60' и сЬ72' Птолемей мог, таким образом, оценить сЬ 12', а также длины хорд для центральных углов, кратных 12'. Получающаяся при этом таблица эквивалентна таблице, составленной из синусов углов, кратных 6'.
В соответствии с теоремой Птолемея утверждается, что для четырехугольника АВСР произвольной формы (рис. 8.6), вершины которого лежат иа окружности с центром О, имеет место равенство АС ВР = АВ.СР + АР.ВС. Для четырехугольника, имею!цего прямоугольную форму, как частный случай получаем теорему Пифагора. При РОВ = 2а и СОВ = 2р получаем теорему Птолемея для синуса разности углов.
Табличные данные для угла 12 применительно к обозначениям, принятым в этой книге, соответствуют случаю М = 60. Для перехода к более мелкому разбиению окружности Птолемей ввел в рассмотрение метод, эквивалентный методу определения длины хорды, стяги- !!О Ю Рлс. 8.6. Теорема Птолемея: АС. ВР = АВ СР -1- АР. ВС. вающей половину дуги: сЬ О/2 = (2 — сЬ(л — 0)3'", который позволил получить результаты вплоть до угла 0,75' и кратных ему значений, что соответствует М = 480.
Этот метод не пригоден для углов, кратных 1'. Однако Птолемей исходил из неравенства сЬО/сЬф < О/ф при 0 > ф. Таким образом, сЬ! /сЬ0,75' < 4/3, сЬ 1,5'/сЬ1' < 3/2. С учетом того, что сЬ1,5' = 0,026179, а сЬ0,75' = 0,013090, из системы этих двух неравенств можно заключить: 0,0174528 < сЬ 1' < 0,0174532. Так как различие правой и левой частей начинает проявляться с шестого десятичного знака, это грубое приближение, но можно повысить точность вычислений, развив метод Птолемея *. Интересным представляется вывод для хорды, стягивающей дугу 1 (илн для аш 0,5'), дальнейшее применение правила разбиения на две равные части позволило Птолемею составить таблицу длин хорд для щ!тервалов, следующих через 0,5' (для синуса — через каждые 0,25'), с точностью до пятого десятичного знака.
Так как эта таблица соответствует случаю М = 1440, она отвечает требованиям программ вычисления БПФ, используемых в настоящее время. е Высокий уровень этой традиции бмл продолжен Архимедом, который установил, например, что 256/153 < .„/3 < ! 351/780 (т. е, 1,732026 < < 1 732050 < ! 732051) Если составление таблицы начать с элементов в(л((я/8), 1= 1, 2, 3, 4, т.е. для В, следующих через интервалы 22,5', то можно перейти к таблице, составленной из элементов, следующих через 11,25', путем вычисления синусов каждого из промежуточных значений аргумента 0 исходя из определенных значений функции яп(0+ 11,25*).
Формула для разности имеет вид яп 0 = (1/2) вес !) 1ял(0 + В) + ял(0 — р)3. Поправочный коэффициент (1/2)вес)3 может быть получен из формулы, определяющей длину хорды, стягивающей половину первоначальной дуги; для этой формулы исходной величиной является: (1/2) вес 11,25' = 0,509795579. Таким образом: ( 1/2) вес В/2 = 12 + 1/(1/2) вес Я Эта реккурентная формула используется в программе РНТЯЗВ, приведенной в приложении 1. Составление таблицы косинусов представляет собой отдельный вопрос.
В следующем разделе будет показано, что целесообразно располагать таблицей значений 180/2. При наличии такой таблицы косинусы могут быть получены из соотношения сов В = 1 — ял 0 18 В/2. Однако нет необходимости заранее вычислять косинусы в явном виде, так как вместо этого можно использовать ташенсы половинных углов, что и целесообразно осуществлять на практике. Операция быстрого поворота Внутри программы РНТВАБ (строки б! 70, 6180) имеются две операции вида х= В-у япВ, у = у'сов В + х'ил В, которые, очевидно, представляют собой стандартные формулы поворота системы координат на угол В. Для этого требуются четыре операции умножения и две операции сложения, а от эффективности их выполнения в силу частого обращения к этому блоку программы в значительной степени зависит суммарное машинное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
