utiliza - potencia en c++ sin pow

¿Por qué no es int pow(int base, int exponente) en las bibliotecas estándares de C++? (10)

Siento que no puedo encontrarlo. ¿Hay alguna razón por la cual la función pow de c ++ no implementa la función "power" para nada excepto floats y dobles?

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 una manera constante y explícita) no es divertido de escribir.

Como cuestión de hecho, lo hace.

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

Como yo no estaba ni estrechamente asociado con los creadores de C ni de C ++ en los días de su creación (aunque soy bastante viejo) ni como parte de los comités ANSI / ISO que crearon los estándares, esto necesariamente es una opinión de mi parte. Me gustaría pensar que es una opinión informada pero, como mi esposa te dirá (con frecuencia y sin mucho aliento), me he equivocado antes :-)

La suposición, por lo que vale, sigue.

Sospecho que la razón por la C original (antes de ANSI) no tenía esta característica es porque era totalmente innecesario. Ya existía una manera perfectamente buena de hacer potencias enteras (con dobles y luego simplemente convertir de nuevo a un número entero, lo que le da la posibilidad de verificar el desbordamiento y desbordamiento de enteros antes de convertir).

La otra cosa que debes recordar es que la intención original de C era un lenguaje de programación de sistemas y es cuestionable si el punto flotante es deseable en esa arena de todos modos. Como su caso de uso inicial era codificar UNIX, el punto flotante habría sido inútil. BCPL, en el que se basó C, tampoco tenía ningún uso para las potencias (no tenía ningún punto flotante, de memoria).

Como un aparte, un operador de potencia 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 en lugar de la biblioteca.

Dado que la implementación del poder integral es relativamente trivial, es casi seguro que los desarrolladores del lenguaje utilizarán mejor su tiempo para proporcionar más cosas útiles (ver los comentarios a continuación sobre el costo de oportunidad).

Eso también es relevante para el C ++ original. Como la implementación original era solo un traductor que producía el código C, transportaba muchos de los atributos de C. Su intención original era C-con-clases, no C-con-clases-más-un-pequeño-bit-de -extra-math-cosas.

En cuanto a por qué nunca se ha agregado a los estándares, debe recordar que los organismos que establecen normas tienen pautas específicas a seguir. Por ejemplo, ANSI C se encargó específicamente de codificar la práctica existente, no de crear un nuevo idioma. De lo contrario, podrían haberse vuelto locos y darnos Ada :-)

Las iteraciones posteriores de esa norma también tienen pautas específicas y se pueden encontrar en los documentos de justificación (fundamento de por qué el comité tomó ciertas decisiones, no razones para el lenguaje en sí).

Por ejemplo, el documento de justificación C99 lleva adelante específicamente dos de los principios rectores de C89 que limitan lo que se puede agregar:

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

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

Además, los organismos de fijación de normas se dan cuenta de que existe un costo de oportunidad (un término económico que significa lo que debe renunciar a una decisión tomada) para cada decisión que toman. Por ejemplo, el costo de oportunidad de comprar esa máquina uber-gaming de $ 10,000 es 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 100 puntos en el hoyo, por lo que tiene que agregar un poco de valor para ser siquiera considerado.

En otras palabras, ¿preferiría tener un operador de energía integral (que, honestamente, cualquier mono de código podría aumentar en diez minutos) o agregar varios hilos al estándar? Para mí, preferiría tener lo último y no tener que rebuscar 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 lógica:

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

Y el número de implementadores en los organismos de estándares supera con creces la cantidad de programadores (o al menos los programadores que no comprenden el costo de oportunidad). Si se añadiera todo eso, el siguiente C ++ estándar sería C ++ 215x y probablemente los desarrolladores del compilador lo implementarían completamente trescientos años después.

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

El mundo está en constante evolución, al igual que 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 funciones pown , que toman un número de coma flotante y un exponente intmax_t .
Las funciones de powr , que toman dos números de puntos flotantes ( y ) y calculan x la potencia y con la fórmula exp(y*log(x)) .

Parece que los tipos 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 son recomendadas por el estándar ISO / IEC / IEEE 60559: 2011 para números de coma flotante binarios y decimales. 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 del estándar ISO / IEC / IEEE 60559 .

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

¹ here puede encontrar documentación sobre el trabajo en progreso.

Esa es en realidad 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 función hypthetical int pow_int(int, int) podría fallar.

Rebosar
Resultado indefinido pow_int(0,0)
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 necesitaría ser definido por el estándar, y los programadores tendrían que ser conscientes de cómo exactamente maneja la función estos casos.

En general, salir de la función parece ser la única opción sensata. El programador puede usar la versión de punto flotante con todos los informes de error disponibles.

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?

Bastante 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 es cierto para exp y doble pow, no veo a nadie quejarse". Esto es incorrecto.

Dejemos a un lado exp , porque eso está fuera del punto (aunque realmente haría mi caso más fuerte), y concéntrese en double pow(double x, double y) . ¿Para qué parte de los pares (x, y) hace esta función algo útil (es decir, no simplemente desbordamiento o subdesbordamiento)?

En realidad, voy a centrarme solo en una pequeña porción de los pares de entrada para los que pow tiene sentido, porque eso será suficiente para probar mi punto: si x es positivo y | y | <= 1, entonces pow no se desborda ni sube por debajo del flujo. Esto comprende casi un cuarto de todos los pares de coma flotante (exactamente la mitad de los números de coma flotante no NaN son positivos, y solo menos de la mitad de los números de coma flotante no NaN tienen una magnitud menor que 1). Obviamente, hay muchos otros pares de entrada para los que pow produce resultados útiles, pero hemos comprobado que es al menos un cuarto de todas las entradas.

Ahora veamos una función de potencia entera de ancho fijo (es decir, no bignum). ¿Para qué parte de las entradas no se desborda? Para maximizar el número de pares de entrada significativos, la base debe estar firmada y el exponente sin signo. Supongamos que la base y el exponente son ambos n bits 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, cualquier base es significativa.
Si el exponente es 2 o mayor, ninguna base mayor a 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 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.

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

>>> print 2**-4 0.0625

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 lanzar al doble, llamar a pow con dobles, luego probar el desbordamiento y devolverlo, que implementarlo usando la aritmética de enteros.

(Por un lado, los logaritmos reducen los poderes a la multiplicación, pero los logaritmos de los 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 las funciones matemáticas fueron seleccionadas (C ++ acaba de usar las funciones C) es ahora ¿qué, 20 años?

Respuesta corta:

Una especialización de pow(x, n) donde n es un número natural a menudo es útil para el rendimiento en el tiempo . Pero el pow() genérico pow() la biblioteca estándar todavía funciona muy bien ( ¡sorprendentemente! ) 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 lo detiene en absoluto de estar en la biblioteca estándar de C ++ o el STL, que estoy bastante seguro de que nadie planea usar en algún tipo de plataforma incrustada.

Ahora, para la respuesta larga.

pow(x, n) puede hacerse mucho más rápido en muchos casos al especializar 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 el tiempo O(log(n)) , pero cuando n es 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é x y el valor de retorno como doble porque el resultado de pow(double x, unsigned n) encajará en un doble aproximadamente con la misma frecuencia que lo hará el pow(double, double) .

(Sí, pown es recursivo, pero romper la pila es absolutamente imposible ya que el tamaño máximo de pila será aproximadamente igual a log_2(n) n es un entero. Si n es un entero de 64 bits, eso le da un tamaño de pila máximo de aproximadamente 64. Ningún hardware tiene tales limitaciones extremas de memoria, a excepción de algunos PIC dudosos con pilas de hardware que solo funcionan de 3 a 8 llamadas de profundidad.)

En cuanto a rendimiento, te sorprenderá lo que una variedad de jardín pow(double, double) es capaz de hacer. 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 ganó. glibc pow() tardó 12.0 segundos de usuario, pown tomó 7.4 segundos de usuario, y pown_l tomó solo 6.5 segundos de usuario. Entonces eso no es demasiado sorprendente. Estábamos más o menos esperando esto.

Entonces, dejé que x sea constante (lo configuré a 2.5), y bifurqué n de 0 a 19 cien millones de veces. Esta vez, bastante inesperadamente, glibc pow ganó, y por un deslizamiento de tierra! Solo tomó 2.0 segundos de usuario. Mi pown tomó 9.6 segundos, y pown_l tomó 12.2 segundos. ¿Lo que pasó aquí? Hice otra prueba para averiguarlo.

Hice lo mismo que arriba solo con x igual a un millón. Esta vez, pown ganó a 9.6 segundos. pown_l tomó 12.2s y glibc pow tomó 16.3s. ¡Ahora está claro! glibc pow comporta mejor que los tres cuando x es bajo, pero peor cuando x es alto. Cuando x es alto, pown_l tiene mejor pown_l cuando n es bajo, y pown funciona mejor cuando x es alto.

Entonces aquí hay tres algoritmos diferentes, cada uno capaz de desempeñarse mejor que los demás bajo las circunstancias correctas. Por lo tanto, en última instancia, lo que más probablemente dependa de cómo se planea usar pow , pero usar la versión correcta lo vale, y tener todas las versiones es bueno. 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_expected y n_expected sean constantes decididas en tiempo de compilación, junto con posiblemente algunas otras advertencias, un compilador de optimización que valga la pena eliminará automáticamente toda la pown_auto función pown_auto y la reemplazará con la elección adecuada de los tres algoritmos. (Ahora, si realmente vas a intentar usar esto, probablemente tendrás que jugar con eso un poco, porque no intenté exactamente compilar lo que había escrito arriba;;))

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 de todo el mundo generalmente aceptan que glibc ya es demasiado grande para ellos), y no puede ser portátil si para cada función matemática simple necesita incluir cada Algoritmo alternativo que podría ser de utilidad. Entonces, es por eso que no está en el estándar C.

nota al pie: en las pruebas de rendimiento de tiempo, di a mis funciones indicadores de optimización relativamente generosos ( -s -O2 ) que probablemente sean comparables, si no peores, a lo que probablemente se utilizó para compilar glibc en mi sistema (archlinux), por lo que los resultados son probablemente justos Para una prueba más rigurosa, tendría que compilar glibc y no tengo ganas de hacerlo. Solía usar Gentoo, así que recuerdo cuánto tiempo lleva, incluso cuando la tarea está automatizada . Los resultados son concluyentes (o bastante inconcluyentes) lo suficiente para mí. Por supuesto, puede hacerlo usted mismo.

Ronda de bonificación: una especialización de pow(x, n) para todos los enteros es instrumental si se requiere una salida entera exacta, lo que sucede. Considere asignar memoria para una matriz N-dimensional con elementos p ^ N. Quitar p ^ N incluso en uno dará como resultado una segfault posiblemente aleatoria.

Una razón muy simple:

5^-2 = 1/25

Todo en la biblioteca de STL se basa en las cosas más precisas y robustas imaginables. Claro, el int regresaría a un cero (desde 1/25) pero esta sería una respuesta inexacta.

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

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

C ++ 98 tiene funciones como double pow(double, int) , pero estas se han eliminado en C ++ 11 con el argumento de que C99 no las incluyó.

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

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