Форум: "Потрепаться";
Текущий архив: 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)
вот это ближе к истине
Страницы: 1 2 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.10.31;
Скачать: [xml.tar.bz2];
Память: 0.52 MB
Время: 0.01 c
