Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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
14-101475
Лохматый
2002-10-10 11:02
2002.10.31
А нужна ли перепись?


7-101533
Flying Bird
2002-08-26 00:40
2002.10.31
Как получить (изменить) атрибуты файла?


1-101236
Прохожий
2002-10-21 21:53
2002.10.31
Lib-файлы


1-101342
Luke
2002-10-20 23:42
2002.10.31
Деинсталяторы


14-101528
Oleg_Gashev
2002-10-14 01:22
2002.10.31
Ошибка в конфигурации РНР?





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский