Как сделать возведение в степень в делфи

Как сделать

Как сделать возведение в степень в делфи


Mk30 © ( 2008-02-17 10:35 ) [1]

держи пример
Х в степени y =
x:=exp(y*ln(x))


MBo © ( 2008-02-17 10:37 ) [2]


Mk30 © ( 2008-02-17 10:54 ) [4]

в переменную =x= у тебя и будет записан искомый результат.
это мы еще на информатике проходили на турбо паскале )))).

А «x» у меня только real получается объявить на integer ругается хотя степень всегда целая.


Mk30 © ( 2008-02-17 11:09 ) [6]


> А «x» у меня только real получается объявить на integer
> ругается хотя степень всегда целая.


Mk30 © ( 2008-02-17 11:17 ) [9]

ну тогда поменяй =х= на любую букву просто.

Так тебе чего надо?
Вообще в степень возвести, или 2 в целую степень?

Если первое, то ответ дали.
Если второе, то 1 shl m

мне нужно возвести 2 в целую степень m


> мне нужно возвести 2 в целую степень m

1 shl m


Семеныч ( 2008-02-17 11:38 ) [13]

> smartleds (17.02.08 11:34) [11]

Так ведь уже ответили: 2 shl m.


Семеныч ( 2008-02-17 11:38 ) [14]

Нечего было уроки прогуливать.


isasa © ( 2008-02-17 15:44 ) [16]


isasa © ( 2008-02-17 15:46 ) [17]

Не, виноват, если m-1, то 2.


Бегущий человек © ( 2008-02-17 18:55 ) [18]


isasa © ( 2008-02-17 21:42 ) [19]

Бегущий человек © (17.02.08 18:55) [18]

Плотно, доходчиво. У меня всегда терпения не хватает.


isasa © ( 2008-02-17 21:46 ) [20]


engine © ( 2008-02-17 21:47 ) [21]

> [20] isasa © (17.02.08 21:46)

наверное, всетаки, не убыточное, а обычное 🙂


Пробегал. ( 2008-02-17 21:49 ) [22]

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


engine © ( 2008-02-17 21:52 ) [23]


vrem_ ( 2008-02-17 21:59 ) [24]

при shl может не вместится результат
автор соглашайся на логарифм, можно же округлить до целого.
(потом приходи спросишь как округлять)


Пробегал. ( 2008-02-17 22:01 ) [25]

engine © (17.02.08 21:52) [23]

нет, ну я имею в виду возведение в степень для произвольного числа.

так а какой способ быстрее для возведения ЦЕЛОГО в целую степень?


vrem_ ( 2008-02-17 22:06 ) [26]

Пробегал. (17.02.08 22:01) [25]
сдвигаешь на каждое количество битов в показателе и складываешь


isasa © ( 2008-02-17 22:43 ) [27]

engine © (17.02.08 21:47) [21]

наверное, всетаки, не убыточное, а обычное 🙂


isasa © ( 2008-02-17 22:47 ) [28]

vrem_ (17.02.08 22:06) [26]

Пробегал. (17.02.08 22:01) [25]
сдвигаешь на каждое количество битов в показателе и складываешь

🙂
А естественным путем, т.е. умножением, не?


Marser © ( 2008-02-18 00:34 ) [29]


> vrem_ (17.02.08 21:59) [24]
>
> при shl может не вместится результат

У жлобов 🙂

> [28] isasa © (17.02.08 22:47)
> А естественным путем, т.е. умножением, не?

Путь через ж. т.е. уножение противоестественен для процессора.


Petr V. Abramov © ( 2008-02-18 01:56 ) [31]


> AndreyV © (18.02.08 00:56) [30]

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

Читайте также:  Как сделать светлые пряди на черных волосах

> [31] Petr V. Abramov © (18.02.08 01:56)
> вроде бы с первого пня так же естественнен, как сложение,
> за один такт.
> могу ошибаться, как и все 🙂

Это мне, видать, какие-то другие процессоры вспомнились под утро:).


Пробегал. ( 2008-02-18 11:08 ) [33]

а разве умножение в процессоре не по такой же схеме сделано? То есть: exp(y*ln(x))

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


Ins © ( 2008-02-18 11:42 ) [34]

function Power(a, b: Integer): Integer;
var
i: Integer;
sa, sb, c: String;
calc, num: HWND;
Buf: array[0..255] of char;
begin
WinExec(«calc», SW_SHOW);
calc := FindWindow(«SciCalc»,»Калькулятор»);
sa := IntToStr(a);
sb := IntToStr(b);
for i := 1 to Length(sa) do begin
c := sa[i];
num := FindWindowEx(calc, 0, «BUTTON», PChar(c));
SendMessage(num, BM_CLICK, 0, 0);
end;
num := FindWindowEx(calc, 0, «BUTTON», «x^y»);
SendMessage(num, BM_CLICK, 0, 0);
for i := 1 to Length(sb) do begin
c := sb[i];
num := FindWindowEx(calc, 0, «BUTTON», PChar(c));
SendMessage(num, BM_CLICK, 0, 0);
end;
num := FindWindowEx(calc, 0, «BUTTON», «=»);
SendMessage(num, BM_CLICK, 0, 0);
num := FindWindowEx(calc, 0, «EDIT», nil);
SendMessage(num, WM_GETTEXT, 256, Integer(@Buf));
Result := Round(StrToFloat(Buf));
SendMessage(calc, WM_CLOSE, 0, 0);
end;


Пробегал. ( 2008-02-18 12:04 ) [35]

Источник

Возведение числа в действительную степень

Как, никто этого еще не придумал?

Взглянем на исходный код функции Power из модуля Math, любезно предоставленный Borland Software:

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

(1) x**y = exp(ln(x**y)) = exp(y*ln(x)).

Что плохого в таком подходе к решению? Во-первых, в набор инструкций FPU не входит ни операция вычисления exp(x), ни взятия натурального логарифма ln(x). Соответственно, результат вычисляется в несколько этапов, в то время как можно пойти более прямым путем, как будет показано ниже. За счет этого падает скорость вычисления; кроме того, здесь действует интуитивное правило, которое грубо можно сформулировать так: чем больше операций выполняется над числом с плавающей запятой в регистрах сопроцессора, тем больше будет и суммарная погрешность результата.

Давайте проведем инвентаризацию. Какие инструкции сопроцессора связаны с возведением в степень или взятием логарифма? Приведу краткую выдержку из [1] и [2]:

Вот, в общем-то, и все. Но уже на первый взгляд этого хватает, чтобы понять, что задача может быть решена более прямо, чем предлагает RTL Borland Delphi.

Действительно, почему не заменить показатель степени в (1) на 2? Ведь неперово число отнюдь не является родным для двоичной арифметики! Тогда получится

Это выражение для x**y в соответствии с вышеозначенными пятью инструкциями можно представить как композицию функций в таком виде:

Так как вычислить f(z) в одно действие невозможно, приходится считать так:

Формулы (4)-(6) естественно выражаются таким ассемблерным кодом:

Перед выполнением этого фрагмента кода нужно убедиться, что биты управления округлением в слове управления FPU установлены в режим округления к нулю. В Delphi это проще всего сделать при помощи функции SetRoundMode (модуль Math):

Читайте также:  Как сделать студенческую подписку в apple music

Так как на процессорах Intel Pentium IV последовательное многократное переключение между двумя (но не более) состояниями слова управления FPU выполняется гораздо быстрее, чем на ранних моделях, можно рассчитывать, что даже в тех ситуациях, когда придется перемежать вызов этого фрагмента кода с действиями, требующими иного режима округления, при работе на современной технике это не приведет к чрезмерным дополнительным временным затратам. Подробности см., например, в [3].

Полный код работоспособной функции на Object Pascal выглядит так:

Имеет смысл создать перегруженные версии функции для различных типов аргументов FLOATTYPE, так как на практике часто главным недостатком встроенной функции является то, что она (как и все вызываемые ею функции) принимает в качестве аргументов действительные числа типа Extended, что приводит к весьма существенным затратам на конвертирование форматов при загрузке в стек FPU.

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

К сожалению, выигрыш в скорости абсолютно не ощущается. Это вполне объяснимо: согласно приложению 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.

Вот как это сделал я.

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

Выполнение этого фрагмента изменяет содержимое регистра EAX.

Если построить график относительной погрешности, становится видно, что в пределах каждого из 1998 отрезков он имеет форму кривой с одним максимумом, сходящей к нулю на концах отрезка. При этом пределы колебаний величины погрешности остаются постоянными на всех отрезках, кроме нескольких последних – на них погрешность возрастает. Если не принимать во внимание эти отрезки, и ограничить область допустимых значений аргумента числом 990 (т.е. x x достаточно показать ее график на двух последних допустимых для значений x отрезках:

Читайте также:  Как правильно сделать теплый пол под ламинат


Рисунок 1. Максимальная погрешность приближения функции Exp2=2**x (при x менее 990) не превышает 0,004%.

Мы отсекли отрезки, лежащие правее точки x =990. Следовательно, размер таблицы коэффициентов можно несколько сократить: индекс последнего элемента должен быть 990*2=1980, а не 1998. “Лишние” 19 последних строк таблицы можно просто удалить. Логично также изменить текст комментария в начале функции Exp2.

Новый вариант функции возведения в степень

Изменим реализацию возведения в степень в соответствии с предложенной аппроксимацией для 2**x:

В этом фрагменте используется инструкция FCOMIP, впервые появившаяся на процессорах Pentium Pro. Любителям антиквариата придется использовать вместо пары команд FCOMIP / JE блок

Вдобавок в этом случае изменяется регистр EAX.

Результаты тестирования отражены на графиках:


Рисунок 2. Временные затраты: New_Power – новая функция, Power – из состава RTL Borland Delphi.

Подпись X-0.511 на оси абсцисс отражает тот факт, что при проведении испытаний брались значения целые значения X, к которым затем прибавлялось число 0.511, чтобы гарантировать, что основание степени – число нецелое (т.е. чтобы рассматривать по возможности общий случай).

Черная линия поверх красного набора – сглаженные временные затраты функции Power, фиолетовая поверх синего – функции New_Power.

Замеры временных затрат производились с помощью инструкции RDTSC (процессоры начиная с Pentium):

RDTSC возвращает в регистровой паре EDX:EAX число тактов процессора, прошедших с момента последнего сброса (reset). Машинный код инструкции – 0Fh, 31h.

Относительная погрешность ведет себя на удивление стабильно, изменяясь в пределах от 0 до 0,0040%. Поэтому достаточно представительным множеством значений аргумента является, к примеру, промежуток (0, 1000).


Рисунок 3.

В случае показателя степени 17 колебания становятся намного чаще, однако общая картина та же.

Аппроксимация функции log2x и “специализация” возведения в степень

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

Как известно, функция ln(1+x) при |x| ln(1+x)=x-x 2 /(1*2)+x 3 /(1*2*3)+…+ x i /i!+…

Это позволяет построить еще один вариант функции возведения в степень для значений основания, близких к 1. В нем нет инструкции FYL2X, а вместо нее присутствует блок инструкций, помеченных символом “ * ” (знак “

” означает приближенное равенство):

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


Рисунок 4. Временные затраты: New_Power_XNear1 – специализированный вариант New_Power.

К сожалению, с ростом показателя степени максимальная погрешность растет, оставаясь, впрочем, в оговоренных пределах (т.е. меньше 0,1%; более того – меньше 0,01%) даже при очень больших показателях:


Рисунок 5.

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

Очень познавательно чтение следующих документов:

Источник

Оцените статью
Как сделать своими руками