Задача

← →
still (2002-10-10 17:02) [40]

> Внук © (10.10.02 16:02)

вот это ближе к истине

← →
han_malign (2002-10-10 17:07) [41]

exp и ln - это ряды - так что насчет количества элементарных операций еще посчитать нужно
x2:=x*x;
x4:=x2*x2;
x8:=x4*x4;
x16:=x8*x8;
x32:=x16*x16;
x39:=x32*x4*x2*x;
x78:=x39*x39;//итого 9*
------------------------
x2:=x*x;
x4:=x2*x2;
x9:=x4*x4*x;
x19:=x9*x9*x;
x39:=x19*x19*x;
x78:=x39*x39;//итого 9*

я тут расписал попроще, но от лишних 2 умножений(всетаки 78>2^6), как не крути, никуда не деться(деление по идее более длительная операция), но во втором случае нужна всего одна промежуточная переменная (в общем случае это действительно решается рекурсией с проверкой на четность степени)

← →
still (2002-10-10 17:15) [42]

> han_malign © (10.10.02 17:07)

идея правильная. можно меньше :)

← →
han_malign (2002-10-10 17:34) [43]

на 8 умножений я решение нашел, интересно есть ли на 7(по идее дальше некуда)

← →
Jeer (2002-10-10 17:38) [44]

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

Если заменить sqrt в схеме Alx2 на умножения, то и будет оптимум, наверное.

>Alx2 © (10.10.02 16:31)
>А вот оптимум, посмею заявить :))
>Result := sqr(sqr(sqr(sqr(sqr(sqr(x)))*x)*x)*x);

Однако и вот это имеет право на жизнь, только как уже программисткая задача.
>Jeer © (10.10.02 16:28)
>Y = X^64*X^16*X^(-2)

Для целых это идеальный вариант, а для real надо учесть, что
порядок храниться отдельным блоком и степень двойки это просто сдвиг порядка вправо при + и влево при -.
По скорости - самый эффективный метод.

← →
han_malign (2002-10-10 17:56) [45]

а я и не претендовал на оригинальность, но сам привык писать читабельные программы и расковыривать 6 скобок мне влом, просто расписал итерации, а вот насчет оптимума то это (с двумя промежуточными):
x2=x*x;
x4=x2*x2;
x8=x4*x4;
x12=x8*x4;
x16=x8*x8;
x32=x16*x16;
x64=x32*x32;
x78=x64*x12;//8* (схема Горнера в чистом виде здесь не пройдет, да и алгоритмизировать по сложнее и для общего случая не решается)
через умножение меньше не получится (хотя доказать не могу), а деление для целых не лучший вариант потому как длительнее умножения(во всяком случае раньше было),а скажем на большинстве DSP операции деления просто нет. Но для Математики, конечно, 7 опреаций с делением лучше чем 8 без.

Задача Найти похожие ветки