¿Por qué no está 'int pow (int base, int exponent)' en las bibliotecas estándar de C ++?

Siento que debo ser incapaz de encontrarlo. ¿Hay alguna razón por la que la powfunción C ++ no implemente la función "potencia" para nada excepto floatsydouble s?

Sé que la implementación es trivial, solo siento que estoy haciendo un trabajo que debería estar en una biblioteca estándar. Una función de potencia robusta (es decir, maneja el desbordamiento de alguna manera explícita y consistente) no es divertido de escribir.

A partir de C++11, se agregaron casos especiales al conjunto de funciones de poder (y otros). C++11 [c.math] /11afirma, después de enumerar todas las float/double/long doublesobrecargas (mi énfasis, y parafraseado):

Además, habrá sobrecargas adicionales suficientes para asegurar que, si cualquier argumento correspondiente a un doubleparámetro tiene un tipo doubleo un tipo entero, entonces todos los argumentos correspondientes a los doubleparámetros sean efectivamente convertidos double.

Entonces, básicamente, los parámetros enteros se actualizarán a dobles para realizar la operación.

Antes de C++11(que fue cuando se hizo su pregunta), no existían sobrecargas de enteros.

Dado que no estaba estrechamente asociado con los creadores Cni C++en los días de su creación (aunque soy bastante mayor), ni formaba parte de los comités ANSI / ISO que crearon los estándares, esta es necesariamente una opinión de mi parte. Me gustaría pensar que está informado opinión pero, como mi esposa le dirá (con frecuencia y sin mucha motivación), me he equivocado antes :-)

Sigue la suposición, por lo que vale.

Yo sospecho que la razón original de la pre-ANSI Cno tienen esta característica se debe a que era totalmente innecesario. Primero, ya había una manera perfectamente buena de hacer potencias enteras (con dobles y luego simplemente convertir de nuevo a un número entero, verificando el desbordamiento y subdesbordamiento de enteros antes de convertir).

En segundo lugar, otra cosa que debe recordar es que la intención original de Cera como lenguaje de programación de sistemas , y es cuestionable si el punto flotante es deseable en ese ámbito.

Dado que uno de sus casos de uso inicial fue codificar UNIX, el punto flotante habría sido casi inútil. BCPL, en el que se basaba C, tampoco tenía uso de poderes (no tenía punto flotante en absoluto, de memoria).

Aparte, un operador de energía integral probablemente habría sido un operador binario en lugar de una llamada a la biblioteca. No agrega dos enteros con x = add (y, z)pero con x = y + z- parte del lenguaje propiamente dicho lugar de la biblioteca.

En tercer lugar, dado que la implementación del poder integral es relativamente trivial, es casi seguro que los desarrolladores del lenguaje utilizarían mejor su tiempo proporcionando cosas más útiles (vea los comentarios a continuación sobre el costo de oportunidad).

Eso también es relevante para el original C++. Dado que la implementación original era efectivamente solo un traductor que producía Ccódigo, se transfirieron muchos de los atributos de C. Su intención original era C-con-clases, no C-con-clases-más-un-poco-de-cosas-matemáticas-adicionales.

En cuanto a por qué nunca se agregó a los estándares antes C++11, debe recordar que los organismos que establecen los estándares tienen pautas específicas a seguir. Por ejemplo, a ANSI Cse le asignó específicamente la tarea de codificar la práctica existente, no de crear un nuevo idioma. De lo contrario, podrían haberse vuelto locos y habernos dado a Ada :-)

Las versiones posteriores de ese estándar también tienen pautas específicas y se pueden encontrar en los documentos de justificación (la justificación de por qué el comité tomó ciertas decisiones, no la justificación del lenguaje en sí).

Por ejemplo, el C99documento de justificación lleva adelante específicamente dos de los C89principios rectores que limitan lo que se puede agregar:

• Mantenga el lenguaje pequeño y simple.
  
• Proporcione solo una forma de realizar una operación.

Las pautas (no necesariamente las específicas ) se establecen para los grupos de trabajo individuales y, por lo tanto, también limitan los C++comités (y todos los demás grupos ISO).

Además, los organismos que establecen los estándares se dan cuenta de que existe un costo de oportunidad (un término económico que significa lo que tiene que renunciar para tomar una decisión) para cada decisión que toman. Por ejemplo, el costo de oportunidad de comprar esa súper máquina de juego de $ 10,000 son relaciones cordiales (o probablemente todas las relaciones) con su otra mitad durante aproximadamente seis meses.

Eric Gunnerson explica esto bien con su explicación de 100 puntos sobre por qué las cosas no siempre se agregan a los productos de Microsoft, básicamente una característica comienza con 100 puntos en el pozo, por lo que tiene que agregar bastante valor para ser considerada.

En otras palabras, ¿preferiría tener un operador de energía integral (que, honestamente, cualquier codificador medio decente podría activar en diez minutos) o agregar múltiples subprocesos al estándar? Para mí, preferiría tener lo último y no tener que andar con las diferentes implementaciones en UNIX y Windows.

También me gustaría ver miles y miles de colecciones de la biblioteca estándar (hashes, btrees, árboles rojo-negro, diccionario, mapas arbitrarios, etc.) pero, como dice la justificación:

Un estándar es un tratado entre el implementador y el programador.

Y la cantidad de implementadores en los organismos de estándares supera con creces la cantidad de programadores (o al menos los programadores que no entienden el costo de oportunidad). Si se añadieran todas esas cosas, el siguiente estándar C++seríaC++215x y probablemente sería completamente implementado por los desarrolladores de compiladores trescientos años después de eso.

De todos modos, esos son mis pensamientos (bastante voluminosos) al respecto. Si solo los votos se repartieran en base a la cantidad en lugar de la calidad, pronto dejaría a todos los demás fuera del agua. Gracias por su atención :-)

Para cualquier tipo integral de ancho fijo, casi todos los pares de entrada posibles desbordan el tipo, de todos modos. ¿De qué sirve estandarizar una función que no da un resultado útil para la gran mayoría de sus posibles entradas?

Prácticamente necesita tener un tipo de entero grande para que la función sea útil, y la mayoría de las bibliotecas de enteros grandes proporcionan la función.

Editar: En un comentario sobre la pregunta, static_rtti escribe "¿La mayoría de las entradas hacen que se desborde? Lo mismo ocurre con exp y double pow, no veo a nadie quejándose". Esto es incorrecto.

Dejemos de lado exp, porque eso no viene al caso (aunque en realidad haría mi caso más sólido), y centrémonos endouble pow(double x, double y) . ¿Para qué porción de pares (x, y) esta función hace algo útil (es decir, no simplemente se desborda o se desborda)?

De hecho, me voy a centrar solo en una pequeña parte de los pares de entrada, lo que powtiene sentido, porque eso será suficiente para probar mi punto: si x es positivo y | y | <= 1, entonces powno se desborda ni se desborda. Esto comprende casi una cuarta parte de todos los pares de punto flotante (exactamente la mitad de los números de punto flotante que no son de NaN son positivos y poco menos de la mitad de los números de punto flotante que no son de NaN tienen una magnitud menor que 1). Obviamente, hay muchos otros pares de entradas para los que powproducen resultados útiles, pero hemos comprobado que es al menos una cuarta parte de todas las entradas.

Ahora veamos una función de potencia entera de ancho fijo (es decir, no bignum). ¿Para qué porción de entradas no se desborda simplemente? Para maximizar el número de pares de entrada significativos, la base debe estar firmada y el exponente sin signo. Suponga que la base y el exponente tienen ambos nbits de ancho. Podemos obtener fácilmente un límite en la porción de entradas que son significativas:

• Si el exponente es 0 o 1, entonces cualquier base es significativa.
• Si el exponente es 2 o mayor, entonces ninguna base mayor que 2 ^ (n / 2) produce un resultado significativo.

Por lo tanto, de los 2 ^ (2n) pares de entrada, menos de 2 ^ (n + 1) + 2 ^ (3n / 2) producen resultados significativos. Si observamos lo que probablemente sea el uso más común, los enteros de 32 bits, esto significa que algo del orden de 1/1000 del uno por ciento de los pares de entrada no se desborda simplemente.

Porque no hay forma de representar todos los poderes enteros en un int de todos modos:

>>> print 2**-4
0.0625

En realidad, esa es una pregunta interesante. Un argumento que no he encontrado en la discusión es la simple falta de valores de retorno obvios para los argumentos. Vamos a contar las formas en que la int pow_int(int, int)función hipética podría fallar.

1. Desbordamiento
2. Resultado indefinido pow_int(0,0)
3. El resultado no se puede representar pow_int(2,-1)

La función tiene al menos 2 modos de falla. Los enteros no pueden representar estos valores, el comportamiento de la función en estos casos debería estar definido por el estándar, y los programadores deberían ser conscientes de cómo maneja exactamente la función estos casos.

En general, dejar la función fuera parece la única opción sensata. El programador puede usar la versión de punto flotante con todos los informes de errores disponibles en su lugar.

Respuesta corta:

Una especialización de pow(x, n)hasta donde nes un número natural suele ser útil para el desempeño del tiempo . Pero el genérico de la biblioteca estándar pow()todavía funciona bastante ( ¡sorprendentemente! ) Bien para este propósito y es absolutamente crítico incluir lo menos posible en la biblioteca C estándar para que pueda ser tan portátil y fácil de implementar como sea posible. Por otro lado, eso no impide en absoluto que esté en la biblioteca estándar de C ++ o en STL, que estoy bastante seguro de que nadie planea usar en algún tipo de plataforma integrada.

Ahora, para la respuesta larga.

pow(x, n)se puede hacer mucho más rápido en muchos casos especializándose nen un número natural. He tenido que usar mi propia implementación de esta función para casi todos los programas que escribo (pero escribo muchos programas matemáticos en C). La operación especializada se puede realizar a O(log(n))tiempo, pero cuando nes pequeña, una versión lineal más simple puede ser más rápida. Aquí hay implementaciones de ambos:

    // 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;
    }

(Dejé xy el valor devuelto se duplica porque el resultado de pow(double x, unsigned n)encajará en un doble con tanta frecuencia como lo pow(double, double)hará).

(Sí, pownes recursivo, pero romper la pila es absolutamente imposible ya que el tamaño máximo de pila será aproximadamente igual log_2(n)y nes un entero. Si nes un entero de 64 bits, eso le da un tamaño máximo de pila de aproximadamente 64. Ningún hardware tiene un tamaño tan extremo limitaciones de memoria, a excepción de algunos PIC poco fiables con pilas de hardware que solo tienen entre 3 y 8 llamadas a funciones).

En cuanto al rendimiento, se sorprenderá de lo que pow(double, double)es capaz de hacer una variedad de jardín . Probé cien millones de iteraciones en mi IBM Thinkpad de 5 años con xigual al número de iteración e nigual a 10. En este escenario, pown_lganó. glibc pow()tomó 12.0 segundos de usuario, pown7.4 segundos de usuario y pown_lsolo 6.5 segundos de usuario. Entonces eso no es demasiado sorprendente. Más o menos esperábamos esto.

Luego, dejé que xsea ​​constante (lo puse en 2.5), y di un bucle nde 0 a 19 cien millones de veces. Esta vez, de forma bastante inesperada, glibc powganó, ¡y por un deslizamiento de tierra! Solo tomó 2.0 segundos de usuario. Mi powntomó 9,6 segundos y pown_l12,2 segundos. ¿Que pasó aquí? Hice otra prueba para averiguarlo.

Hice lo mismo que el anterior solo con xigual a un millón. Esta vez, pownganó a los 9,6 segundos. pown_ltomó 12.2s y glibc pow tomó 16.3s. ¡Ahora está claro! glibc powfunciona mejor que los tres cuando xes bajo, pero peor cuando xes alto. Cuando xes alto, pown_lfunciona mejor cuando nes bajo y pownfunciona mejor cuando xes alto.

Así que aquí hay tres algoritmos diferentes, cada uno capaz de funcionar mejor que los demás en las circunstancias adecuadas. Por lo tanto, en última instancia, que el uso más probable es que depende de cómo se está planeando sobre el uso pow, pero utilizando la versión correcta es la pena, y que tengan todas las versiones es agradable. De hecho, incluso podría automatizar la elección del algoritmo con una función como esta:

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);
}

Siempre que x_expectedy n_expectedse decidan las constantes en tiempo de compilación, junto con posiblemente otras advertencias, un compilador de optimización que se precie eliminará automáticamente toda la pown_autollamada a la función y la reemplazará con la elección adecuada de los tres algoritmos. (Ahora, si realmente va a intentar usar esto, probablemente tendrá que jugar un poco con él, porque no intenté exactamente compilar lo que había escrito anteriormente.;))

Por otro lado, glibc pow funciona y glibc ya es lo suficientemente grande. Se supone que el estándar C es portátil, incluso para varios dispositivos integrados (de hecho, los desarrolladores integrados en todas partes generalmente están de acuerdo en que glibc ya es demasiado grande para ellos), y no puede ser portátil si para cada función matemática simple necesita incluir todos algoritmo alternativo que podría ser de utilidad. Entonces, es por eso que no está en el estándar C.

nota a pie de página: En la prueba de rendimiento temporal, le di a mis funciones indicadores de optimización relativamente generosos ( -s -O2) que probablemente sean comparables, si no peores, a lo que probablemente se usó para compilar glibc en mi sistema (archlinux), por lo que los resultados probablemente sean justa. Para una prueba más rigurosa, tendría que compilar glibc yo mismo y realmente no tengo ganas de hacer eso. Solía ​​usar Gentoo, así que recuerdo cuánto tiempo lleva, incluso cuando la tarea está automatizada . Los resultados son lo suficientemente concluyentes (o más bien inconclusos) para mí. Por supuesto, puede hacerlo usted mismo.

Ronda de bonificación: una especialización de pow(x, n)a todos los enteros es fundamental si se requiere una salida de entero exacta, lo que sucede. Considere la posibilidad de asignar memoria para una matriz N-dimensional con p ^ N elementos. Obtener p ^ N incluso por uno resultará en una falla segmentaria posiblemente ocurrida al azar.

Una razón para que C ++ no tenga sobrecargas adicionales es que sea compatible con C.

C ++ 98 tiene funciones como double pow(double, int), pero se eliminaron en C ++ 11 con el argumento de que C99 no las incluía.

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

Obtener un resultado un poco más preciso también significa obtener un resultado ligeramente diferente .

El mundo está en constante evolución y también los lenguajes de programación. La cuarta parte del C decimal TR ¹ agrega algunas funciones más a <math.h>. Dos familias de estas funciones pueden ser de interés para esta pregunta:

• Las pownfunciones, que toman un número de coma flotante y un intmax_texponente.
• Las powrfunciones, que toman dos números de coma flotante ( xy y) y calculan xa la potencia ycon la fórmula exp(y*log(x)).

Parece que los chicos estándar eventualmente consideraron estas características lo suficientemente útiles como para integrarse en la biblioteca estándar. Sin embargo, lo racional es que estas funciones están recomendadas por la norma ISO / IEC / IEEE 60559: 2011 para números de coma flotante binaria y decimal. No puedo decir con certeza qué "estándar" se siguió en el momento de C89, pero las evoluciones futuras de <math.h>probablemente estarán muy influenciadas por las evoluciones futuras de ISO / IEC / IEEE 60559 .

Tenga en cuenta que la cuarta parte del TR decimal no se incluirá en C2x (la próxima revisión principal de C), y probablemente se incluirá más adelante como una característica opcional. No ha habido ninguna intención que yo sepa de incluir esta parte del TR en una futura revisión de C ++.

¹ Puede encontrar documentación sobre trabajos en curso aquí .

Quizás porque la ALU del procesador no implementó tal función para los enteros, pero existe una instrucción FPU (como señala Stephen, en realidad es un par). Así que en realidad fue más rápido convertir para duplicar, llamar a pow con dobles, luego probar el desbordamiento y devolver, que implementarlo usando aritmética de enteros.

(por un lado, los logaritmos reducen las potencias a la multiplicación, pero los logaritmos de números enteros pierden mucha precisión para la mayoría de las entradas)

Stephen tiene razón en que en los procesadores modernos esto ya no es cierto, pero el estándar C cuando se seleccionaron las funciones matemáticas (C ++ solo usó las funciones C) tiene ahora, ¿20 años?

Aquí hay una implementación O (log (n)) realmente simple de pow () que funciona para cualquier tipo numérico, incluidos los enteros :

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;
}

Es mejor que la implementación de O (log (n)) de enigmaticPhysicist porque no usa la recursividad.

También es casi siempre más rápido que su implementación lineal (siempre que p> ~ 3) porque:

• no requiere memoria extra
• solo hace ~ 1.5 veces más operaciones por ciclo
• solo hace ~ 1,25 veces más actualizaciones de memoria por ciclo

De hecho, lo hace.

Desde C ++ 11 hay una implementación de plantilla de pow(int, int)--- e incluso casos más generales, consulte (7) en http://en.cppreference.com/w/cpp/numeric/math/pow

EDITAR: los puristas pueden argumentar que esto no es correcto, ya que en realidad se usa una mecanografía "promocionada". De una forma u otra, se obtiene un intresultado correcto o un error en los intparámetros.

Una razón muy simple:

5^-2 = 1/25

Todo en la biblioteca STL se basa en el material más preciso y robusto que se pueda imaginar. Claro, el int volvería a cero (desde 1/25) pero esta sería una respuesta inexacta.

Estoy de acuerdo, es extraño en algunos casos.