VPF::Составьте программу вычисления степени числа А с н

Dem_max

Дата 10.12.2012, 17:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1780
Регистрация: 12.4.2007

Репутация: 4
Всего: 39

ТС это приказ ???

--------------------

Американские программисты долго не могли понять, почему русские при зависании Windоws всё время повторяют "Твой зайка написал" ("Yоur bunnу wrоte")

Zhunko

Дата 10.12.2012, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 75
Регистрация: 4.11.2009

Репутация: нет
Всего: нет

Цитата(bsa @ 10.12.2012, 18:02

)

Понимаешь, до сего момента для меня было очевидно, что люди говорящие подобные вещи знают математику (хотя бы на уровне 6-го класса средней школы).Сдвиг (самая сложная битовая операция) позволяет умножать/делить число на 2 в целой степени. Т.е. сдвигами можно решить задачу, если A = 2. Остальные битовые операции тут вообще вряд ли помогут.Перевод в число с плавающей точкой тоже не вариант, так как оно выглядит как мантисса * 2 ^ экспонента. Т.е. опять, с ее помощью можно решить задачу только для A=2 (при этом будет много головной боли при смене архитектуры и/или разрядности).Сдвигами и сложением можно реализовать умножение. А возведение в целую неотрицательную степень можно реализовать с помощью умножения. Раскрываем скобки и получаем, что возведение в степень можно реализовать через битовые операции и суммирование. НО! Это будет крайне неоптимально. Так как современный процессор делает сдвиг и умножение за одинаковое время, но для реализации 32-х битного умножения нужно сделать 31 сдвиг и столько же сложений.Можно зайти с другой стороны, и с помощью сдвигов оптимизировать операцию деления на 2, которая используется в индийском варианте решения. Вот только если посмотреть ассемблерный листинг вариантов с делением и со сдвигами, то с большой вероятностью они полностью совпадут, так как компилятор не дурак и знает, что x >> 1 и x / 2 дают одинаковый результат (для целых неотрицательных x).

Вот спасибо! Теперь мне не надо доказывать, что это возможно! smile

Про оптимальность в задании ничего не было.
Математику совсем не знаю. Тем более не в курсе, что сейчас в 6-ом классе изучают. Может то, что раньше в детском саду? Палочки считают? smile

Как Вы думаете, процессор что-нибудь умеет, кроме побитовых операций?

Это сообщение отредактировал(а) Zhunko - 10.12.2012, 17:31

volatile

Дата 10.12.2012, 17:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(feodorv @ 10.12.2012, 09:35

)

double Pow( double A, unsigned int n)
{
return (n == 0) ? 1 : A*Pow( A, n-1);
}

Да, угадал, светлая башка, практически один в один

Вот вчерашний мой вариант:

Код


double pw (double a, unsigned n)
{
   return n ? a * pw (a, n - 1) : 1;
}

http://codepad.org/7rA8WEHS (там время поста должно стоять)

Спасибо всем кто принял участие.
Интересные решения у
math64,
feodorv,
baldina,

Плюсики сим товарищам щас поставлю, если получится.
(я не из дома, так что если щас не получится, то расставлю сразу как доберусь до своего компа.)

bsa

Дата 10.12.2012, 17:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

Zhunko, молодец. давай еще на электронный уровень перейдем: вычисление степени числа путем перевода электронов из одного места в другое.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

baldina

Дата 10.12.2012, 18:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

Цитата(volatile @ 10.12.2012, 17:53

)

Интересные решения

с лямбдой выпендреж, жаль никто не отметил. можно проще (и понятней)

Код


return n ? (n%2 ? a : 1)*pow(a*a,n/2) : 1;

Это сообщение отредактировал(а) baldina - 10.12.2012, 18:05

Zhunko

Дата 10.12.2012, 18:27 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 75
Регистрация: 4.11.2009

Репутация: нет
Всего: нет

Цитата(baldina @ 10.12.2012, 19:04

)

с лямбдой выпендреж, жаль никто не отметил. можно проще (и понятней)

Отметил! Мне понравилось. Хоть, до сих пор не понял, как это работает. smile

Цитата(bsa @ 10.12.2012, 18:53

)

Zhunko, молодец. давай еще на электронный уровень перейдем: вычисление степени числа путем перевода электронов из одного места в другое.

Так оно скоро будет. Типа квантовых компьютеров. Там производительность на 300 порядков выше.

Это сообщение отредактировал(а) Zhunko - 10.12.2012, 18:38

volatile

Дата 11.12.2012, 00:22 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(Zhunko @ 10.12.2012, 18:27

)

Там производительность на 300 порядков выше.

pow (10, 300) ? а хоть и pow (2, 300) это слишком дофига.
Если в ближайшее время изобретут такой комп, первое что будет это глабальный катаклизм.
потому-что банковская система рухнет
потому-как все ключи будут взломаны за минуты.
ну и т.д.

math64

Дата 11.12.2012, 07:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

Можно ещё сделать на шаблонах:

Код


template<unsigned m>
inline double pow(double x, unsigned n) {
  return n == 0 ? 1 : pow<m/2>(x * x, n/2) * pow<0>(x,n);
}

template<>
inline double pow<0>(double x, unsigned n) {
  return n % 2 == 0 ? 1 : x;
}

double pow(double x, int n)
{
return n < 0 ? 1 / pow<unsigned(-1)/2>(x,(unsigned)-n) : pow<unsigned(-1)/2>(x,(unsigned)n);
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »