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

StackOverflow https://stackoverflow.com/questions/2398442

Вопрос

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

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

Это было полезно?

Решение

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

Поскольку C ++ 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, которые создали стандарты, это обязательно мнение по моей части. Я хотел бы думать, что это проинформирован Мнение, но, как моя жена скажет вам (часто и без особого поощрения), я был неправ раньше :-)

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

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

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

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

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

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

Это также актуально для оригинала C++. Отказ Поскольку первоначальная реализация была эффективно просто переводчиком, который производится C код, он переносился над многими атрибутами C. Отказ Его первоначальное намерение было C-с-классами, а не C-с-с-с-с-с-с-с-с-классами - плюс-а-малоусчитыми.

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

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

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

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

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

Кроме того, органы по стандартам понимают, что есть альтернативные стоимость (Экономический термин, что означает, что вы должны отказаться от принятия решения) для каждого решения, которое они делают. Например, возможность покупки, что 100 000 долларов Uber-Gaming Machine - это сердечные отношения (или, вероятно, все Отношения) с другой половиной около шести месяцев.

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

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

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

Стандарт - это договор между исполнителем и программистом.

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

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

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

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

Редактировать: В комментарии к вопросу static_rtti пишет "большинство входов заставляют его переполнить? То же самое верно для exp и двойной пауси, я не вижу, кто жалуется". Это неверно.

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

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

Теперь давайте посмотрим на фиксированную ширину (т.е. не-Bignum) целочисленную функцию питания. Для каких порций входы это не просто переполнение? Чтобы максимизировать количество осмысленных входных пар, база должна быть подписана и подвергается отказа от неподписан. Предположим, что основание и экспонент являются оба 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. Нет Аппаратное обеспечение имеет такие экстремальные ограничения памяти, за исключением некоторых хитрых фото с аппаратными стеками, которые вызовы только от 3 до 8 функций.)

Что касается производительности, вы будете удивлены тем, что сад сорт pow(double, double) способен на. Я проверил сто миллионов итераций на моем 5-летнем IBM ThinkPad с x равный числу итерации и n равный 10. В этом сценарии, pown_l победил. глибц 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,6. pown_l Взял 12,2, а Glibc Pow занял 16,3. Теперь ясно! глибц 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.

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

Мир постоянно развивается и поэтому языки программирования. То Четвертая часть Десятичного 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 стандартный

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

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

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

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

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

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

5^-2 = 1/25

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top