What does this square bracket and parenthesis bracket notation mean [first1,last1)?

264.1k views Asked by At

I have seen number ranges represented as [first1,last1) and [first2,last2).

I would like to know what such a notation means.

4

There are 4 answers

8
Michael Mrozek On BEST ANSWER

A bracket - [ or ] - means that end of the range is inclusive -- it includes the element listed. A parenthesis - ( or ) - means that end is exclusive and doesn't contain the listed element. So for [first1, last1), the range starts with first1 (and includes it), but ends just before last1.

Assuming integers:

  • (0, 5) = 1, 2, 3, 4
  • (0, 5] = 1, 2, 3, 4, 5
  • [0, 5) = 0, 1, 2, 3, 4
  • [0, 5] = 0, 1, 2, 3, 4, 5
0
Michaelangel007 On

The concept of interval notation comes up in both Mathematics and Computer Science. The Mathematical notation [, ], (, ) denotes the domain (or range) of an interval.

  • The brackets [ and ] means:

    1. The number is included,
    2. This side of the interval is closed,
  • The parenthesis ( and ) means:

    1. The number is excluded,
    2. This side of the interval is open.

An interval with mixed states is called "half-open".

For example, the range of consecutive integers from 1 .. 10 (inclusive) would be notated as such:

  • [1,10]

Notice how the word inclusive was used. If we want to exclude the end point but "cover" the same range we need to move the end-point:

  • [1,11)

For both left and right edges of the interval there are actually 4 permutations:

(1,10) =   2,3,4,5,6,7,8,9       Set has  8 elements
(1,10] =   2,3,4,5,6,7,8,9,10    Set has  9 elements
[1,10) = 1,2,3,4,5,6,7,8,9       Set has  9 elements
[1,10] = 1,2,3,4,5,6,7,8,9,10    Set has 10 elements

How does this relate to Mathematics and Computer Science?

Array indexes tend to use a different offset depending on which field are you in:

  • Mathematics tends to be one-based.
  • Certain programming languages tends to be zero-based, such as C, C++, Javascript, Python, while other languages such as Mathematica, Fortran, Pascal are one-based.

These differences can lead to subtle fence post errors, aka, off-by-one bugs when implementing Mathematical algorithms such as for-loops.

Integers

If we have a set or array, say of the first few primes [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], Mathematicians would refer to the first element as the 1st absolute element. i.e. Using subscript notation to denote the index:

  • a1 = 2
  • a2 = 3
  • :
  • a10 = 29

Some programming languages, in contradistinction, would refer to the first element as the zero'th relative element.

  • a[0] = 2
  • a[1] = 3
  • :
  • a[9] = 29

Since the array indexes are in the range [0,N-1] then for clarity purposes it would be "nice" to keep the same numerical value for the range 0 .. N instead of adding textual noise such as a -1 bias.

For example, in C or JavaScript, to iterate over an array of N elements a programmer would write the common idiom of i = 0, i < N with the interval [0,N) instead of the slightly more verbose [0,N-1]:

function main() {
    var output = "";
    var a = [ 2, 3, 5, 7,  11, 13, 17, 19, 23, 29 ];
    for( var i = 0; i < 10; i++ ) // [0,10)
       output += "[" + i + "]: " + a[i] + "\n";

    if (typeof window === 'undefined') // Node command line
        console.log( output )
    else
        document.getElementById('output1').innerHTML = output;
}
 <html>
     <body onload="main();">
         <pre id="output1"></pre>
     </body>
 </html>

Mathematicians, since they start counting at 1, would instead use the i = 1, i <= N nomenclature but now we need to correct the array offset in a zero-based language.

e.g.

function main() {
    var output = "";
    var a = [ 2, 3, 5, 7,  11, 13, 17, 19, 23, 29 ];
    for( var i = 1; i <= 10; i++ ) // [1,10]
       output += "[" + i + "]: " + a[i-1] + "\n";

    if (typeof window === 'undefined') // Node command line
        console.log( output )
    else
        document.getElementById( "output2" ).innerHTML = output;
}
<html>
    <body onload="main()";>
        <pre id="output2"></pre>
    </body>
</html>

Aside:

In programming languages that are 0-based you might need a kludge of a dummy zero'th element to use a Mathematical 1-based algorithm. e.g. Python Index Start

Floating-Point

Interval notation is also important for floating-point numbers to avoid subtle bugs.

When dealing with floating-point numbers especially in Computer Graphics (color conversion, computational geometry, animation easing/blending, etc.) often times normalized numbers are used. That is, numbers between 0.0 and 1.0.

It is important to know the edge cases if the endpoints are inclusive or exclusive:

  • (0,1) = 1e-M .. 0.999...
  • (0,1] = 1e-M .. 1.0
  • [0,1) = 0.0 .. 0.999...
  • [0,1] = 0.0 .. 1.0

Where M is some machine epsilon. This is why you might sometimes see const float EPSILON = 1e-# idiom in C code (such as 1e-6) for a 32-bit floating point number. This SO question Does EPSILON guarantee anything? has some preliminary details. For a more comprehensive answer see FLT_EPSILON and David Goldberg's What Every Computer Scientist Should Know About Floating-Point Arithmetic

Some implementations of a random number generator, random() may produce values in the range 0.0 .. 0.999... instead of the more convenient 0.0 .. 1.0. Proper comments in the code will document this as [0.0,1.0) or [0.0,1.0] so there is no ambiguity as to the usage.

Example:

  • You want to generate random() colors. You convert three floating-point values to unsigned 8-bit values to generate a 24-bit pixel with red, green, and blue channels respectively. Depending on the interval output by random() you may end up with near-white (254,254,254) or white (255,255,255).
     +--------+-----+
     |random()|Byte |
     |--------|-----|
     |0.999...| 254 | <-- error introduced
     |1.0     | 255 |
     +--------+-----+

For more details about floating-point precision and robustness with intervals see Christer Ericson's Real-Time Collision Detection, Chapter 11 Numerical Robustness, Section 11.3 Robust Floating-Point Usage.

0
Mark Byers On

That's a half-open interval.

  • A closed interval [a,b] includes the end points.
  • An open interval (a,b) excludes them.

In your case the end-point at the start of the interval is included, but the end is excluded. So it means the interval "first1 <= x < last1".

Half-open intervals are useful in programming because they correspond to the common idiom for looping:

for (int i = 0; i < n; ++i) { ... } 

Here i is in the range [0, n).

0
Eddy On

It can be a mathematical convention in the definition of an interval where square brackets mean "extremal inclusive" and round brackets "extremal exclusive".