Wyzwanie

Wyzwanie polega na napisaniu programu, który przyjmuje liczby dodatniea oraz liczbę niezerowąb i dane wyjściowe a^b(podniesione do potęgi b). Możesz używać tylko + - * / abs()jako funkcji / operatorów matematycznych. Można je stosować tylko do wartości skalarnych, ale nie do całych list lub tablic.

Przykłady:

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

Ważne: http://xkcd.com/217/

Detale

Możesz napisać funkcję lub podobną konstrukcję do użycia w konsoli. Jeśli nie możesz użyć danych wejściowych konsoli, możesz założyć, że obie liczby są zapisywane w zmiennych i wypisie przez standardowe wyjście lub zapis do pliku. Dane wyjściowe muszą być poprawne do co najmniej 4 cyfr znaczących. Można założyć, że oba ai bsą niezerowe. Czas działania znacznie dłuższy niż 1 minuta jest niedopuszczalny. Wygra najmniejsza liczba bajtów. Proszę wyjaśnić swój program i algorytm.

EDYCJA: Należy brać pod uwagę tylko pozytywne zasady . Możesz założyć a>0. Pamiętaj, że obie liczby nie muszą być liczbami całkowitymi !!!

Python, 77

Podobnie jak w przypadku niektórych innych odpowiedzi, jest to oparte na log i exp. Ale funkcje są obliczane przez numeryczne rozwiązywanie równań różniczkowych zwyczajnych.

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

Czy spełnia wymagania? Dla przykładów w pytaniu tak. W przypadku dużych a zajmie to bardzo dużo czasu. Dla dużych a lub b stanie się niedokładny.

Przykłady:

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

Aktualizacja: flawr poprosił o więcej szczegółów na temat matematyki, więc proszę bardzo. Rozważyłem następujące problemy z wartością początkową:

• x '(t) = x (t), przy x (0) = 1. Rozwiązaniem jest exp (t).
• y '(t) = przez (t), przy czym y (0) = 1. Rozwiązaniem jest exp (bt).

Jeśli mogę znaleźć wartość t taką, że x (t) = a, to będę mieć y (t) = exp (bt) = a ^ b. Najprostszym sposobem numerycznego rozwiązania problemu z wartością początkową jest metoda Eulera . Obliczasz pochodną, ​​którą funkcja ma mieć, a następnie wykonujesz krok w kierunku pochodnej i proporcjonalnie do niej, ale skalowana za pomocą małej stałej. Więc to właśnie robię, rób małe kroki, aż x będzie tak duże jak a, a następnie zobacz, jakie jest y w tym czasie. Cóż, tak o tym myślałem. W moim kodzie t nigdy nie jest jawnie obliczane (jest to 1e-7 * liczba kroków pętli while), a niektóre znaki zapisałem, wykonując obliczenia dla x za pomocą a.

JavaScript (E6) 155 174 191

Edycja 2 Zgodnie z sugestią @bebe, użycie funkcji rekurencyjnej (działa gorzej, ale krócej)
Nieznacznie zmieniono funkcję R, aby uniknąć „zbyt dużej rekurencji”
Dodano zestaw testowy. Funkcja działa dobrze dla zasad <3000 i wykładnika w zakresie -50..50.
Edytuj Golfed więcej i lepszą precyzję

Dowolna liczba rzeczywista może być przybliżona liczbą wymierną (a standardowe „rzeczywiste” liczby IEEE przechowują racjonalne wartości). Dowolną liczbę wymierną można wyrazić jako ułamek a / bz liczbami całkowitymi a i b. x ^ (a / b) jest pierwiastkiem b z (x ^ a) lub (pierwiastek b z x) ^ a. Wykładanie liczb całkowitych jest dość łatwe przez podniesienie do kwadratu. Pierwiastek całkowity można aproksymować metodami numerycznymi.

Kod

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

Testuj w FireFox lub konsoli 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))
}

Haskell, 85 90

Standardowy algorytm exp-log. Teraz pod inną nazwą, goląc jeszcze kilka znaków:

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]

raisejest teraz nazywany (%), lub %w notacji infiksowej, nawet jego użycie pochłania mniej bajtów:4.5%(-4.5)

Wersja bez golfa używa również tylko 172 bajtów:

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]

JS (ES6), 103 bajty

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)

Przykłady:

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

Użyj serii Taylora.
b^x = 1 + ln(b)*x/1! + (ln(b)*x)^2/2! + (ln(b)*x)^3/3! + (ln(b)*x)^4/4! + ...
z przybliżeniem logarytmu naturalnego :
ln(b) = (1-1/x) + (1-1/x)^2/2 + (1-1/x)^3/3 + (1-1/x)^4/4 + ...

Użyłem 128 iteracji do obliczeń b^x(więcej iteracji jest trudnych z powodu silni) i 262144 iteracji dlaln(b)

golflua 120

Korzystam z tego, że

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

i napisałem własne logi expfunkcje. Wartości ai bnależy wprowadzić w nowych wierszach podczas uruchamiania w terminalu:

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

Przykładowe przebiegi:

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

Nie golfowa wersja Lua to:

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