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

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

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

По состоянию на некоторые 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и, вероятно, был бы полностью реализован разработчиками компилятора через триста лет после этого.

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

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

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

Изменить: в комментарии к вопросу 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 одного процента входных пар не просто переполняется.

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

>>> print 2**-4
0.0625

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

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

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

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

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

Специализация 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.

Одна из причин, по которой 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

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

Мир постоянно развивается, как и языки программирования. Четвёртая часть 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 ++.

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

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

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

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

Вот действительно простая реализация 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 раза больше обновлений памяти за цикл

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

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

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

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

5^-2 = 1/25

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

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