Почему нет int pow (int base, int exponent) в стандартных библиотеках C ++?

116

Я чувствую, что просто не могу его найти. Есть ли причина, по которой powфункция C ++ не реализует функцию "power" ни для чего, кроме floats и doubles?

Я знаю, что реализация тривиальна, я просто чувствую, что делаю работу, которая должна быть в стандартной библиотеке. Надежную степенную функцию (т. Е. Обрабатывает переполнение некоторым последовательным, явным образом) неинтересно писать.

Дэн О
источник
4
Это хороший вопрос, и я не думаю, что ответы имеют большой смысл. Отрицательные показатели не работают? В качестве экспонентов используйте целые числа без знака. Большинство входов вызывают его переполнение? То же самое и с опытом и удвоением силы, я не вижу, чтобы кто-то жаловался. Так почему же эта функция не является стандартной?
static_rtti
2
@static_rtti: «То же самое для exp и double pow» полностью неверно. Я уточню в своем ответе.
Стивен Кэнон
11
Стандартная библиотека C ++ существует double pow(int base, int exponent)с C ++ 11 (§26.8 [c.math] / 11 bullet point 2)
Cubbi
Вам нужно выбрать между «реализация тривиальна» и «писать не весело».
Marquis of Lorne

Ответы:

66

По состоянию на некоторые C++11особые случаи были добавлены к набору степенных функций (и других). C++11 [c.math] /11заявляет после перечисления всех float/double/long doubleперегрузок (выделено мной и перефразировано):

Более того, должны быть дополнительные перегрузки, достаточные для гарантии того, что если какой-либо аргумент, соответствующий doubleпараметру, имеет тип doubleили целочисленный тип, то все аргументы, соответствующие doubleпараметрам, будут эффективно преобразованы в double.

Таким образом, в основном целочисленные параметры будут обновлены до удвоения для выполнения операции.


До C++11(когда был задан ваш вопрос) целочисленных перегрузок не существовало.

Так как я не был ни тесно связан с создателями , Cни C++в дни их создания (хотя я являюсь довольно старым), ни часть комитетов ANSI / ISO , которые создали стандарты, это обязательно мнение по моей части. Я хотел бы думать, что это информированное мнение, но, как моя жена скажет вам (часто и без особой поддержки), я ошибался раньше :-)

Предположение, чего оно стоит, следует.

Я подозреваю, что причина, по которой исходный pre-ANSI Cне имел этой функции, заключается в том, что она была совершенно ненужной. Во-первых, уже существовал совершенно хороший способ выполнения целочисленных степеней (с двойным, а затем просто преобразованием обратно в целое число, проверяя целочисленное переполнение и потерю значимости перед преобразованием).

Во-вторых, вы должны помнить еще одну вещь: изначально задумывались Cкак язык системного программирования, и сомнительно, желательна ли вообще плавающая точка в этой области.

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

Кстати, интегральный оператор мощности, вероятно, был бы бинарным оператором, а не вызовом библиотеки. Вы не добавить два целых числа с , x = add (y, z)а с x = y + z- частью языка собственно , а не в библиотеке.

В-третьих, поскольку реализация интегральной мощности относительно тривиальна, почти наверняка разработчики языка лучше потратят свое время на создание более полезных вещей (см. Ниже комментарии о альтернативных издержках).

Это актуально и для оригинала C++. Поскольку исходная реализация фактически была просто переводчиком, производившим Cкод, она переносила многие атрибуты C. Его первоначальной целью было C-with-classes, а не C-with-classes-plus-a-little-of-extra-math-stuff.

Что касается того, почему он никогда раньше не добавлялся к стандартам C++11, вы должны помнить, что органы, устанавливающие стандарты, имеют определенные руководящие принципы, которым нужно следовать. Например, ANSI Cбыла специально поставлена ​​задача систематизировать существующую практику, а не создавать новый язык. Иначе они могли бы сходить с ума и отдать нам Аду :-)

Более поздние версии этого стандарта также имеют конкретные руководящие принципы и могут быть найдены в обосновательных документах (обоснование того, почему комитет принял определенные решения, а не обоснование самого языка).

Например, C99документ с обоснованием конкретно продвигает два C89руководящих принципа, которые ограничивают то, что можно добавить:

  • Держите язык маленьким и простым.
  • Обеспечьте только один способ выполнения операции.

Руководства (не обязательно конкретные ) устанавливаются для отдельных рабочих групп и, следовательно, ограничивают также и C++комитеты (и все другие группы ISO).

Кроме того, органы, устанавливающие стандарты, осознают, что каждое принимаемое ими решение сопряжено с упущенными издержками (экономический термин, означающий то, чего вы должны отказаться для принятия решения). Например, альтернативная стоимость покупки этого сверх-игрового автомата за 10000 долларов - это теплые отношения (или, возможно, все отношения) с вашей второй половиной в течение примерно шести месяцев.

Эрик Ганнерсон хорошо объясняет это, объясняя, почему в продукты Microsoft не всегда что-то добавляют, - 100 баллов - в основном функция начинается со 100 баллов, так что она должна добавить немало ценности, чтобы ее можно было даже рассмотреть.

Другими словами, вы бы предпочли иметь интегральный оператор мощности (который, честно говоря, любой полуприличный кодер мог бы создать за десять минут) или многопоточность, добавленную к стандарту? Что касается меня, я бы предпочел последнее, и мне не приходилось возиться с различными реализациями под UNIX и Windows.

Я также хотел бы увидеть тысячи и тысячи коллекций стандартной библиотеки (хэши, b-деревья, красно-черные деревья, словарь, произвольные карты и т. Д.), Но, как говорится в обосновании:

Стандарт - это договор между разработчиком и программистом.

А количество разработчиков в органах стандартизации намного превышает количество программистов (или, по крайней мере, тех программистов, которые не понимают альтернативных издержек). Если бы все это было добавлено, следующий стандарт C++был бы C++215xи, вероятно, был бы полностью реализован разработчиками компилятора через триста лет после этого.

Во всяком случае, это мои (довольно объемные) мысли по этому поводу. Если бы голоса раздавались только по количеству, а не по качеству, я бы скоро вышиб из воды всех остальных. Спасибо за прослушивание :-)

paxdiablo
источник
2
FWIW, я не думаю, что C ++ следует «Предоставить только один способ выполнения операции» как ограничение. Это правильно, потому что to_stringи например, и лямбды - это удобство для вещей, которые вы уже могли бы сделать. Я полагаю, что можно очень свободно интерпретировать «только один способ выполнения операции» , чтобы разрешить оба из них, и в то же время позволить почти любое дублирование функциональности, которое можно себе представить, сказав «ага! Нет! Потому что удобство делает эта операция несколько отличается от точно такой же, но более длинной альтернативы! ". Что, безусловно, верно в отношении лямбд.
Стив Джессоп,
@ Стив, да, это было плохо с моей стороны. Точнее сказать, что для каждого комитета есть руководящие принципы, а не все комитеты следуют одним и тем же принципам. Скорректированная ответ на clarifyl
paxdiablo
2
Всего один пункт (из немногих): «любая кодовая обезьяна может взлететь за десять минут». Конечно, и если 100 кодовых обезьян (приятный оскорбительный термин, кстати) делают это каждый год (вероятно, низкая оценка), мы теряем 1000 минут. Очень эффективно, не правда ли?
Jürgen A. Erhard
1
@ Jürgen, это не должно было быть оскорблением (поскольку я на самом деле не приписывал ярлык кому-то конкретному), это было просто указанием, которое на powсамом деле не требует особых навыков. Конечно , я предпочел бы иметь стандарт обеспечить то , что будет требовать большого мастерства, и привести к гораздо более впустую минут , если усилие должно было быть продублированы.
paxdiablo
2
@ eharo2, просто замените «наполовину приличный кодировщик» в текущем тексте на «обезьяну кода». Я тоже не думал, что это было оскорбительно, но я подумал, что лучше проявить осторожность, и, честно говоря, нынешняя формулировка перекликается с той же идеей.
paxdiablo
41

В любом случае для любого целочисленного типа фиксированной ширины почти все возможные входные пары переполняют тип. Какая польза от стандартизации функции, которая не дает полезного результата для подавляющего большинства возможных входов?

Вам в значительной степени нужен большой целочисленный тип, чтобы функция была полезной, и большинство больших целочисленных библиотек предоставляют эту функцию.


Изменить: в комментарии к вопросу static_rtti пишет: «Большинство входных данных вызывают его переполнение? То же самое верно для exp и double pow, я не вижу, чтобы кто-то жаловался». Это неверно.

Давайте оставим в стороне exp, потому что это не относится к делу (хотя на самом деле это сделало бы мои доводы более убедительными), и сосредоточимся на этом double pow(double x, double y). Для какой части пар (x, y) эта функция делает что-то полезное (т. Е. Не просто переполнение или потеря значимости)?

На самом деле я собираюсь сосредоточиться только на небольшой части входных пар, для которой powимеет смысл, потому что этого будет достаточно, чтобы доказать мою точку зрения: если x положительно и | y | <= 1, то powне происходит переполнения или потери значимости. Это составляет почти четверть всех пар с плавающей запятой (ровно половина чисел с плавающей запятой, отличных от NaN, являются положительными, и чуть менее половины чисел с плавающей запятой, отличных от NaN, имеют величину меньше 1). Очевидно, есть много других пар входных данных, для которых можно powполучить полезные результаты, но мы убедились, что это не менее четверти всех входных пар .

Теперь давайте посмотрим на целочисленную степенную функцию с фиксированной шириной (т.е. без большого размера). Для какой порции входов просто не переполняется? Чтобы максимально увеличить количество значимых входных пар, основание должно быть подписано, а показатель степени - без знака. Предположим, что основание и экспонента имеют nразрядность. Мы можем легко определить ту часть входных данных, которая имеет смысл:

  • Если показатель степени 0 или 1, то любое основание имеет смысл.
  • Если показатель степени равен 2 или больше, то никакое основание больше 2 ^ (n / 2) не дает значимого результата.

Таким образом, из входных пар 2 ^ (2n) менее 2 ^ (n + 1) + 2 ^ (3n / 2) дают значимые результаты. Если мы посмотрим на наиболее распространенное использование 32-битных целых чисел, это означает, что что-то порядка 1/1000 одного процента входных пар не просто переполняется.

Стивен Кэнон
источник
8
В любом случае это спорный вопрос. Тот факт, что функция недопустима для некоторых или многих входных данных, не делает ее менее полезной.
static_rtti
2
@static_rtti: pow(x,y)не опустошается до нуля для любого x, если | y | <= 1. Существует очень узкая полоса входных данных (большие x, y очень близки к -1), для которых происходит потеря значимости, но результат все еще имеет смысл в этом диапазоне.
Стивен Кэнон
2
Поразмыслив, я согласен на недополнение. Я все же думаю, что это не имеет отношения к вопросу.
static_rtti
7
@ybungalobill: Почему вы выбрали это в качестве причины? Лично я бы предпочел полезность для большого количества задач и программистов, возможность создавать версии, оптимизированные для аппаратного обеспечения, которые быстрее, чем наивные реализации, которые, вероятно, напишут большинство программистов, и так далее. Ваш критерий кажется совершенно произвольным и, откровенно говоря, совершенно бессмысленным.
static_rtti
5
@StephenCanon: С другой стороны, ваш аргумент показывает, что очевидно правильная и оптимальная реализация целого числа pow- это просто крошечная таблица поиска. :-)
R .. GitHub ОСТАНОВИТЬ ПОМОЩЬ ICE
11

Потому что в любом случае невозможно представить все целые степени в int:

>>> print 2**-4
0.0625
Игнасио Васкес-Абрамс
источник
3
Для числового типа конечного размера невозможно представить все степени этого типа внутри этого типа из-за переполнения. Но ваша точка зрения об отрицательных силах более верна.
Крис Лутц,
1
Я рассматриваю отрицательные показатели как нечто, с чем может справиться стандартная реализация, либо принимая беззнаковое int в качестве показателя степени, либо возвращая ноль, когда отрицательный показатель степени представлен как вход, а int - это ожидаемый результат.
Дэн О
3
или разделить int pow(int base, unsigned int exponent)иfloat pow(int base, int exponent)
Ponkadoodle 08
4
Они могли просто объявить это как неопределенное поведение для передачи отрицательного целого числа.
Йоханнес Шауб - лит
2
Во всех современных реализациях все int pow(int base, unsigned char exponent)остальное в любом случае бесполезно. Либо база равна 0, либо 1, и показатель степени не имеет значения, это -1, и в этом случае имеет значение только последний бит показателя степени, или base >1 || base< -1в этом случае - exponent<256штраф за переполнение.
MSalters 08
9

На самом деле это интересный вопрос. Один аргумент, который я не нашел в обсуждении, - это простое отсутствие очевидных возвращаемых значений аргументов. Давайте посчитаем, как гипотетическая int pow_int(int, int)функция может выйти из строя.

  1. перелив
  2. Результат не определен pow_int(0,0)
  3. Результат не может быть представлен pow_int(2,-1)

Функция имеет как минимум 2 режима отказа. Целые числа не могут представлять эти значения, поведение функции в этих случаях должно быть определено стандартом - и программисты должны знать, как именно функция обрабатывает эти случаи.

В целом отказ от функции кажется единственным разумным вариантом. Вместо этого программист может использовать версию с плавающей запятой со всеми доступными сообщениями об ошибках.

phoku
источник
Но разве первые два случая не применимы и к a powbetween float? Возьмите два больших поплавка, поднимите один в степень другого, и у вас будет переполнение. И pow(0.0, 0.0)вызовет ту же проблему, что и ваша вторая точка. Ваш третий пункт - единственное реальное различие между реализацией функции мощности для целых чисел и чисел с плавающей запятой.
numbermaniac
7

Короткий ответ:

Специализация pow(x, n)в nвиде натурального числа часто бывает полезна для измерения времени . Но универсальный стандарт стандартной библиотеки по- pow()прежнему хорошо работает (что удивительно! ) Для этой цели, и абсолютно важно включать как можно меньше в стандартную библиотеку C, чтобы ее можно было сделать максимально переносимой и максимально простой в реализации. С другой стороны, это вовсе не мешает ему находиться в стандартной библиотеке C ++ или STL, которые, я почти уверен, никто не планирует использовать в какой-то встроенной платформе.

А теперь длинный ответ.

pow(x, n)во многих случаях можно сделать намного быстрее, если nиспользовать натуральное число. Мне приходилось использовать мою собственную реализацию этой функции почти для каждой программы, которую я пишу (но я пишу много математических программ на C). Специализированная операция может быть выполнена O(log(n))вовремя, но когда nона небольшая, более простая линейная версия может быть быстрее. Вот реализации обоих:


    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

(Я оставил, xи возвращаемое значение удваивается, потому что результат pow(double x, unsigned n)будет вписываться в удвоение примерно так часто, как pow(double, double)будет.)

(Да, pownэто рекурсивно, но сломать стек абсолютно невозможно, так как максимальный размер стека будет примерно равным log_2(n)и nявляется целым числом. Если nэто 64-битное целое число, это дает максимальный размер стека около 64. Никакое оборудование не имеет таких экстремальных значений. ограничения памяти, за исключением некоторых хитрых PIC с аппаратными стеками, которые обрабатывают от 3 до 8 вызовов функций.)

Что касается производительности, вы будете удивлены тем, на что pow(double, double)способны садовые сорта . Я протестировал сто миллионов итераций на моем 5-летнем IBM Thinkpad с xномером итерации, nравным 10. В этом сценарии pown_lпобедил. glibc pow()занял 12,0 пользовательских секунды, pown7,4 пользовательских секунды и pown_lвсего 6,5 пользовательских секунды. Так что это не слишком удивительно. Этого мы более или менее ожидали.

Затем я позволил xбыть постоянным (я установил его на 2,5) и nсделал цикл от 0 до 19 сто миллионов раз. На этот раз совершенно неожиданно powпобедила glibc , причем безоговорочно! Потребовалось всего 2,0 пользовательских секунды. My pownзанял 9,6 секунды и pown_l12,2 секунды. Что здесь случилось? Я сделал еще один тест, чтобы узнать.

Я сделал то же самое, только с xравным миллиону. На этот раз pownвыиграл с результатом 9,6 с. pown_lзанял 12,2 секунды, а glibc pow - 16,3 секунды. Теперь ясно! glibc powработает лучше трех при xнизком уровне и хуже всего при xвысоком. Когда xвысокий, pown_lлучше всего работает, когда nнизкий, и pownлучше всего работает, когда xвысокий.

Итак, вот три разных алгоритма, каждый из которых может работать лучше других при правильных обстоятельствах. Таким образом, в конечном счете, что использовать , скорее всего , зависит от того, как вы планируете использовать pow, но используя правильную версию это стоит, и иметь все версии хорошо. Фактически, вы даже можете автоматизировать выбор алгоритма с помощью такой функции:

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

Пока x_expectedи n_expectedявляются константами, определяемыми во время компиляции, наряду, возможно, с некоторыми другими предостережениями, оптимизирующий компилятор, стоящий его соли, автоматически удалит весь pown_autoвызов функции и заменит его соответствующим выбором из трех алгоритмов. (Теперь, если вы действительно собираетесь попробовать это использовать , вам, вероятно, придется немного поиграть с этим, потому что я точно не пытался скомпилировать то, что написал выше.;))

С другой стороны, glibc pow действительно работает, и glibc уже достаточно большой. Стандарт C должен быть переносимым, в том числе на различные встроенные устройства (на самом деле встроенные разработчики во всем мире в целом согласны с тем, что glibc уже слишком велик для них), и он не может быть переносимым, если для каждой простой математической функции необходимо включать все альтернативный алгоритм, который может пригодиться. Вот почему этого нет в стандарте C.

сноска: во время тестирования производительности времени я дал своим функциям относительно щедрые флаги оптимизации ( -s -O2), которые, вероятно, будут сопоставимы, если не хуже, чем то, что, вероятно, использовалось для компиляции glibc в моей системе (archlinux), поэтому результаты, вероятно, будут Справедливая. Для более тщательной проверки, я должен был бы составить Glibc себя , и я reeeally не чувствую , как это делать. Раньше я использовал Gentoo, поэтому помню, сколько времени это занимает, даже если задача автоматизирована . Результаты для меня убедительны (или, скорее, неубедительны). Вы, конечно, можете сделать это сами.

Бонусный раунд: специализация pow(x, n)для всех целых чисел важна, если требуется точный целочисленный вывод, что действительно происходит. Рассмотрите возможность выделения памяти для N-мерного массива с элементами p ^ N. Отключение p ^ N даже на единицу приведет к возможной случайной ошибке segfault.

enigmaticPhysicist
источник
Думаю, если вы избавитесь от рекурсии, вы сэкономите время, необходимое для распределения стека. И да, у нас была ситуация, когда pow все замедляло, и мы должны были реализовать свой собственный pow.
Sambatyon
«Ни у кого нет таких крайних ограничений памяти» - ложь. PIC часто имеет ограниченный стек вызовов для максимум от 3 (например, PIC10F200) до 8 (например, 16F722A) вызовов (PIC использует аппаратный стек для вызовов функций).
12431234123412341234123
о, чувак, это жестоко, лол. Хорошо, так что это не будет работать с этими PIC.
enigmaticPhysicist
Для целочисленной базы, а также мощности, как и в вопросе, компиляторы (gcc и clang) легко создадут цикл без ветвей из итеративной (вместо рекурсивной) реализации. Это позволяет избежать ошибочных прогнозов ветвления для каждого бита n. godbolt.org/z/L9Kb98 . gcc и clang не могут оптимизировать ваше рекурсивное определение в простой цикл и фактически выполняют ветвление для каждого бита n. (Поскольку pown_iter(double,unsigned)они по-прежнему ветвятся, но реализация SSE2 или SSE4.1 без ответвлений должна быть возможна в x86 asm или с внутренними функциями C. Но даже это лучше, чем рекурсия)
Питер Кордес
Дерьмо, теперь мне нужно снова провести тесты с версией на основе цикла, чтобы быть уверенным. Я подумаю об этом.
enigmaticPhysicist
6

Одна из причин, по которой C ++ не имеет дополнительных перегрузок, - это совместимость с C.

В C ++ 98 есть такие функции double pow(double, int), но они были удалены в C ++ 11 с аргументом, что C99 их не включает.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

Получение немного более точного результата также означает получение немного другого результата.

Бо Перссон
источник
3

Мир постоянно развивается, как и языки программирования. Четвёртая часть C десятичного TR ¹ добавляет еще несколько функций <math.h>. В ответ на этот вопрос могут быть интересны два семейства этих функций:

  • Эти pownфункции, которая принимает число с плавающей точкой и intmax_tэкспоненту.
  • Эти powrфункции, которая принимает два числа с плавающей точкой ( xа y) и вычислить xк мощности yс формулой exp(y*log(x)).

Кажется, что разработчики стандартной библиотеки в конце концов сочли эти функции достаточно полезными, чтобы их можно было интегрировать в стандартную библиотеку. Однако рациональным является то, что эти функции рекомендованы стандартом ISO / IEC / IEEE 60559: 2011 для двоичных и десятичных чисел с плавающей запятой. Я не могу точно сказать, каким «стандартом» следовали во времена C89, но на будущее развитие <math.h>, вероятно, сильно повлияет будущее развитие стандарта ISO / IEC / IEEE 60559 .

Обратите внимание, что четвертая часть десятичного TR не будет включена в C2x (следующая основная версия C) и, вероятно, будет включена позже как дополнительная функция. Я не собирался включать эту часть TR в будущую ревизию C ++.


¹ Вы можете найти некоторые документы , работу в прогрессе здесь .

Morwenn
источник
Существуют ли какие-либо правдоподобные реализации, в которых использование pownс показателем степени больше, чем LONG_MAXкогда-либо должно давать значение, отличное от using LONG_MAX, или где значение меньше, чем LONG_MINдолжно давать значение, отличное от LONG_MIN? Интересно, какая польза от использования intmax_tэкспоненты?
supercat
@supercat Понятия не имею, извините.
Morwenn
Возможно, стоит упомянуть, что, глядя на Стандарт, кажется, что он также определяет необязательную функцию "crpown", которая, если она определена, была бы версией "pown" с правильными округлениями; В остальном Стандарт не определяет требуемую степень точности. Реализовать быстрый и умеренно точный "pown" легко, но обеспечение правильного округления во всех случаях может быть намного дороже.
supercat
2

Возможно, потому, что ALU процессора не реализовал такую ​​функцию для целых чисел, но есть такая инструкция FPU (как указывает Стивен, на самом деле это пара). Таким образом, на самом деле было быстрее выполнить приведение к удвоению, вызвать pow с числами удвоения, затем протестировать на переполнение и вернуть назад, чем реализовать это с помощью целочисленной арифметики.

(во-первых, логарифмы уменьшают степень умножения, но логарифмы целых чисел теряют большую точность для большинства входных данных)

Стивен прав в том, что на современных процессорах это уже не так, но стандарту C, когда были выбраны математические функции (C ++ просто использовал функции C), теперь что, 20 лет?

Бен Фойгт
источник
5
Я не знаю какой-либо текущей архитектуры с инструкцией FPU для pow. x86 имеет y log2 xинструкцию ( fyl2x), которая может использоваться как первая часть powфункции, но powфункция, написанная таким образом, требует сотен циклов для выполнения на текущем оборудовании; хорошо написанная процедура возведения в степень целочисленного значения в несколько раз быстрее.
Стивен Кэнон
Я не знаю, что «сотни» является точным, кажется, около 150 циклов для fyl2x, затем f2xm1 на большинстве современных процессоров, и это конвейерно с другими инструкциями. Но вы правы, что хорошо настроенная целочисленная реализация должна быть намного быстрее (в наши дни), поскольку IMUL ускорился намного больше, чем инструкции с плавающей запятой. Однако, когда был написан стандарт C, IMUL был довольно дорогим, и его использование в цикле, вероятно, занимало больше времени, чем использование FPU.
Бен Фойгт
2
Изменил свой голос с учетом поправки; тем не менее, имейте в виду (а), что стандарт C претерпел серьезную переработку (включая большое расширение математической библиотеки) в 1999 году, и (б) что стандарт C не записан для какой-либо конкретной процессорной архитектуры - наличие или отсутствие инструкций FPU на x86 по существу не имеет ничего общего с тем, какие функции комитет C выбирает для стандартизации.
Стивен Кэнон
Это не связано с какой-либо архитектурой, правда, но относительная стоимость интерполяции таблицы поиска (обычно используемой для реализации с плавающей запятой) по сравнению с целочисленным умножением изменилась примерно одинаково для всех архитектур, как я полагаю.
Бен Фойгт
1

Вот действительно простая реализация pow () O (log (n) ), которая работает для любых числовых типов, включая целые :

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

Это лучше, чем реализация O (log (n)) enigmaticPhysicist, потому что она не использует рекурсию.

Кроме того, это почти всегда быстрее, чем его линейная реализация (пока p> ~ 3), потому что:

  • не требует дополнительной памяти
  • он выполняет только в ~ 1,5 раза больше операций за цикл
  • он делает только ~ 1,25 раза больше обновлений памяти за цикл
serg06
источник
-2

На самом деле это так.

Начиная с C ++ 11 существует шаблонная реализация pow(int, int)--- и даже более общие случаи, см. (7) в http://en.cppreference.com/w/cpp/numeric/math/pow


РЕДАКТИРОВАТЬ: пуристы могут возразить, что это неверно, поскольку на самом деле используется «продвинутая» типизация. Так или иначе, по параметрам получается правильный intрезультат или ошибка int.

Дима Пасечник
источник
2
это неверно. Перегрузка (7) - это перегрузка, pow ( Arithmetic1 base, Arithmetic2 exp )которая будет преобразована в doubleили, long doubleесли вы прочитали описание: «7) Набор перегрузок или шаблон функции для всех комбинаций аргументов арифметического типа, не охваченных 1-3). Если какой-либо аргумент имеет целочисленный тип, он приводится к типу double. Если какой-либо аргумент имеет значение long double, то тип возвращаемого значения Promoted также является long double, в противном случае тип возвращаемого значения всегда двойной ".
phuclv
что здесь не так? Я просто сказал, что в настоящее время (начиная с C ++ 11) шаблонный pow ( , ) находится в стандартной библиотеке, чего не было в 2010 году.
Дима Пасечник
5
Нет, это не так. Темплаты продвигают эти типы к удвоению или долгому удвоению. Так что он работает с двойниками внизу.
Трисмегист
1
@Trismegistos Он по-прежнему допускает параметры типа int. Если этого шаблона не было, передача параметров int заставляет его интерпретировать биты в int как float, вызывая произвольные неожиданные результаты. То же самое происходит со смешанными входными значениями. eg pow(1.5f, 3)= 1072693280but pow(1.5f, float(3))=3.375
Mark Jeronimus
2
OP просил int pow(int, int), но C ++ 11 только предоставляет double pow(int, int). См. Объяснение @phuclv.
xuhdev
-4

Очень простая причина:

5^-2 = 1/25

Все в библиотеке STL основано на самых точных и надежных материалах, которые только можно представить. Конечно, int вернется к нулю (с 1/25), но это будет неточный ответ.

Согласен, в некоторых случаях это странно.

Джейсон А.
источник
3
Очевидно, что требуется второй аргумент без знака. Есть много приложений, в которых требуются только неотрицательные целые степени.
enigmaticPhysicist