Elevarse al poder

12

Desafío

El desafío es escribir un programa que tome un número positivoa y un número distinto de cerob y salga a^b(a elevado a la potencia b). Solo se puede usar + - * / abs()como funciones / operadores matemáticos. Estos solo pueden aplicarse a valores escalares, pero no a listas completas o matrices.

Ejemplos:

1.234 ^ 5.678 = 3.29980
4.5   ^ 4.5   = 869.874
4.5   ^-4.5   = 0.00114959

Relevante: http://xkcd.com/217/

Detalles

Puede escribir una función o una construcción similar para usar en la consola. Si no puede usar la entrada de la consola, puede suponer que ambos números se guardan en variables y salen a través de la salida estándar o escribiendo en un archivo. La salida debe ser correcta al menos a 4 dígitos significativos. Puede suponer que ambos ay bno son cero. Un tiempo de ejecución de significativamente más de 1 minuto no es aceptable. El menor número de bytes ganará. Por favor explique su programa y su algoritmo.

EDITAR: solo se deben considerar las bases positivas . Puedes asumir a>0. ¡Tenga en cuenta que ambos números no tienen que ser enteros!

falla
fuente
3
¿Nos está pidiendo que elevemos a una potencia decimal? Como decir, 4.5 ^ 4.5?
fuandon
1
¿Esto significa que también tenemos que generar números imaginarios si la base es negativa?
bebe
1
¿Cuál debería ser el resultado -0.5 ** 0.5?
Dennis
Ok, no pensé en ese caso, gracias: las bases negativas no deben implementarse correctamente. @fuandon exactamente, los números reales pueden tener decimales (al menos en la mayoría de los lenguajes de programación =)
error
Me gustaría agregar un caso de prueba con b <0: `4.5 ^ -4.5 = 0.0011496 '
edc65

Respuestas:

3

Python, 77

Al igual que con otras respuestas, esto se basa en log y exp. Pero las funciones se calculan resolviendo numéricamente ecuaciones diferenciales ordinarias.

def f(a,b,y=1):
 if a<1:a=1/a;b=-b
 while a>1:a/=1e-7+1;y*=b*1e-7+1
 return y

¿Cumple los requisitos? Para los ejemplos en la pregunta, sí. Para grandes a, llevará mucho tiempo. Para grandes aob, se volverá inexacto.

Ejemplos:

a            b            f(a, b)      pow(a, b)      <1e-5 rel error?
       1.234        5.678       3.2998       3.2998   OK
         4.5          4.5      869.873      869.874   OK
         4.5         -4.5   0.00114959   0.00114959   OK
         0.5          0.5     0.707107     0.707107   OK
         0.5         -0.5      1.41421      1.41421   OK
          80            5  3.27679e+09   3.2768e+09   OK
     2.71828      3.14159      23.1407      23.1407   OK

Actualización: flawr pidió más detalles sobre las matemáticas, así que aquí tienes. Considere los siguientes problemas de valor inicial:

  • x '(t) = x (t), con x (0) = 1. La solución es exp (t).
  • y '(t) = por (t), con y (0) = 1. La solución es exp (bt).

Si puedo encontrar el valor de t tal que x (t) = a, entonces tendré y (t) = exp (bt) = a ^ b. La forma más simple de resolver numéricamente un problema de valor inicial es el método de Euler . Calcula la derivada que se supone que tiene la función, y luego da un paso, en la dirección de la derivada, y proporcional a ella, pero escalada por una pequeña constante. Entonces eso es lo que hago, dar pequeños pasos hasta que x sea tan grande como a, y luego ver qué es y en ese momento. Bueno, así es como lo pensé. En mi código, t nunca se calcula explícitamente (es 1e-7 * el número de pasos del bucle while), y guardé algunos caracteres haciendo los cálculos para x con a en su lugar.

recalentado
fuente
¡Eso se ve genial, estoy feliz de ver otro enfoque diferente! ¿Puedes contarnos un poco más sobre estas ecuaciones diferenciales? En general, sé cuáles son, pero no pude averiguar cómo los usa su programa =)
error
@flawr: OK, actualicé con más detalles sobre las matemáticas.
recalentado el
6

JavaScript (E6) 155174191

Edición 2 Según lo sugerido por @bebe, uso de la función recursiva (rendimiento peor pero más corto) Se
modificó ligeramente la función R para evitar "demasiada recursividad"
. Se agregó el conjunto de pruebas. La función funciona bien para bases <3000 y exponente en el rango -50..50.
Editar Golfed más y mejor precisión

Cualquier número real puede ser aproximado con un número racional (y los números 'reales' estándar de IEEE almacenan racionales de hecho). Cualquier número racional se puede expresar como una fracción a / b con enteros ayb. x ^ (a / b) es la raíz b de (x ^ a) o (raíz b de x) ^ a. La exponenciación de enteros es bastante fácil al cuadrar. La raíz entera se puede aproximar utilizando métodos numéricos.

Código

P=(x,e)=>(
  f=1e7,e<0&&(x=1/x,e=-e),
  F=(b,e,r=1)=>e?F(b*b,e>>1,e&1?r*b:r):r,
  R=(b,e,g=1,y=1e-30,d=(b/F(g,e-1)-g)/e)=>d>y|d<-y?R(b,e,g+d,y/.99):g,
  F(R(x,f),e*f)
)

Prueba en la consola FireFox o FireBug

for (i=0;i<100;i++)
{
  b=Math.random()*3000
  e=Math.random()*100-50
  p1=Math.pow(b,e) // standard power function, to check
  p2=P(b,e)
  d=(p1-p2)/p1 // relative difference
  if (!isFinite(p2) || d > 0.001) 
    console.log(i, b, e, p1, p2, d.toFixed(3))
}
edc65
fuente
Buen trabajo, no es terriblemente preciso, pero el algoritmo es bueno =)
error
¿Puedes explicar qué e&1&&(r*=b)hace esto , excepto multiplicar rpor b?
flawr
1
@flawrif(e&1 != 0) r *= b
bebe
Gracias, no estaba al tanto de esa hazaña, pero parece ser buena para jugar al golf =)
error
1
aquí está el código de trabajo: P=(x,e)=>(F=(b,e,r=1)=>e?F(b*b,e>>1,e&1?r*b:r):r,R=(b,e,g=1,y=1e-16,d=(b/F(g,e-1)-g)/e)=>d>y|d<-y?R(b,e,g+d):g,e<0&&(x=1/x,e=-e),f=1<<24,F(R(x,f),e*f))(debo estar cansado)
bebe
6

Haskell, 85 90

Algoritmo estándar de registro de exp. Ahora con un nombre diferente, eliminando algunos caracteres más:

a%b|a>1=1/(1/a)%b|0<1=sum$scanl((/).((-b*foldr1(\n b->(1-a)*(b+1/n))c)*))1c
c=[1..99]

raiseahora se llama (%), o %en notación infija, incluso haciendo que su uso consuma menos bytes:4.5%(-4.5)

La versión sin golf también usa solo 172 bytes:

raise a b | a > 1     = 1 / raise (1/a) b
          | otherwise = expo (-b* ln (1-a))

ln x = foldr1 (\n a -> x*a+x/n) [1..99]

expo x = sum $ scanl ((/) . (x*)) 1 [1..99]
La Inquisición Española
fuente
4

JS (ES6), 103 bytes

t=(x,m,f)=>{for(r=i=s=u=1;i<1<<7+f;r+=s/(u=i++*(f?1:u)))s*=m;return r};e=(a,b)=>t(b,t(a,1-1/a,9)*b-b,0)

Ejemplos:

e(1.234,5.678) = 3.299798925315965
e(4.5,4.5)     = 869.8739233782269
e(4.5,-4.5)    = 0.0011495918812070608

Utiliza la serie Taylor.
b^x = 1 + ln(b)*x/1! + (ln(b)*x)^2/2! + (ln(b)*x)^3/3! + (ln(b)*x)^4/4! + ...
con aproximación de logaritmo natural :
ln(b) = (1-1/x) + (1-1/x)^2/2 + (1-1/x)^3/3 + (1-1/x)^4/4 + ...

Utilicé 128 iteraciones para calcular b^x(más iteraciones es difícil debido a factorial) y 262144 iteraciones paraln(b)

Michael M.
fuente
Tal vez debería jugar menos golf pero agregar más precisión: e(80,5) ->1555962210.2240903- debería ser 3276800000
edc65
@ edc65, tienes razón, arreglado para 5 caracteres más.
Michael M.
1
¡Es muy agradable ver algunos enfoques diferentes!
flawr
3

golflua 120

Uso el hecho de que

a^b = exp(log(a^b)) = exp(b*log(a))

y escribí mis propias logy expfunciones. Los valores ay bdeben ingresarse en las nuevas líneas cuando se ejecutan en la terminal:

\L(x)g=0~@ i=1,50 c=(x-1)/x~@j=2,i c = c*(x-1)/x$g=g+c/i$~g$\E(x)g=1;R=1e7~@i=1,R g=g*(1+x/R)$~g$a=I.r()b=I.r()w(E(b*L(a)))

Ejecuciones de muestra:

4.5, 4.5  ==> 869.87104890175
4.5, -4.5 ==> 0.0011495904124065
3.0, 2.33 ==> 12.932794624815
9.0, 0.0  ==> 1
2.0, 2.0  ==> 3.9999996172672

Una versión sin Lua es,

-- returns log
function L(x)
   g = 0
   for i=1,50 do
      c=(x-1)/x
      for j=2,i do
         c = c*(x-1)/x
      end
      g = g + c/i
   end
   return g
end

-- returns exp
function E(x)
   g=1;L=9999999
   for i=1,L do
      g=g*(1+x/L)
   end
   return g
end

a=io.read()
b=io.read()

print(E(b*L(a)))
print(a^b)
Kyle Kanos
fuente
¿Puedes proporcionar algunos resultados de ejemplo?
error
@flawr: Supongo que puedo ... y ahora listo
Kyle Kanos