Задача

← →
still (2002-10-10 15:38) [0]

Дано: X
Требуется: минимальным числом операций получить X^78 (в смысле в степени)

← →
AL2002 (2002-10-10 15:42) [1]

А это смотря какие операции.

← →
qube (2002-10-10 15:42) [2]

Result := Exp(Ln(78)*X) ?

← →
Внук (2002-10-10 15:44) [3]

Первое, что подумалось: exp(78*ln x)

← →
qube (2002-10-10 15:47) [4]

Внук © (10.10.02 15:44)
Тьфу ты, а я все перепутал :).

← →
ZrenBy (2002-10-10 15:48) [5]

Встречная постановка !

X - целое и > 1000000

Получить точный результат ( в смысле - все знаки).

← →
Внук (2002-10-10 15:49) [6]

>>qube © (10.10.02 15:47)
Я сначала так же написал, потом посмотрел, что получилось :))

← →
AL2002 (2002-10-10 15:50) [7]

X^39*X^39?

← →
still (2002-10-10 15:52) [8]

> Внук © (10.10.02 15:44)

а если с помощью арифметики?

← →
Wonder (2002-10-10 15:54) [9]

А если с помощью арифметики - то простейшая рекурсия :)

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

>
> AL2002 © (10.10.02 15:50)
> X^39*X^39?

а X^39 откуда возьмешь?
можно уж тогда сразу так : X^78

← →
qube (2002-10-10 15:56) [11]

Wonder © (10.10.02 15:54)
Зачем рекурсия? Простейшая итерация :)

← →
still (2002-10-10 15:57) [12]

> Wonder © (10.10.02 15:54)

ну и количество операций какое?

← →
AL2002 (2002-10-10 15:58) [13]

>still © (10.10.02 15:55)
но икс же неизвестен. скажи тогда, чему изначально равен икс.

← →
Alx2 (2002-10-10 16:00) [14]

78 = (2^5+2^2+2+1)*2
result := (x shl 5 + x shl 2 + x shl 1 + 1) shl 1

← →
qube (2002-10-10 16:01) [15]

Alx2 © (10.10.02 16:00)
Браво!

← →
Внук (2002-10-10 16:02) [16]

Сначала
X:=X*X 6 раз (это будет 64-ая степень), затем умножить на X^8 - еще четыре умножения (это 72-ая степень), потом еще на X^4 - три умножения и еще на X*X - всего 16 операций, вроде.
X^78= X^64*X^8*x^4*X^2.
А если запоминать промежуточные результаты - и того меньше.

← →
Wonder (2002-10-10 16:03) [17]

Это вот shl - арифметика ?!?
Ну вы, блин, даете! :)

← →
Alx2 (2002-10-10 16:05) [18]

>Alx2 © (10.10.02 16:00)
Не то написал :)

Result := ((x^13)^3)^2=sqr(sqr(sqr(sqr(sqr(x)))*sqr(sqr(x))*x)*sqr(sqr(sqr(x)))*sqr(sqr(x))*x)

Осталось только промежуточные повторные вычисления выкинуть :))

← →
still (2002-10-10 16:05) [19]

> AL2002 © (10.10.02 15:58)

значение X не играет роли

> Alx2 © (10.10.02 16:00)
> 78 = (2^5+2^2+2+1)*2
> result := (x shl 5 + x shl 2 + x shl 1 + 1) shl 1

для целых чисел красиво, а для произвольных?

Задача вообще-то не программистская, а так - из математики

← →
Внук (2002-10-10 16:08) [20]

>>Alx2 © (10.10.02 16:05)
Продублировали друг друга :))

← →
Alx2 (2002-10-10 16:08) [21]

>qube © (10.10.02 16:01)

Мой пост Alx2 © (10.10.02 16:00) прошу считать БРЕДОМ.
Так как там только лишь вычисляется x*78 :)))

← →
Alx2 (2002-10-10 16:11) [22]

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

← →
Jeer (2002-10-10 16:11) [23]

Тогда уж
Y = X^64*X^16/X^2

← →
still (2002-10-10 16:20) [24]

> Alx2 © (10.10.02 16:08)

точно, а я уж повелся:)

← →
Alx2 (2002-10-10 16:24) [25]

>Jeer © (10.10.02 16:11)
Угу. Еще круче :)

← →
Внук (2002-10-10 16:26) [26]

>>Alx2 © (10.10.02 16:24)
Если решать как математическую, то да. Если применительно к компьютерам - неоправданное деление = потеря точности.

← →
Jeer (2002-10-10 16:27) [27]

:))

← →
Jeer (2002-10-10 16:28) [28]

Y = X^64*X^16*X^(-2)

← →
Внук (2002-10-10 16:30) [29]

Зря улыбаетесь, символ ^ и я могу поставить, а реализовывать как будете - все равно через деление?

← →
Alx2 (2002-10-10 16:31) [30]

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

← →
qube (2002-10-10 16:35) [31]

>Задача вообще-то не программистская, а так - из математики
А что в таком случае считать элементарной операцией? По-моему, без привязки к компьютерам и конкретному языку программирования задача в такой формулировке смысла не имеет.

← →
Внук (2002-10-10 16:38) [32]

← →
Alx2 (2002-10-10 16:42) [33]

← →
still (2002-10-10 16:43) [34]

> qube © (10.10.02 16:35)
> > А что в таком случае считать элементарной операцией?

Умножение, деление, сложение, вычитание
А вот sqr - я бы сказал не операция, а функция, пусть и встроенная

← →
Внук (2002-10-10 16:45) [35]

← →
qube (2002-10-10 16:46) [36]

still © (10.10.02 16:43)
Умножение тоже можно с помощью сдвигов и сложений выполнять (другое дело, что это функция процессора, пусть и встроенная :).

← →
Внук (2002-10-10 16:46) [37]

>>still © (10.10.02 16:43)
Не важно, можно заменить умножением и введением промежуточных переменных. Ведь про объем памяти не было речи? :)

← →
still (2002-10-10 16:51) [38]

> Внук © (10.10.02 16:46)
> >>still © (10.10.02 16:43)
> Не важно, можно заменить умножением и введением промежуточных
> переменных. Ведь про объем памяти не было речи? :)

про объем памяти действительно речи не было, как в общем-то и про какой-то язык программирования, особенности процессоров и пр.

Чистая арифметика :)

← →
Alx2 (2002-10-10 16:56) [39]

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

← →
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 (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 без.

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