Форум: "Потрепаться";
Текущий архив: 2002.10.31;
Скачать: [xml.tar.bz2];
Вниз
Задача Найти похожие ветки
← →
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 © (10.10.02 16:31)
У меня получается только 74-ая степень? Глюки? :)
← →
Alx2 (2002-10-10 16:42) [33]>Внук © (10.10.02 16:38)
Нет, именно 78-я. Только что проверил
← →
still (2002-10-10 16:43) [34]
> qube © (10.10.02 16:35)
> > А что в таком случае считать элементарной операцией?
Умножение, деление, сложение, вычитание
А вот sqr - я бы сказал не операция, а функция, пусть и встроенная
← →
Внук (2002-10-10 16:45) [35]>>Alx2 © (10.10.02 16:42)
Точно, это глюки.
Посмею подтвердить, что это действительно оптимум :)
← →
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 © (10.10.02 16:51)
Ну как, это (Alx2 © (10.10.02 16:31)) тоже не подходит?
← →
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 без.
Страницы: 1 2 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.10.31;
Скачать: [xml.tar.bz2];
Память: 0.54 MB
Время: 0.009 c
