18
\$\begingroup\$

Left and right Riemann sums are approximations to definite integrals. Of course, in mathematics we need to be very accurate, so we aim to calculate them with a number of subdivisions that approaches infinity, but that's not needed for the purposes of this challenge. You should instead try to write the shortest program, taking input and providing output through any of the default methods, in any programming language, which does the following:

Task

Given two rational numbers \$a\$ and \$b\$ (the limits of the definite integral), a positive integer \$n\$, a boolean \$k\$ representing left / right and a black-box function \$f\$, calculate the left or right Riemann sum (depending on \$k\$) of \$\int_a^b f(x)\mathrm{d}x\$, using \$n\$ equal subdivisions.

I/O Specs

  • \$a\$ and \$b\$ can be rational / floating-point numbers or fractions.

  • \$k\$ can be represented by any two distinct and consistent values, but please keep in mind that you aren't allowed to take complete or partial functions as input.

  • \$f\$ is a black-box function. Citing the meta answer linked above, the content (i.e. the code) of black-box-functions may not be accessed, you can only call them (passing arguments if applicable) and observe their output. If needed, please include the necessary information about the syntax your language uses such that we can test your submission.

As output, you must provide a rational / floating-point / fraction representing the Riemann sum you are asked for. As discussed in the past, floating-point imprecision can be ignored, as long as your output is accurate to at least three decimal places when rounded to the nearest multiple of 1 / 1000 (e.g. 1.4529999 is fine instead of 1.453).

Math Specs

  • \$f\$ is guaranteed to be continuous between \$a\$ and \$b\$ (no jumps, no holes, no vertical asymptotes).

  • There are three possible cases you have to handle: \$a = b\$ (The result should be \$0\$ or its equivalents), \$a < b\$ or \$a > b\$.

  • If \$b < a\$, the integral changes its sign. Also, the right sense of the integral in this case is towards \$a\$.

  • Areas under the graph are negative and those above the graph are positive.

Examples / Test Cases

The resolution is not optimal, because I had to shrink them down a bit, but they're still readable.

  • \$f(x) = 2x + 1,\: a = 5,\: b = 13,\: n = 4\$, k = right:

    2x+1

    The result should be \$15 \cdot 2 + 19 \cdot 2 + 23 \cdot 2 + 27 \cdot 2 = 168\$, because the width of each rectangle is \$\frac{|b - a|}{n} = 2\$ and the corresponding heights are \$f(7) = 15,\:f(9) = 19,\:f(11) = 23,\:f(13) = 27\$.

  • \$f(x)=\sqrt{x},\: a = 1,\: b = 2.5,\: n = 3\$, k = left:

    Square Root

    The output should be \$1.8194792169\$.

  • \$f(x) = -3x + 4 + \frac{x^2}{5},\: a = 12.5,\: b = 2.5,\: n = 10\$, k = right:

    -3x+4+1/5x^2

    The expected output value is \$- (- 4.05 - 5.45 - 6.45 - 7.05 - 7.25 - 7.05 - 6.45 - 5.45 - 4.05 - 2.25) = 55.5\$, because the integral changes signs when flipping the boundaries (\$b<a\$).

  • \$f(x) = 9 - 4x + \frac{2x^2}{7},\: a = 0,\: b = 15,\: n = 3\$, k = left:

    9-4x+2/7x^2

    Calculating our Riemann sum, we get \$13.5714285715\$.

  • \$f(x) = 6,\: a = 1,\: b = 4,\: n = 2\$, k = right — Output: \$18\$.

  • \$f(x) = x^7 + 165x + 1,\: a = 7,\: b = 7,\: n = 4\$, k = left — Output: \$0\$.

  • \$f(x) = x \cdot \sin(x^{-1}),\: a = 0,\: b = 1,\: n = 50\$, k = right — Output: \$0.385723952885505\$. Note that sine uses radians here, but feel free to use degrees instead.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Special thanks: This challenge has been posted in the Sandbox, where it received valuable feedback from user202729, AdmBorkBork and Leaky Nun. \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 29, 2017 at 12:58
  • \$\begingroup\$ I sure hope the solutions here help many years' worth of Calc I students... \$\endgroup\$
    – Giuseppe
    Commented Dec 29, 2017 at 20:55
  • \$\begingroup\$ f(x) = x * sin(1 / x); a = 0; b = 1; n = 50; k = right — Output: 0.385723952885505. Note that sine uses radians here, but feel free to use degrees instead. Now that f(x) is a black box why does it matter? \$\endgroup\$
    – l4m2
    Commented Dec 30, 2017 at 4:55
  • \$\begingroup\$ @l4m2 It doesn’t matter much, just wanted to let people know that they shouldn’t worry about such things. \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 30, 2017 at 7:29
  • \$\begingroup\$ @Giuseppe No. The methods of programs here are even worse than methods of handheld calculators. [just saying] \$\endgroup\$
    – user202729
    Commented Dec 30, 2017 at 9:39

10 Answers 10

10
\$\begingroup\$

R, 69 65 63 57 bytes

function(a,b,n,k,f,w=(b-a)/n)sum(sapply(a+w*(1:n-k),f))*w

Try it online!

Takes k=FALSE for right-hand sums, although the TIO link now includes aliases for "left" and "right" for ease of use.

a+w*(1:n-k) generates appropriate left- or right-hand points.

Then sapply applies f to each element of the result, which we then sum up and multiply by the interval width (b-a)/n to yield the result. This last also neatly takes care of any sign issues we might have.

\$\endgroup\$
4
\$\begingroup\$

SNOBOL4 (CSNOBOL4), 127 bytes

	DEFINE('R(a,b,n,k,p)')
R	l =(b - a) / n
	i =1
l	R =R + eval(p '(a + l * (i - k))')
	i =lt(i,n) i + 1	:s(l)
	R =R * l :(return)

Try it online!

Assuming that the function p is defined somewhere, this takes a,b,n,k,(name of p), with k=0 for right and l=1 for left.

catspaw's SNOBOL4+ supports REALs but doesn't have builtin trig functions. However, I suppose one could come up with a reasonable sin function using a taylor series.

I'm not 100% sure this is the "right" way to pass a black-box function in SNOBOL (which, to my knowledge, doesn't have first-class functions), but it seems reasonable-ish to me.

I suppose that assuming the function is defined as f would be shorter, as line l could be

l	R =R + f(a + l * (i - k))

but then it's not passed as an argument, which feels a bit like "cheating".

Note that the TIO link has a :(e) after the DEFINE statement, which is so that the code will actually run properly.

\$\endgroup\$
4
\$\begingroup\$

Julia 0.6, 50 bytes

R(f,a,b,n,k)=(c=(b-a)/n;sum(f.(a+[k:n+k-1...]c))c)

Try it online!

A normalized range is constructed, collected into a vector and then scaled. Collecting the range into a vector using [X...] is necessary to avoid the inexact error when multiplying the range directly with 0 when a=b. Similarly, constructing a range directly with : or range() is not possible when a=b.

The usage of k is very similar to the solution of Guiseppe, with k=1 for right and k=0 for left.

\$\endgroup\$
2
  • \$\begingroup\$ f. vectorizes f over its argument(s)? \$\endgroup\$
    – Giuseppe
    Commented Dec 29, 2017 at 20:42
  • \$\begingroup\$ @Giuseppe: Exactly. f. is element-wise application of f. \$\endgroup\$
    – LukeS
    Commented Dec 30, 2017 at 7:00
2
\$\begingroup\$

Haskell, 73 67 bytes

Thanks to H.PWiz and Bruce Forte for the tips!

(f&a)b n k|d<-(b-a)/realToFrac n=d*sum(f<$>take n(drop k[a,a+d..]))

Try it online!

Pretty straightforward solution.

k is 0 for left and 1 for right.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ If your are taking n, you don't need to go up to b \$\endgroup\$
    – H.PWiz
    Commented Dec 29, 2017 at 23:13
2
\$\begingroup\$

Jelly, 21 bytes

ƓḶ+Ɠ÷
IḢ×¢A+ṂɠvЀÆm×I

Try it online!

Take a,b from arguments, and

n
right
f

from stdin.


If you are not familiar with Jelly, you can use Python to write the black box function f:

f(x) = 2x + 1; a = 5; b = 13; n = 4; k = right

f(x) = √x; a = 1; b = 2.5; n = 3; k = left

f(x) = -3x + 4 + 1/5 * x2; a = 12.5; b = 2.5; n = 10; k = right

f(x) = 9 - 4x + 2/7 * x2 ; a = 0; b = 15; n = 3; k = left

f(x) = 6; a = 1; b = 4; n = 2; k = right

f(x) = x * sin(1 / x); a = 0; b = 1; n = 50; k = right


Explanation:


ƓḶ+Ɠ÷     Helper niladic link.
Ɠ         First line from stdin. (n). Assume n = 4.
 Ḷ        Lowered range (unlength). Get [0, 1, 2, 3].
  +Ɠ      Add second line from stdin (k). Assume k = 1 (right).
            Get [1, 2, 3, 4].
    ÷     Divide by (n). Get [0.25,0.5,0.75,1].

IḢ×¢A+ṂɠvЀÆm×I   Main monadic link. Take input `[a, b]`, assume `a=2,b=6`.
IḢ                `a-b`. Get `-4`.
  ×¢              Multiply by value of niladic link above. Get `[-1,-2,-3,-4]`.
    A             Absolute value. Get `[1,2,3,4]`.
     +Ṃ           Add min(a, b) = 2. Get `[3,4,5,6]`.
        vЀ       For each number, evaluate with...
       ɠ            input line from stdin.
           Æm     Arithmetic mean.
             ×I   Multiply by `a-b`.

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

Python 2, 99 94 bytes

A bit of a naive solution.

def R(f,a,b,n,k):s=cmp(b,a);d=s*(b-a)/n;return s*sum(d*f([0,a,b][s]+i*d)for i in range(k,n+k))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 94 bytes in Python 2 \$\endgroup\$
    – Mr. Xcoder
    Commented Jul 25, 2019 at 5:02
  • \$\begingroup\$ For some reason I thought we had to handle integer input. Thanks. \$\endgroup\$
    – mbomb007
    Commented Jul 25, 2019 at 14:05
1
\$\begingroup\$

JavaScript (Node.js), 73 71 59 bytes

(a,b,n,k,f)=>(g=i=>i--&&g(i)+f(a+k++/n)/n)(n,k^=a>b,n/=b-a)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 65 bytes

{my \d=($^b-$^a)/$^n;sum ($a,*+d...*)[($^k+^0>d)+ ^$n]».&^f X*d}

Try it online!

Relatively straightforward. The only complication is handling the a > b case, which I do by xor-ing the input flag $^k with 0 > d, which inverts it when a > b.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 22 bytes

L<+¹/I`α©*³ß+Iδ.VÅA®*Ä

Inputs in the order \$n\$, \$k\$, \$[a,b]\$, \$f\$, with \$k\$ being 1 for right and 0 for left.

Try it online or verify all test cases.

Explanation:

L                      # Push a list in the range [1, (implicit) input n]
 <                     # Decrease each by 1 to make the range: [0, n)
  +                    # Add the (implicit) input k to each
   ¹/                  # Divide each by the first input n
     I                 # Push the next input [a,b]
      `α               # Push both separated to the stack, and take their absolute difference
        ©              # Store this in variable `®` (without popping)
         *             # Multiply it to each value in the list
          ³ß           # Push the third input [a,b] again, and pop and push its minimum
            +          # Add it to each value in the list
              δ        # Apply to each value in the list,
             I         # using the next input f:
               .V      #  Evalutate the it as 05AB1E code
                 ÅA    # Then pop and push the arithmetic mean of the list
                   ®*  # Multiply it by |a-b| from variable `®`
                     Ä # And take the absolute value of this result
                       # (after which it is output implicitly)
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Classic), 37 bytes

{(a b n k)←⍵⋄l←n÷⍨b-a⋄l×+/⍺⍺a+l×k+⍳n}

Try it online!

APL NARS, 37 chars

The function has the argument in the left the function, in the right numeric argument a b n k. In the question k=left here it means k=¯1; k=right here it means k=0. Test:

  f←{(a b n k)←⍵⋄l←n÷⍨b-a⋄l×+/⍺⍺a+l×k+⍳n}
  {1+2×⍵} f 5 13 4 0
168
  {√⍵} f 1 2.5 3 ¯1
1.819479217
  {4+(¯3×⍵)+0.2×⍵×⍵} f 12.5 2.5 10 0
55.5
  {9+(¯4×⍵)+7÷⍨2×⍵×⍵} f 0 15 3 ¯1
13.57142857
  {6-0×⍵} f 1 4 2 0
18
  {1+(165×⍵)+⍵*7} f 7 7 4 ¯1
0
  {⍵×1○÷⍵} f 0 1 50 0
0.3857239529
\$\endgroup\$
4
  • \$\begingroup\$ Submissions are counted in bytes, not characters. I don't remember if NARS has a custom code page (so it would be also 37 bytes) or uses UTF16. \$\endgroup\$
    – Uriel
    Commented Dec 30, 2017 at 17:22
  • \$\begingroup\$ @Uriel It is 37 bytes in Dyalog APL classic follow the link; possibly 35x2 bytes for Nars Apl... \$\endgroup\$
    – user58988
    Commented Dec 30, 2017 at 22:07
  • \$\begingroup\$ So why do you write it as NARS? Does NARS even has dfnss? By the way you can drop the first parents for 35 bytes \$\endgroup\$
    – Uriel
    Commented Dec 30, 2017 at 22:31
  • \$\begingroup\$ APL NARS, 37 chars means it should run in NARS APL too \$\endgroup\$
    – user58988
    Commented Dec 31, 2017 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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