Я чувствую, что просто не могу его найти. Есть ли какая-либо причина, по которой функция C++ pow не реализует функцию "питания" ни для чего, кроме float и double s?
Я знаю, что реализация тривиальна, я просто чувствую, что делаю работу, которая должна быть в стандартной библиотеке. Надежная мощная функция (т.е. обрабатывает переполнение каким-то непротиворечивым, явным образом) писать не весело.
На самом деле, это так.
Начиная с С++ 11 существует шаблонная реализация pow(int, int) --- и даже в более общих случаях, см. (7) в
http://en.cppreference.com/w/cpp/numeric/math/pow
ОБНОВЛЕНИЕ: пуристы могут утверждать, что это не правильно, поскольку на самом деле используется "продвижение" типирования. Так или иначе, каждый получает правильный результат int или ошибку в параметрах int.
Начиная с 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++11, вы должны помнить, что у органов, устанавливающих стандарты, есть конкретные рекомендации, которым нужно следовать. Например, ANSI C было специально поручено кодифицировать существующую практику, а не создавать новый язык. Иначе они могли бы сойти с ума и дать нам Аду :-)
Более поздние итерации этого стандарта также имеют конкретные руководящие указания и могут быть найдены в документах обоснования (обоснование того, почему комитет принял определенные решения, а не обоснование самого языка).
Например, документ с обоснованием C99, в частности, содержит два руководящих принципа C89, которые ограничивают то, что можно добавить:
Руководящие принципы (не обязательно те, которые являются конкретными) изложены для отдельных рабочих групп и, следовательно, ограничивают комитеты C++ (и все другие группы ISO).
Кроме того, органы, устанавливающие стандарты, понимают, что для каждого принятого ими решения существует альтернативная стоимость (экономический термин, означающий то, что вы должны упустить для принятия решения). Например, альтернативная стоимость покупки этого игрового автомата за 10 000 долларов - это теплые отношения (или, вероятно, все отношения) с вашей второй половиной в течение примерно шести месяцев.
Эрик Ганнерсон хорошо объясняет это своим -100 объяснением точек относительно того, почему вещи не всегда добавляются в Microsoft products-, в основном функция запускает 100 точек в лунке, поэтому она должна добавить немало значение, которое даже нужно учитывать.
Другими словами, вы бы предпочли иметь встроенного оператора мощности (который, честно говоря, любой полу-приличный кодер мог бы заработать за десять минут) или многопоточность, добавленную к стандарту? Что касается меня, я бы предпочел иметь последнее и не разбираться с различными реализациями в UNIX и Windows.
Я хотел бы также видеть тысячи и тысячи коллекций стандартной библиотеки (хэши, деревья, красно-черные деревья, словарь, произвольные карты и т.д.), Но, как говорится в обосновании:
Стандарт - это соглашение между исполнителем и программистом.
И количество разработчиков в органах стандартизации намного превышает количество программистов (или, по крайней мере, тех программистов, которые не понимают альтернативных издержек). Если бы все это было добавлено, следующим стандартом C++ был бы C++215x, и он, вероятно, был бы полностью реализован разработчиками компилятора через триста лет после этого.
Во всяком случае, это мои (довольно объемные) мысли по этому поводу. Если бы раздавались только голоса по количеству, а не по качеству, я бы скоро выкинул всех остальных из воды. Спасибо за прослушивание :-)
Для любого интегрального типа с фиксированной шириной почти все возможные входные пары переполняют тип. Какое использование стандартизации функции, которая не дает полезного результата для подавляющего большинства его возможных входов?
Вам очень нужно иметь большой целочисленный тип, чтобы сделать функцию полезной, и большинство больших целочисленных библиотек предоставляют эту функцию.
Изменить: В комментарии к вопросу, static_rtti пишет: "Большинство входов вызывают переполнение? То же самое верно для exp и double pow, я не вижу, чтобы кто-то жаловался". Это неверно.
Оставьте в стороне exp, потому что это рядом с точкой (хотя это действительно сделает мой случай сильнее) и сосредоточьтесь на double pow(double x, double y). Для какой части (x, y) пар эта функция делает что-то полезное (т.е. Не просто переполнение или недополнение)?
Я собираюсь сосредоточиться только на небольшой части входных пар, для которых pow имеет смысл, потому что этого будет достаточно, чтобы доказать мою точку: если x положительно и | y | <= 1, то pow не переполняется и не заканчивается. Это составляет почти четверть всех пар с плавающей запятой (ровно половина чисел с плавающей запятой, отличных от NaN, являются положительными, а чуть меньше половины чисел с плавающей запятой, отличных от NaN, имеют величину меньше 1). Очевидно, что существует много других входных пар, для которых pow дает полезные результаты, но мы убедились, что это не менее четверти всех входов.
Теперь рассмотрим функцию целочисленной мощности с фиксированной шириной (т.е. не-бигнем). Для каких порций это не просто переполнение? Чтобы максимизировать количество значимых входных пар, база должна быть подписана, а экспонента - без знака. Предположим, что база и экспонента имеют ширину n. Мы можем легко получить привязку к той части входных данных, которая имеет смысл:
Таким образом, из входных пар 2 ^ (2n) меньше 2 ^ (n + 1) + 2 ^ (3n/2) дают значимые результаты. Если мы посмотрим на то, что, пожалуй, наиболее распространенное использование, 32-битные целые числа, это означает, что что-то порядка 1/1000-го процента входных пар не просто переполняется.
Потому что нет способа представлять все целые степени в int any:
>>> print 2**-4
0.0625
Это действительно интересный вопрос. Один аргумент, который я не нашел в обсуждении, - это простой недостаток очевидных возвращаемых значений для аргументов. Позвольте подсчитать, как может функционировать функция gpthetical int pow_int(int, int).
pow_int(0,0)pow_int(2,-1)Функция имеет как минимум 2 режима отказа. Целые числа не могут представлять эти значения, поведение функции в этих случаях должно определяться стандартом - и программисты должны знать, как именно функция обрабатывает эти случаи.
В целом выход из функции кажется единственным разумным вариантом. Программист может использовать версию с плавающей точкой со всеми доступными сообщениями об ошибках.
Короткий ответ:
Специализация pow(x, n) где n является натуральным числом, часто полезна для производительности времени. Но стандартная библиотека generic pow() по-прежнему хорошо работает (удивительно!) Для этой цели, и абсолютно необходимо включать как можно меньше в стандартную библиотеку 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) будет вписываться в double примерно так же часто, как pow(double, double).)
(Да, pown является рекурсивным, но разбиение стека абсолютно невозможно, поскольку максимальный размер стека будет примерно равным log_2(n) и n является целым числом. Если n - это 64-разрядное целое число, это дает максимальный размер стека около 64. Никакие аппаратные средства не имеют таких экстремальных ограничений памяти, за исключением некоторых изворотливых ПОС с аппаратными стеками, которые имеют только от 3 до 8 вызовов функций.)
Что касается производительности, вы будете удивлены тем, чем способна садовая разновидность pow(double, double). Я протестировал сто миллионов итераций на своем пятилетнем IBM Thinkpad с x, равным номеру итерации, и n, равному 10. В этом случае выиграл pown_l. glibc pow() заняло 12,0 секунд пользователя, pown заняло 7,4 пользовательских секунды, а pown_l заняло всего 6,5 пользовательских секунд. Так что не слишком удивительно. Мы более или менее ожидали этого.
Тогда, пусть x будет постоянным (я установил его в 2.5), и я зацикливал n от 0 до 19 сто миллионов раз. На этот раз, совершенно неожиданно, glibc pow победил, и оползнем! Это заняло всего 2,0 пользовательских секунды. Мой pown занял 9,6 секунды, а pown_l заняло 12,2 секунды. Что здесь случилось? Я сделал еще один тест, чтобы узнать.
Я сделал то же, что и выше, только с x равным миллиону. На этот раз pown выиграл в 9.6s. 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.
footnote: во время тестирования производительности я дал свои функции относительно щедрым оптимизационным флагам (-s -O2), которые, вероятно, будут сопоставимы, если не хуже, что, вероятно, использовалось для компиляции glibc в моей системе (archlinux), поэтому результаты, вероятно, справедливы. Для более тщательного теста мне пришлось бы скомпилировать glibc, и я не хочу, чтобы это делалось так. Я использовал Gentoo, поэтому я помню, сколько времени требуется, даже когда задача автоматизирована. Результаты для меня являются неопровержимыми (или, скорее, неубедительными). Вы, конечно же, можете сделать это сами.
Бонусный раунд: специализация pow(x, n) для всех целых чисел является инструментальной, если требуется точный целочисленный вывод, что и происходит. Рассмотрим распределение памяти для N-мерного массива с элементами p ^ N. Получение p ^ N даже одним приведет к случайному появлению segfault.
Одна из причин того, что С++ не имеет дополнительных перегрузок, должна быть совместима с C.
С++ 98 имеет такие функции, как double pow(double, int), но они были удалены в С++ 11 с аргументом, что C99 не включил их.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550
Получение немного более точного результата также означает получение немного другого результата.
Мир постоянно развивается, а также языки программирования. четвертая часть C decimal 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 в будущую версию С++.
¹ Вы можете найти документацию о незавершенном производстве здесь.
Возможно, потому, что процессор ALU не реализовал такую функцию для целых чисел, но есть такая инструкция FPU (как указывает Стивен, на самом деле это пара). Таким образом, на самом деле было быстрее выполнить двойное нажатие, вызвать pow с удвоениями, а затем проверить переполнение и отбрасывание, чем реализовать его с использованием целочисленной арифметики.
(во-первых, логарифмы уменьшают степень до умножения, но логарифмы целых чисел теряют большую точность для большинства входов)
Стивен прав, что на современных процессорах это уже не так, но стандарт C, когда были выбраны математические функции (С++ только использовал функции C), теперь то, что 20 лет?
Очень простая причина:
5^-2 = 1/25
Все в библиотеке STL основано на наиболее точном, надежном материале, который только можно себе представить. Конечно, int вернется к нулю (с 1/25), но это будет неточным ответом.
Я согласен, в некоторых случаях это странно.