24
\$\begingroup\$

You are to approximate the value of:

enter image description here

Where your input is I.

Rules

  • You may not use any built-in integral functions.
  • You may not use any built-in infinite summation functions.
  • Your code must execute in a reasonable amount of time ( < 20 seconds on my machine)
  • You may assume that input is greater than 0 but less than your language's upper limit.
  • It may be any form of standard return/output.

You can verify your results at Wolfram | Alpha (you can verify by concatenating your intended input to the linked query).

Examples

(let's call the function f)

f(1) -> 2.18273
f(50) -> 6.39981
f(10000) -> 6.39981
f(2.71828) -> 5.58040
f(3.14159) -> 5.92228

Your answer should be accurate to ±.0001.

\$\endgroup\$
  • \$\begingroup\$ @ThomasKwa Maximum for your language. I'll add it to the question. \$\endgroup\$ – Addison Crump Feb 6 '16 at 22:52
  • \$\begingroup\$ Wolfram Alpha says the last one rounds to 5.92228 \$\endgroup\$ – Neil Feb 7 '16 at 0:33
  • \$\begingroup\$ @Neil o-o Alrighty then, must've mistyped. Thanks! \$\endgroup\$ – Addison Crump Feb 7 '16 at 0:47
  • 7
    \$\begingroup\$ I'll award 200 rep to the shortest valid answer in TI-BASIC that executes in <20 seconds on WabbitEmu at 100% speed. \$\endgroup\$ – lirtosiast Feb 7 '16 at 1:24
  • \$\begingroup\$ @lirtosiast If you are still intent on following up on this bounty, you should post it here instead. \$\endgroup\$ – Addison Crump Feb 28 '16 at 0:31
10
\$\begingroup\$

Julia, 79 77 38 bytes

I->sum(x->(e/x)^x,0:1e-5:min(I,9))/1e5

This is an anonymous function that accepts a numeric value and returns a float. To call it, assign it to a variable.

The approach here is to use a right Riemann sum to approximate the integral, which is given by the following formula:

latex

In our case, a = 0 and b = I, the input. We divide the region of integration into n = 105 discrete portions, so ∆x = 1/n = 10-5. Since this is a constant relative to the sum, we can pull this outside of the sum and simply sum the function evaluations at each point and divide by n.

The function is surprisingly well-behaved (plot from Mathematica):

mathematicaplot

Since the function evaluates nearly to 0 for inputs greater than about 9, we truncate the input to be I if I is less than 9, or 9 otherwise. This simplifies the calculations we have to do significantly.

Ungolfed code:

function g(I)
    # Define the range over which to sum. We truncate the input
    # at 9 and subdivide the region into 1e5 pieces.
    range = 0:1e-5:min(I,9)

    # Evaluate the function at each of the 1e5 points, sum the
    # results, and divide by the number of points.
    return sum(x -> (e / x)^x, range) / 1e5
end

Saved 39 bytes thanks to Dennis!

\$\endgroup\$
  • \$\begingroup\$ Isn't this also equivalent to: $\frac{t\sum_{k=0}^{n}(f(a+kt)+f(a+(k+1)t))}{2}$? That seems slightly simpler of an algorithm to use. \$\endgroup\$ – Addison Crump Feb 7 '16 at 1:37
  • \$\begingroup\$ 10^4 can be written as 1e4. \$\endgroup\$ – Rainer P. Feb 7 '16 at 16:22
  • \$\begingroup\$ @VoteToClose Ended up taking a different approach \$\endgroup\$ – Alex A. Feb 7 '16 at 22:03
  • \$\begingroup\$ @RainerP. Heh, right. Thanks. \$\endgroup\$ – Alex A. Feb 7 '16 at 22:03
  • \$\begingroup\$ The asymptotic value of the integral is $6.39981...$. The value $6.39981... - 10^{-4}$ is first attained at $I = 7.91399...$, so you can truncate at $8$ instead of $9$ to save a little time. \$\endgroup\$ – Eric Towers Feb 7 '16 at 22:56
9
\$\begingroup\$

Jelly, 20 19 17 bytes

ð«9×R÷øȷ5µØe÷*×ḢS

This borrows the clever truncate at 9 trick from @AlexA.'s answer, and uses a right Riemann sum to estimate the corresponding integral.

Truncated test cases take a while, but are fast enough on Try it online!

How it works

ð«9×R÷øȷ5µØe÷*×ḢS  Main link. Input: I

      øȷ5          Niladic chain. Yields 1e5 = 100,000.

ð                  Dyadic chain. Left argument: I. Right argument: 1e5.
 «9                Compute min(I, 9).
   ×               Multiply the minimum with 1e5.
    R              Range; yield [1, 2, ..., min(I, 9) * 1e5] or [0] if I < 1e-5.
     ÷             Divide the range's items by 1e5.
                   This yields r := [1e-5, 2e-5, ... min(I, 9)] or [0] if I < 1e-5.

         µ         Monadic chain. Argument: r
          Øe÷      Divide e by each element of r.
             *     Elevate the resulting quotients to the corresponding elements,
                   mapping t -> (e/t) ** t over r.
                   For the special case of r = [0], this yields [1], since
                   (e/0) ** 0 = inf ** 0 = 1 in Jelly.
              ×Ḣ   Multiply each power by the first element of r, i.e., 1e-5 or 0.
                S  Add the resulting products.
\$\endgroup\$
  • \$\begingroup\$ Oh, alright. Left-hand rule is how it's referred to in AP Calculus classes. :P Coolio. \$\endgroup\$ – Addison Crump Feb 7 '16 at 0:20
  • \$\begingroup\$ I'm not familiar with that name, but the left-hand rule probably uses the left endpoints. My code uses the right ones. \$\endgroup\$ – Dennis Feb 7 '16 at 0:24
  • 2
    \$\begingroup\$ (~-.-)~ It's some form of handed rule. xD \$\endgroup\$ – Addison Crump Feb 7 '16 at 0:31
4
\$\begingroup\$

ES7, 78 bytes

i=>[...Array(n=2e3)].reduce(r=>r+Math.exp(j+=i)/j**j,0,i>9?i=9:0,i/=n,j=-i/2)*i

This uses the rectangle rule with 2000 rectangles, which (at least for the examples) seem to produce a sufficiently accurate answer, but the accuracy could easily be increased if necessary. It has to use the 9 trick otherwise the accuracy drops off for large values.

73 byte version that uses rectangles of width ~0.001 so it doesn't work above ~700 because Math.exp hits Infinity:

i=>[...Array(n=i*1e3|0)].reduce(r=>r+Math.exp(j+=i)/j**j,0,i/=n,j=-i/2)*i
\$\endgroup\$
2
\$\begingroup\$

golflua, 83 chars

I'll admit it: it took my a while to figure out the min(I,9) trick Alex presented allowed computing arbitrarily high numbers because the integral converged by then.

\f(x)~M.e(x)/x^x$b=M.mn(I.r(),9)n=1e6t=b/n g=0.5+f(b/2)~@k=1,n-1g=g+f(k*t)$I.w(t*g)

An ungolfed Lua equivalent would be

function f(x)
   return math.exp(x)/x^x
end

b=math.min(io.read("*n"),9)
n=1e6
t=b/n
g=0.5+f(b/2)

for k=1,n-1 do
   g=g+f(k*t)
end
io.write(t*g)
\$\endgroup\$
  • \$\begingroup\$ And by "a while" I mean about 10 minutes. And that was entirely because I didn't actually read Alex's comment that explains it, just saw it in the code. \$\endgroup\$ – Kyle Kanos Feb 7 '16 at 3:35
2
\$\begingroup\$

Python 2, 94 76 bytes

Thanks to @Dennis for saving me 18 bytes!

lambda I,x=1e5:sum((2.71828/i*x)**(i/x)/x for i in range(1,int(min(I,9)*x)))

Try it online with testcases!

Using the rectangle method for the approximation. Using a rectangle width of 0.0001 which gives me the demanded precision. Also truncating inputs greater 9 to prevent memory errors with very big inputs.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 90 55 bytes

{my \x=1e5;sum ((e/$_*x)**($_/x)/x for 1..min($_,9)*x)}

usage

my &f = {my \x=1e5;sum ((e/$_*x)**($_/x)/x for 1..min($_,9)*x)}

f(1).say;       # 2.1827350239231
f(50).say;      # 6.39979602775846
f(10000).say;   # 6.39979602775846
f(2.71828).say; # 5.58039854392816
f(3.14159).say; # 5.92227602782184

It's late and I need to sleep, I'll see if I can get this any shorter tomorrow.

EDIT: Managed to get it quite a bit shorter after seeing @DenkerAffe 's method.

\$\endgroup\$
  • 1
    \$\begingroup\$ I like how it says $h*t in there. :D \$\endgroup\$ – Addison Crump Feb 7 '16 at 10:30
2
\$\begingroup\$

Pyth, 34 29 bytes

Saved 5 Bytes with some help from @Dennis!

J^T5smcc^.n1d^ddJmcdJU*hS,Q9J

Try it online!

Explanation

Same algorithm as in my Python answer.

J^T5smcc^.n1d^ddJmcdJU*hS,Q9J        # Q=input
J^T5                                 # set J so rectangle width *10^5
                       hS,Q9         # truncate inputs greater 9
                 mcdJU/     J        # range from zero to Input in J steps
     mcc^.n1d^ddJ                    # calculate area for each element in the list
    s                                # Sum all areas and output result

\$\endgroup\$
  • \$\begingroup\$ You can save a few bytes by assigning J to ^T5 and swapping multiplication with division by J. Also, the truncation can be done with hS,Q9. \$\endgroup\$ – Dennis Feb 7 '16 at 18:01
  • \$\begingroup\$ @Dennis Thanks, did not think about that. Also the sorting trick is nice, I was just searching for min ^^ \$\endgroup\$ – Denker Feb 8 '16 at 8:54
2
\$\begingroup\$

MATL, 26 bytes

9hX<t1e6XK:K/*ttZebb^/sK/*

This approximates the integral as a Riemann sum. As argued by Alex, we can truncate the integration interval at approximately 9 because the function values are very small beyond that.

The maximum value of the function is less than 3, so a step of about 1e-5 should be enough to obtain the desired accuracy. So for the maximum input 9 we need about 1e6 points.

This takes about 1.5 seconds in the online compiler, for any input value.

Try it online!

9hX<         % input number, and limit to 9
t            % duplicate
1e6XK:       % generate vector [1,2,...,1e6]. Copy 1e6 to clipboard K
K/*          % divide by 1e6 and multiply by truncated input. This gives 
             % a vector with 1e6 values of x from 0 to truncated input
ttZe         % duplicate twice. Compute exp(x)
bb^          % rotate top three elements of stack twice. Compute x^x
/            % divide to compute exp(x)/x^x
s            % sum function values
K/*          % multiply by the step, which is the truncated input divided
             % by 1e6
\$\endgroup\$
2
\$\begingroup\$

Vitsy, 39 bytes

Thought I might as well give my own contribution. ¯\_(ツ)_/¯ This uses the Left-Hand Riemann Sum estimation of integrals.

D9/([X9]1a5^D{/V}*0v1{\[EvV+DDv{/}^+]V*

D9/([X9]               Truncation trick from Alex A.'s answer.
D                      Duplicate input.
 9/                    Divide it by 9.
   ([  ]               If the result is greater than 0
     X9                Remove the top item of the stack, and push 9.

1a5^D{/V}*0v0{         Setting up for the summation.
1                      Push 1.
 a5^                   Push 100000.
    D                  Duplicate the top item of the stack.
     {                 Push the top item of the stack to the back.
      /                Divide the top two items of the stack. (1/100000)
       V               Save it as a global variable.
                       Our global variable is ∆x.
        }              Push the bottom item of the stack to the top.
         *             Multiply the top two items.
                       input*100000 is now on the stack.
          0v           Save 0 as a temporary variable.
            0          Push 1.
             {         Push the bottom item of the stack to the top.
                       input*100000 is now the top of the stack.

\[EvV+DDv{/}^+]        Summation.
\[            ]        Loop over this top item of the stack times.
                       input*100000 times, to be exact.
  E                    Push Math.E to the stack.
   v                   Push the temporary variable to the stack.
                       This is the current value of x.
    V+                 Add ∆x.
      DD               Duplicate twice.
        v              Save the temporary variable again.
         {             Push the top item of the stack to the back.
          /            Divide the top two items.
                       e/x
           }           Push the top item back to the top of the stack.
            ^          Put the second to top item of the stack to the power of the top item.
                       (e/x)^x
             +         Add that to the current sum.

V*                     Multiply by ∆x

This leaves the sum on the top of the stack. The try it online link below has N on the end to show you the result.

Try it Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.