Варианты алгоритма возведения в степень: повышение точности и ускорение
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: налоги и налогообложение, план дипломной работы
| Добавил(а) на сайт: Gershel'man.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
К сожалению, выигрыш в скорости абсолютно не ощущается. Это вполне объяснимо: согласно приложению C (“IA-32 Instruction Latency and Throughput”) документа [3], из всего этого фрагмента основная вычислительная нагрузка ложится на трансцендентные (ответственность за не вполне корректное применение термина ложится не на меня, а на господ из Intel) операции, а именно – FYL2X, FRNDINT, F2XM1 и FSCALE. Количество же этих операций в предложенном алгоритме и их общее число в реализации функций ln(x) и exp(x) в RTL Delphi одинаково.
Конечно, хотелось бы увеличить и скорость вычислений. Но мир не идеален, и за это придется расплачиваться все той же точностью. Как правило, в каждой ситуации существует предел допустимых погрешностей при расчетах. В иллюстративных целях я задался максимальной допустимой относительной погрешностью 0,0001=0,1%. В действительности, как будет видно из графиков относительной погрешности, удалось достичь еще большей точности.
Дальнейшие наши действия должны состоять в том, чтобы исключить трансцендентные математические операции. Ясно, что всякое представление в виде конечной композиции элементарных арифметических операций некоторой функции, неразложимой в такую композицию, является приближением исходной функции. То есть задача ставится так: нужно приблизить используемые трансцендентные функции композициями элементарных операций, оставаясь при этом в допустимых для погрешности пределах.
Аппроксимация функции 2x
Эта мера позволит нам избавиться сразу и от длительной F2XM1, и от выполняющейся ненамного быстрее FSCALE.
Существует бесконечное множество способов приблизить функцию f(x). Один из наиболее простых в вычислительном плане – подбор подходящего по точности многочлена g(x)=anxn+an-1xn-1+...+a1x+a0. Его коэффициенты могут быть постоянны, а могут некоторым образом зависеть от x. В первом случае коэффициенты легко найти методом наименьших квадратов, взяв значения исходной функции в нескольких точках и подобрав коэффициенты так, чтобы в этих точках многочлен принимал значения, как можно более близкие к значениям функции (подробное описание полиномиальной аппроксимации функций и метода наименьших квадратов можно найти в книгах, посвященных курсам вычислительной математики или обработке экспериментальных данных). Простота метода оборачивается существенным недостатком: он подчас неплох для выявления качественных тенденций, но плохо отражает исходную функцию количественно, причем, как правило, погрешность растет с уменьшением степени многочлена n, а скорость вычисления g(x) с ростом n падает.
Достойная альтернатива, позволяющая достаточно точно
приближать гладкие кривые, такие, как y=2**x, - аппроксимация сплайнами. Говоря
простым языком (возможно, чересчур простым – пусть меня извинят специалисты), сплайн – это кривая, моделирующая форму, принимаемую упругим стержнем, деформированным путем закрепления в заданных точках. Она проходит точно через
заданные точки, подчиняясь при этом некоторым дополнительным условиям, в
частности, условию непрерывности второй производной. Существуют различные виды
сплайнов. В этой работе достаточно практично использование кубических сплайнов.
Кубический сплайн на каждом отрезке между двумя последовательными (в порядке
возрастания координаты x) эталонными точками (x,f(x)) описывается полиномом
третьей степени g(x)=a3x3+a2x2+a1x+a0, где набор коэффициентов (a0,a1,a2,a3)
свой для каждого отрезка. Поиск этих коэффициентов – не слишком сложная задача, но описание метода ее решения выходит за рамки этой статьи. 
Таблица
коэффициентов, получающаяся после учета всех замечаний этого раздела, прилагается к статье.
Итак, я ограничусь лишь использованием полученных мною значений коэффициентов. Чтобы обеспечить необходимую точность на промежутке 0<=x<999, мне понадобились в качестве эталонных 2039 точек, которым соответствовали значения x=(i-40)/2, i=0..2038. Сорок значений на отрицательной полуоси нужны были только для того, чтобы отразить поведение сплайна в этой части плоскости, слегка скорректировав таким образом его вид на остальных отрезках; в вычислениях эти 40 отрезков не участвуют, т.к. для значений x<0 можно воспользоваться (без ощутимого проигрыша в скорости или точности) соотношением 2**(-|x|)=1/(2**|x|).
Итак, у нас есть таблица коэффициентов, представленная в виде массива из 1999 блоков по 8*4 байт (если для представления коэффициентов используется тип double). На Object Pascal такой массив описывается типом
|
array [0..1998] of packed record c3,c2,c1,c0:double end; |
На практике возникает тонкий момент. Дело в том, что Delphi почему-то отказывается выравнивать массивы Double’ов по границе 8 байт. Лично у меня получается так, что адрес первого элемента всегда бывает кратен 4, но никогда – 8. Поэтому перед началом массива я вставляю заполнитель, чтобы избежать медленного чтения некоторых double’ов, которые частично лежат в одной 64- или 32-байтной линейке кэша, а частично – в следующей:
|
//Предполагаю, что выставлена опция компилятора {$Align 8} Type TArr=packed record Padding:integer; //Фиктивный 4-байтовый заполнитель - чтобы массив выравнялся по 8 байтам C:array [0..1998] of packed record c3,c2,c1,c0:double end; //Собственно коэффициенты end; |
На вход функции Exp2 поступает единственный аргумент x - возводимое в степень число. Как можно реализовать функцию?
Вот как это сделал я.
|
ПРЕДУПРЕЖДЕНИЕ Как и для предыдущей функции, нужно обеспечить установку бит управления округлением в режим округления к нулю. |
|
function Exp2(x:FLOATTYPE):FLOATTYPE; //0<=x<999 asm fld x call Core_Exp2 //Оформим основную часть в виде процедуры, т.к. она будет использоваться не только здесь - Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини. Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная