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

116

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.

Dan O
fuente
4
Esta es una buena pregunta y no creo que las respuestas tengan mucho sentido. ¿Los exponentes negativos no funcionan? Tome ints sin firmar como exponentes. ¿La mayoría de las entradas hacen que se desborde? Lo mismo ocurre con exp y double pow, no veo a nadie quejarse. Entonces, ¿por qué esta función no es estándar?
static_rtti
2
@static_rtti: "Lo mismo es cierto para exp y double pow" es totalmente falso. Desarrollaré mi respuesta.
Stephen Canon
11
La biblioteca estándar de C ++ tiene double pow(int base, int exponent)desde C ++ 11 (§26.8 [c.math] / 11 viñeta 2)
Cubbi
Debe tomar una decisión entre "la implementación es trivial" y "no es divertido de escribir".
Marqués de Lorne

Respuestas:

66

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 :-)

paxdiablo
fuente
2
FWIW, no creo que C ++ siga a "Proporcionar sólo una forma de hacer una operación" como restricción. Con razón, porque, por ejemplo, las to_stringlambdas son conveniencias para cosas que ya podría hacer. Supongo que se podría interpretar "sólo una forma de hacer una operación" de manera muy vaga para permitir ambas, y al mismo tiempo permitir casi cualquier duplicación de funcionalidad que uno pueda imaginar, diciendo "¡ajá! ¡No! Porque la conveniencia hace ¡Es una operación sutilmente diferente de la alternativa exactamente equivalente pero más larga! ". Lo que ciertamente es cierto en el caso de las lambdas.
Steve Jessop
@Steve, sí, eso fue mal redactado de mi parte. Es más exacto decir que hay pautas para cada comité en lugar de que todos los comités sigan las mismas pautas. Respuesta ajustada a clarifyl
paxdiablo
2
Solo un punto (de unos pocos): "cualquier mono de código podría funcionar en diez minutos". Claro, y si 100 monos de código (término insultante agradable, por cierto) hacen eso cada año (probablemente una estimación baja), tenemos 1000 minutos perdidos. Muy eficiente, ¿no crees?
Jürgen A. Erhard
1
@ Jürgen, no estaba destinado a ser un insulto (ya que en realidad no le atribuí la etiqueta a nadie en específico), fue solo una indicación que powrealmente no requiere mucha habilidad. Ciertamente, yo prefiero que el estándar proporciona cosa que se requiere mucha habilidad, y el resultado en minutos desperdiciados mucho más si el esfuerzo tuvo que ser duplicado.
paxdiablo
2
@ eharo2, simplemente reemplace el "codificador medio decente" en el texto actual con "código mono". Tampoco pensé que fuera un insulto, pero pensé que era mejor ser cauteloso y, para ser honesto, la redacción actual transmite la misma idea.
paxdiablo
41

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.

Stephen Canon
fuente
8
De todos modos, todo esto es discutible. El hecho de que una función no sea válida para algunas o muchas entradas no la hace menos útil.
static_rtti
2
@static_rtti: pow(x,y)no sube a cero para cualquier x si | y | <= 1. Hay una banda muy estrecha de entradas (x grande, y muy cerca de -1) para las que se produce un subdesbordamiento, pero el resultado sigue siendo significativo en ese rango.
Stephen Canon
2
Habiéndolo pensado más, estoy de acuerdo con el desbordamiento. Sin embargo, sigo pensando que esto no es relevante para la pregunta.
static_rtti
7
@ybungalobill: ¿Por qué elegirías eso como motivo? Personalmente, preferiría la utilidad para una gran cantidad de problemas y programadores, la posibilidad de hacer versiones optimizadas de hardware que sean más rápidas que la implementación ingenua que probablemente escribirán la mayoría de los programadores, y así sucesivamente. Su criterio parece completamente arbitrario y, para ser franco, absolutamente inútil.
static_rtti
5
@StephenCanon: En el lado positivo, su argumento muestra que la implementación obviamente correcta y óptima de integer powes simplemente una pequeña tabla de búsqueda. :-)
R .. GitHub DEJA DE AYUDAR A ICE
11

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

>>> print 2**-4
0.0625
Ignacio Vázquez-Abrams
fuente
3
Para un tipo numérico de tamaño finito, no hay forma de representar todos los poderes de ese tipo dentro de ese tipo debido al desbordamiento. Pero tu punto sobre los poderes negativos es más válido.
Chris Lutz
1
Veo exponentes negativos como algo que una implementación estándar podría manejar, ya sea tomando un int sin signo como exponente o devolviendo cero cuando se proporciona un exponente negativo como entrada y un int es la salida esperada.
Dan O
3
o tener separados int pow(int base, unsigned int exponent)yfloat pow(int base, int exponent)
Ponkadoodle
4
Podrían simplemente declararlo como un comportamiento indefinido para pasar un entero negativo.
Johannes Schaub - litb
2
En todas las implementaciones modernas, cualquier cosa más allá int pow(int base, unsigned char exponent)es algo inútil de todos modos. O la base es 0 o 1, y el exponente no importa, es -1, en cuyo caso solo importa el último bit del exponente, o base >1 || base< -1en cuyo caso exponent<256con penalización de desbordamiento.
MSalters
9

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.

phoku
fuente
Pero, ¿no se aplicarían los dos primeros casos también a powentre flotadores? Coge dos grandes flotadores, sube uno a la potencia del otro y tienes un Overflow. Y pow(0.0, 0.0)causaría el mismo problema que su segundo punto. Su tercer punto es la única diferencia real entre implementar una función de potencia para enteros y flotantes.
numbermaniac
7

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.

enigmático fisico
fuente
Supongo que si se deshace de la recursividad, se ahorrará el tiempo necesario para la asignación de la pila. Y sí, tuvimos una situación en la que el poder estaba ralentizando todo y tenemos que implementar nuestro propio poder.
Sambatión
"Nadie tiene limitaciones de memoria tan extremas" es falso. PIC a menudo tiene una pila de llamadas limitada para un máximo de 3 (el ejemplo es PIC10F200) a 8 (el ejemplo es 16F722A) llamadas (PIC usa una pila de hardware para llamadas de función).
12431234123412341234123
oh, hombre eso es brutal jajaja. Bien, entonces no funcionará en esos PIC.
enigmaticPhysicist
Para una base entera así como para poder, como se pregunta en la pregunta, los compiladores (gcc y clang) producirán fácilmente un bucle sin ramificaciones a partir de una implementación iterativa (en lugar de recursiva). Esto evita errores de predicción de rama de cada bit de n. godbolt.org/z/L9Kb98 . gcc y clang no optimizan la definición recursiva en un bucle simple y, de hecho, se ramifican en cada bit de n. (Porque pown_iter(double,unsigned)todavía se ramifican, pero una implementación SSE2 o SSE4.1 sin ramificaciones debería ser posible en x86 asm o con intrínsecos C. Pero incluso eso es mejor que la recursividad)
Peter Cordes
Mierda, ahora tengo que volver a hacer los puntos de referencia con una versión basada en bucles solo para estar seguro. Lo pensare.
enigmaticFysicist
6

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 .

Bo Persson
fuente
3

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í .

Morwenn
fuente
¿Hay alguna implementación plausible en la que el uso powncon un exponente mayor que LONG_MAXnunca debería producir un valor diferente al uso LONG_MAX, o donde un valor menor que LONG_MINdebería producir un valor diferente del LONG_MIN? Me pregunto qué beneficio se obtiene al usar intmax_tcomo exponente.
supercat
@supercat No tengo idea, lo siento.
Morwenn
Vale la pena mencionar que, mirando el Estándar, parece que también define una función "crpown" opcional que, si se define, sería una versión correctamente redondeada de "pown"; de lo contrario, la Norma no especifica el grado de precisión requerido. Implementar un "pown" rápido y moderadamente preciso es fácil, pero asegurar el redondeo correcto en todos los casos puede resultar mucho más costoso.
supercat
2

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?

Ben Voigt
fuente
5
No conozco ninguna arquitectura actual con una instrucción FPU para pow. x86 tiene una y log2 xinstrucción ( fyl2x) que se puede usar como la primera parte de una powfunción, pero una powfunción escrita de esa manera requiere cientos de ciclos para ejecutarse en el hardware actual; una rutina de exponenciación de enteros bien escrita es varias veces más rápida.
Stephen Canon
No sé si "cientos" es exacto, parece ser alrededor de 150 ciclos para fyl2x y luego f2xm1 en la mayoría de las CPU modernas y eso se canaliza con otras instrucciones. Pero tiene razón en que una implementación de enteros bien ajustada debería ser mucho más rápida (en estos días) ya que IMUL se ha acelerado mucho más que las instrucciones de punto flotante. Sin embargo, cuando se escribió el estándar C, IMUL era bastante caro y usarlo en un bucle probablemente tomó más tiempo que usar la FPU.
Ben Voigt
2
Cambié mi voto a la luz de la corrección; Aun así, tenga en cuenta (a) que el estándar C se sometió a una revisión importante (incluida una gran expansión de la biblioteca matemática) en 1999, y (b) que el estándar C no está escrito en ninguna arquitectura de procesador específica: la presencia o la ausencia de instrucciones FPU en x86 no tiene esencialmente nada que ver con la funcionalidad que el comité C elige estandarizar.
Stephen Canon
No está vinculado a ninguna arquitectura, es cierto, pero el costo relativo de la interpolación de una tabla de búsqueda (generalmente utilizada para la implementación de punto flotante) en comparación con la multiplicación de enteros ha cambiado casi por igual para todas las arquitecturas, supongo.
Ben Voigt
1

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
serg06
fuente
-2

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.

Dima Pasechnik
fuente
2
Esto es incorrecto. La sobrecarga (7) es a pow ( Arithmetic1 base, Arithmetic2 exp )qué se enviará doubleo long doublesi ha leído la descripción: "7) Un conjunto de sobrecargas o una plantilla de función para todas las combinaciones de argumentos de tipo aritmético no cubiertos por 1-3). Si hay algún argumento tiene un tipo integral, se convierte en double. Si cualquier argumento es long double, entonces el tipo de retorno Promoted también es long double; de ​​lo contrario, el tipo de retorno es siempre double ".
phuclv
¿Qué es incorrecto aquí? Simplemente dije que hoy en día (desde C ++ 11) hay una plantilla de pow ( , ) en la biblioteca estándar, lo que no era el caso en 2010.
Dima Pasechnik
5
No, no es así. Los Templeates promueven estos tipos al doble o al doble largo. Entonces funciona en dobles por debajo.
Trismegistos
1
@Trismegistos Todavía permite int parámetros. Si esta plantilla no estuviera allí, pasar los parámetros int hace que interprete los bits en el int como un flotante, provocando resultados inesperados arbitrarios. Lo mismo ocurre con los valores de entrada mixtos. eg pow(1.5f, 3)= 1072693280but pow(1.5f, float(3))=3.375
Mark Jeronimus
2
El OP lo solicitó int pow(int, int), pero C ++ 11 solo proporciona double pow(int, int). Vea la explicación de @phuclv.
xuhdev
-4

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.

Jason A.
fuente
3
Obviamente, es necesario un segundo argumento sin firmar. Hay muchas aplicaciones que solo requieren potencias enteras no negativas.
enigmaticPhysicist