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

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

Pregunta

Siento que no debo poder encontrarlo.¿Hay alguna razón por la que C++ pow La función no implementa la función "potencia" para nada excepto floatarena double¿s?

Sé que la implementación es trivial, simplemente 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 consistente y explícita) no es divertido de escribir.

¿Fue útil?

Solución

Como cuestión de hecho, lo hace.

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

EDIT: puristas pueden argumentar que esto no es correcto, ya que es en realidad "promovió" la tipificación usa. De una forma u otra, se obtiene un resultado int correcta, o un error, en parámetros int.

Otros consejos

A partir de C++11, se añadieron casos especiales para el conjunto de funciones de potencia (y otros). C++11 [c.math] /11 estados, después de enumerar todas las sobrecargas float/double/long double (el subrayado es mío, y parafraseado):

  

Además, no habrá sobrecargas adicionales suficientes para asegurar que, si cualquier argumento correspondiente a un parámetro double tiene tipo double o un tipo entero, entonces todos los argumentos correspondientes a parámetros double se echan eficazmente a double.

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

Antes de C++11 (que fue cuando se le pidió a su pregunta), no existía sobrecargas enteros.

Como estaba ni estrechamente asociado con los creadores de C ni C++ en los días de su creación (aunque I am en lugar de edad), ni parte de los comités ANSI / ISO que crearon las normas, esto es necesariamente la opinión de mi parte. Me gustaría pensar que es informado opinión, pero, como mi esposa le dirá (con frecuencia y sin mucho ánimo necesario), me he equivocado antes: -)

La suposición, por lo que vale la pena, a continuación.

sospechoso que la razón por la C original de pre-ANSI no tienen esta característica se debe a que era totalmente innecesario. En primer lugar, ya había una perfectamente buena manera de hacer las potencias enteras (con dobles y luego simplemente convertir de nuevo a un entero, la comprobación de desbordamiento de enteros o por defecto antes de la conversión).

En segundo lugar, otra cosa que hay que recordar es que la intención original de C era como un sistemas lenguaje de programación, y es cuestionable si en coma flotante es deseable en esa arena en absoluto.

Dado que uno de sus casos de uso iniciales fue al código de los servidores UNIX, el punto flotante habría sido prácticamente inútil. BCPL, en la que se basa C, también tenía ningún uso para potencias (que no tenía punto flotante en absoluto, de la memoria).

  

Como acotación al margen, un operador potencia integral probablemente habría sido un operador binario en lugar de una llamada a la librería. No agrega dos números enteros con x = add (y, z) pero con x = y + z -. Parte de la lenguaje adecuado en lugar de la biblioteca

En tercer lugar, ya que la aplicación de la energía integral es relativamente trivial, es casi seguro que los desarrolladores del lenguaje tendrían un mejor uso de su tiempo proporcionando material más útil (ver más abajo los comentarios sobre el costo de oportunidad).

Eso también es relevante para la C++ originales. Desde la implementación original era efectivamente sólo un traductor que produjo código C, se llevó sobre muchos de los atributos de C. Su intención original era C-with-clases, no en C-con-clases-más-un-poco-poco-de-extra-matemáticas-cosas.

En cuanto a por qué nunca se añadió a las normas antes C++11, hay que recordar que los organismos de normalización tienen pautas específicas a seguir. Por ejemplo, ANSI C fue específicamente la tarea de codificar la práctica existente, no para crear un nuevo lenguaje. De lo contrario, podría haber ido loco y dado que nos Ada: -)

iteraciones posteriores de esa norma también tienen directrices específicas y se pueden encontrar en los documentos de justificación (razón de por qué el comité hizo ciertas decisiones, no justificación de la propia lengua).

Por ejemplo el documento C99 razón lleva adelante específicamente dos de los C89 principios que limitan lo que se puede guiar añadió:

  • Mantenga la lengua pequeña y sencilla.
  • Proporcionar una sola manera de hacer una operación.

Directrices (no necesariamente los específica los) están fijados para el individuogrupos de trabajo y por lo tanto limitar los comités C++ (y todos los otros grupos ISO) también.

Además, los organismos de normalización se dan cuenta de que hay un costo de oportunidad (un término económico que significa lo que tiene que renunciar a una decisión tomada) a cada decisión que tomen. Por ejemplo, el costo de oportunidad de compra que $ 10.000 máquina súper juego es cordiales relaciones (o probablemente todos las relaciones) con su otra mitad durante unos seis meses.

Eric Gunnerson explica muy bien con sus -100 puntos explicación de por qué las cosas no siempre se agregan a Microsoft PRODUCTOS- básicamente una función comienza 100 puntos en el agujero de modo que tiene que añadir un poco de valor que se considera incluso.

En otras palabras, le gustaría tener un operador de potencia integral (que, de verdad, que cualquier programador medio decente podría preparar rápidamente en cuestión de minutos diez) o multi-threading añadido a la norma? En cuanto a mí, yo prefiero tener la última y no tener que perder el tiempo con las implementaciones diferentes en Unix y Windows.

Me gustaría también ver miles y miles de colección de la biblioteca estándar (hashes, btree, árboles rojo-negro, diccionario, mapas arbitrarios, etc.) también, pero, como dice el Justificación:

  

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

Y el número de los ejecutores de los organismos de normalización superan con creces el número de programadores (o al menos aquellos programadores que no entienden coste de oportunidad). Si se ha añadido todo eso, la próxima C++ estándar sería C++215x y probablemente ser aplicado plenamente por los desarrolladores de compiladores trescientos años después de eso.

De todos modos, de que es mi lugar (voluminosos) pensamientos sobre la materia. Si únicos votos se repartieron bases en la cantidad de calidad, me pronto golpe a todos los demás fuera del agua. Gracias por su atención: -)

Para cualquier tipo de ancho fijo integral, casi todos los posibles pares de entrada de desbordamiento del tipo, de todos modos. ¿Cuál es el uso de la normalización de una función que no reconocen un resultado útil para la gran mayoría de sus posibles entradas?

Más o menos necesidad de tener un gran tipo entero con el fin de hacer que la función de utilidad, y la mayoría de las bibliotecas grandes enteros proporcionan la función.

Editar En un comentario sobre la cuestión, static_rtti escribe "?. La mayoría de las entradas de hacer que se desborde Lo mismo es cierto para exp y el doble prisionero de guerra, no veo a nadie quejándose" Esto es incorrecto.

Vamos a un lado licencia exp, porque ese no es el punto (a pesar de que en realidad lo haría más fuerte mi caso), y se centran en double pow(double x, double y). Para qué porción de (x, y) pares no esta función hacer algo útil (es decir, no simplemente desbordamiento o subdesbordamiento)?

de hecho voy a centrarse sólo en una pequeña parte de los pares de entrada para las que pow tiene sentido, ya que será suficiente para demostrar mi punto: si x es positiva y | y | <= 1, entonces pow no rebose, o subdesbordamiento. Esto abarca casi una cuarta parte de todos los pares de punto flotante (exactamente la mitad de la no-nan números de punto flotante son positivos, y un poco menos de la mitad de los números de punto flotante no tienen NaN magnitud menor que 1). Obviamente, hay mucho de los otros pares de entrada para las que pow produce resultados útiles, pero nos hemos asegurado de que hay al menos una cuarta parte de todas las entradas.

Ahora vamos a ver un ancho fijo (es decir, no bignum) función de energía entero. Por lo que lo hace parte de los insumos no simplemente desbordamiento? Para maximizar el número de pares de entrada significativas, la base debe ser firmado y el exponente sin signo. Supongamos que la base y exponente son ambos bits n de ancho. Fácilmente puede obtener un atado en la parte de los insumos que son significativos:

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

Por lo tanto, de los 2 pares de entrada ^ (2n), a menos de 2 ^ (n + 1) + 2 ^ (3n / 2) producen resultados significativos. Si nos fijamos en lo que es probable que la mayoría de los números enteros uso común, de 32 bits, significa esto que algo del orden de 1 / 1.000 de un uno por ciento de los pares de entrada No se limite a desbordamiento.

Debido a que no hay manera de representar a todas las potencias enteras en un int de todos modos: 

>>> print 2**-4
0.0625

Eso en realidad es una pregunta interesante. Un argumento que no he encontrado en la discusión es la simple falta de valores de retorno obvias para los argumentos. Vamos a contar las maneras la función int pow_int(int, int) hypthetical podría fallar.

  1. Overflow
  2. resultado no definido pow_int(0,0)
    3. pow_int(2,-1)
  3. El resultado no puede ser representada

La función tiene al menos 2 modos de fallo. Los enteros no pueden representar estos valores, necesitarían el comportamiento de la función en estos casos a ser definidos por el estándar -. Y programadores tendrían que ser conscientes de cómo exactamente los mangos de función estos casos

En general, el dejar a cabo la función parece ser la única opción sensata. El programador puede utilizar la versión de coma flotante con todo el informe de errores disponibles en su lugar.

Respuesta corta:

una especialización de pow(x, n) A donde n es un número natural suele ser útil para rendimiento del tiempo.Pero el genérico de la biblioteca estándar pow() todavía funciona bastante (¡asombrosamente!) bien para este propósito y es absolutamente crítico incluir la menor cantidad posible en la biblioteca C estándar para que pueda ser lo más portátil y fácil de implementar posible.Por otro lado, eso no impide en absoluto que esté en la biblioteca estándar de C++ o STL, que estoy bastante seguro de que nadie planea usar en algún tipo de plataforma integrada.

Ahora, la respuesta larga.

pow(x, n) se puede hacer mucho más rápido en muchos casos especializándose n a un número natural.Tuve 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 en O(log(n)) tiempo, pero cuando n es pequeño, 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;
    }

(me fui x y el valor de retorno se duplica porque el resultado de pow(double x, unsigned n) cabrá en un doble tan a menudo como pow(double, double) voluntad.)

(Sí, pown es recursivo, pero romper la pila es absolutamente imposible ya que el tamaño máximo de la pila será aproximadamente igual log_2(n) y n es un número entero.Si n es un entero de 64 bits, lo que le da un tamaño de pila máximo de aproximadamente 64. No El hardware tiene limitaciones de memoria tan extremas, a excepción de algunos PIC poco fiables con pilas de hardware que solo abarcan de 3 a 8 llamadas de función).

En cuanto al rendimiento, te sorprenderá la variedad de jardín. pow(double, double) es capaz de.Probé cien millones de iteraciones en mi IBM Thinkpad de 5 años con x igual al número de iteración y n igual a 10.En este escenario, pown_l ganado.glibc pow() tomó 12,0 segundos de usuario, pown tomó 7,4 segundos de usuario, y pown_l El usuario tardó sólo 6,5 segundos.Entonces eso no es demasiado sorprendente.Más o menos esperábamos esto.

Entonces, dejé x ser constante (lo configuré en 2.5), y hice un bucle n de 0 a 19 cien millones de veces.Esta vez, de forma bastante inesperada, glibc pow ¡Ganó, y por goleada!El usuario tardó sólo 2,0 segundos.Mi pown tomó 9,6 segundos, y pown_l tardó 12,2 segundos.¿Que pasó aquí?Hice otra prueba para averiguarlo.

Hice lo mismo que arriba solo que con x igual a un millón.Esta vez, pown ganó a 9,6s. pown_l tardó 12,2 segundos y glibc pow tardó 16,3 segundos.¡Ahora está claro!glibc pow se desempeña mejor que los tres cuando x es bajo, pero peor cuando x es alto.Cuando x es alto, pown_l funciona mejor cuando n es bajo y pown funciona mejor cuando x es alto.

Aquí hay tres algoritmos diferentes, cada uno de ellos capaz de funcionar mejor que los demás en las circunstancias adecuadas.Entonces, en última instancia, cuál usar probablemente depende de cómo planeas usar pow, pero usando la versión correcta es Vale la pena y tener todas las versiones es bueno.De hecho, incluso podrías 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);
}

Mientras x_expected y n_expected son constantes decididas en el momento de la compilación, junto con posiblemente algunas otras advertencias, un compilador optimizador que valga la pena eliminará automáticamente todo el pown_auto llamada a la función y reemplácela con la elección adecuada de los tres algoritmos.(Ahora, si realmente vas a intentar usar esto, probablemente tendrás que jugar un poco con ello, porque no lo intenté exactamente compilando lo que había escrito arriba.;))

Por otra parte, 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 de todo el mundo generalmente coinciden 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 los algoritmos alternativos que podría ser de utilidad.Por eso no está en el estándar C.

nota:En las pruebas de rendimiento de tiempo, 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 justos.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 es automatizado.Los resultados son bastante concluyentes (o más bien no concluyentes) para mí.Por supuesto, puedes hacerlo tú mismo.

Ronda de bonificación:una especialización de pow(x, n) a todos los números enteros es instrumental si se requiere una salida entera exacta, lo cual sucede.Considere asignar memoria para una matriz N-dimensional con p^N elementos.Quitar p^N incluso por uno resultará en una falla de segmentación posiblemente aleatoria.

Una de las razones para C ++ para no tener sobrecargas adicionales es para ser compatible con C.

C ++ 98 tiene funciones como double pow(double, int), pero éstos se han eliminado en C ++ 11 con el argumento de que C99 no los incluyen.

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

El conseguir un resultado ligeramente más precisa también significa conseguir un poco diferente resultado.

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

  • Las funciones pown, que toma un número de coma flotante y un exponente intmax_t.
  • Las funciones powr, que toma dos números de puntos flotantes (x y y) y x de cómputo a la y de alimentación con la fórmula exp(y*log(x)).

Parece que los chicos estándar con el tiempo estas características consideradas lo suficientemente útil para ser integrado en la biblioteca estándar. Sin embargo, lo racional es que estas funciones son recomendadas por la ISO / IEC / IEEE 60559: 2011 estándar de números de punto flotante binario y decimal. No puedo decir con certeza lo "estándar" fue seguido en el momento de C89, pero las evoluciones futuras de <math.h> probablemente serán muy influenciados por las futuras evoluciones del ISO / IEEE 60559 estándar / IEC .

Tenga en cuenta que la cuarta parte de la TR decimal no se incluirá en C2x (la próxima gran revisión C), y probablemente se incluirá más adelante como una característica opcional. No ha habido ningún intento que conozco para incluir esta parte de la TR en una futura revisión de C ++.

¹ se pueden encontrar algunos documentos de trabajo en curso aquí .

Tal vez porque ALU del procesador no puso en práctica una función de este tipo de números enteros, pero no hay tal instrucción FPU (como señala Stephen, es en realidad un par). Así que fue realmente más rápido para echar a duplicar, prisionero de guerra llamada con dobles, a continuación, prueba de desbordamiento y la espalda fundido, de ponerlo en práctica utilizando la aritmética de enteros.

(por un lado, reducir los logaritmos poderes a la multiplicación, pero logaritmos de los números enteros pierden una gran cantidad de precisión para la mayoría de los insumos)

Stephen es correcto que en los procesadores modernos esto ya no es cierto, pero el estándar C cuando se seleccionaron las funciones matemáticas (C ++ acaba de utilizar las funciones de C) es ahora lo que, a 20 años de edad?

Una razón muy sencilla: 

5^-2 = 1/25

Todo en la biblioteca STL se basa en el más preciso, robusto imaginables cosas. Claro, el int volvería a un cero (de 1/25), pero esto sería una respuesta inexacta.

Estoy de acuerdo, es raro en algunos casos.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top