Floor, ceiling, bracket

Mathematics notation changes slowly over time, generally for the better. I can’t think of an instance that I think was a step backward.

Gauss introduced the notation [x] for the greatest integer less than or equal to x in 1808. The notation was standard until relatively recently, though some authors used the same notation to mean the integer part of x. The two definitions agree if x is positive, but not if x is negative.

Not only is there an ambiguity between the two meanings of [x], it’s not immediately obvious that there is an ambiguity since we naturally think first of positive numbers. This leads to latent errors, such as software that works fine until the first person gives something a negative input.

In 1962 Kenneth Iverson introduced the notation ⌊x⌋ (“floor of x“) and ⌈x⌉ (“ceiling of x“) in his book A Programming Language, the book that introduced APL. According to Concrete Mathematics, Iverson

found that typesetters could handle the symbols by shaving off the tops and bottoms of ‘[‘ and ‘]’.

This slight modification of the existing notation made things much clearer. The notation [x] is not mnemonic, but clearly ⌊x⌋ means to move down and ⌈x⌉ means to move up.

Before Iverson introduced his ceiling function, there wasn’t a standard notation for the smallest integer greater than or equal to x. If you did need to refer to what we now call the ceiling function, it was awkward to do so. And if there was a symmetry in some operation between rounding down and rounding up, the symmetry was obscured by asymmetric notation.

My impression is that ⌊x⌋ became more common than [x] somewhere around 1990, maybe earlier in computer science and later in mathematics.

Iverson and APL

Iverson’s introduction of the floor and ceiling functions was brilliant. The notation is mnemonic, and it filled what in retrospect was a gaping hole. In hindsight, it’s obvious that if you have a notation for what we now call floor, you should also have a notation for what we now call ceiling.

Iverson also introduced the indicator function notation, putting a Boolean expression in brackets to denote the function that is 1 when the expression is true and 0 when the expression is false. Like his floor and ceiling notation, the indicator function notation is brilliant. I give an example of this notation in action here.

I had a small consulting project once where my main contribution was to introduce indicator function notation. That simple change in notation made it clear how to untangle a complicated calculation.

Since two of Iverson’s notations were so simple and useful, might there be more? He introduced a lot of new notations in his programming language APL, and so it makes sense to mine APL for more notations that might be useful. But at least in my experience, that hasn’t paid off.

I’ve tried to read Iverson’s lecture Notation as a Tool of Thought several times, and every time I’ve given up in frustration. Judging by which notations have been widely adopted, the consensus seems to be that the floor, ceiling, and indicator function notations were the only ones worth stealing from APL.

15 thoughts on “Floor, ceiling, bracket

  1. There is a slight ambiguity in “the smallest integer”: At first, I read that as meaning smallest-magnitude (truncate towards zero), but the usual convention for the floor function is least-positive (truncate towards minus infinity).

    One might generalize the square-bracket notation by affixing negative infinity, zero, or positive infinity to the brackets, indicating truncation to the nearest integer in the direction of that value. Similar notations for rounding, rather than truncation, could follow. I don’t know that anyone does that, though.

  2. I attended a talk by Iverson once, and he explained that one of the advantages of APL was that it was readable. I guess it’s a subjective thing…. :)

  3. And now you can write the most beautiful equation in mathematics, ⌈e⌉ = ⌊π⌋.

    (I don’t remember where I heard this one.)

  4. There is some APL legacy living on in function naming, if not in the notation/symbols. I’m talking about `iota` for range generation (IIRC Go and C++ have that) and `reduce` (many functional programming languages have that).

  5. Feynman once wrote about having invented new symbols for trigonometric functions. He wasn’t happy with seeing the letters “s i n” smashed together, as if they were variables to be multiplied.

    IIRC, his symbols had a long tail over the top (like square roots), and at the left side it turned into the shape of the letter “S”/”C”/”T”. I don’t remember what the inverses or hyperbolics were.

    I can’t point to any specific case where notation made a step backwards, but it certainly has made many steps to the side. Notation often seems to change for no apparent reason other than fashion. Newton’s notation isn’t any worse than Lagrange’s, IMHO, but I haven’t seen it used in any books in the past 50 years. Fortunately, calculus is still not lacking for redundant notations.

    And of course physicists make up their own notation just for fun all the time. Which probably explains Feynman!

  6. Ah, APL, my first programming language (maybe that’s my problem :-), back in 1971 (yikes! 50 years ago).

    I was obsessed with concatenating functions together, so that the only required leftmost operator on any line was a go-to (right arrow). I seem to recall that the concatenation operator is: x0i (multiply zero iota). This allowed a lot of functionality with minimal lines of code.

    I was proud to write an unbeatable tic-tac-toe program in 28 lines of code (including I/O). Back then I could read it like a cheap novel. I just now looked again, and it’s totally alphabet soup (with a lot of funny looking noodles :-).

  7. Just to be clear, Iverson didn’t invent the concept of the indicator function, or the idea of using a concise notation for it. Wikipedia has an example from the 1930s, and I’ve seen plenty of mathematics books use them which, while admittedly later than APL, I highly doubt trace their roots back to that.

    I can believe that he invented the invented that particular notation. Unlike the floor and ceiling notations (which I agree are a big improvement on what came before), I’m afraid that indicator function notation is a lot worse than the standard mathematical notation in my opinion. Having the Boolean condition at full height gives the wrong visual weight to something that isn’t directly used as a value in the expression. The more common notation is χ (Greek letter chi) or boldface numeral 1, with the condition in a subscript. This works a lot better, and fingers crossed that it remains more common than Iverson’s.

  8. Hey, David W. I remember telling John Cook once that my dad taught me APL as my first programming language in the early 70s, and his immediate reaction was, “That’s child abuse!” I later told my dad, and he laughed so hard. But I do remember how elegantly mathematical APL was and thinking as I learned other languages later how clumsy it was to write out functions as WORDS instead of concise symbols and how you had to laboriously write out loops to calculate element by element across data. What I could do in one very concise line of APL code took a big, chunky block of code in other languages.

    I don’t remember x0ι. It’s been so long now. I think I remember xι (times iota) after a goto expression in APL, which basically meant “if”. I also remember trying to avoid goto and loops, since that’s what the language was designed to do internally.

    My big project was designing a Mastermind game, but I don’t have any of my old code anymore!

  9. I like the idea of a bigger symbolic vocabulary in principle. And I don’t think it’s too much of a strike against a language if it looks unfamiliar to people who don’t use it; easy of getting started is nice, but it’s not everything. You usually spend a whole lot more time using a language than learning it.

    In practice, software is still almost exclusively ASCII text. Experiments to store code in binary formats or to introduce non-ASCII symbols haven’t worked out so well, or at least have not been widely adopted.

  10. > My impression is that ⌊x⌋ became more common than [x] somewhere around 1990, maybe earlier in computer science and later in mathematics.

    I wonder how significant the 1989 publication of the book *Concrete Mathematics* by Graham, Knuth, and Patashnik was. This book enthusiastically promoted this ⌊x⌋ and ⌈x⌉ notation, with an entire chapter mostly about floors and ceilings. This book started as lecture notes for a course based on the first section (“Mathematical Preliminaries”) of Knuth’s The Art of Computer Programming, and even its first (1968) edition used this ⌊x⌋ and ⌈x⌉ notation crediting Iverson (1962).

    As for the indicator function notation, those are also used heavily in the book, and Knuth later wrote a paper called “Two Notes on Notation” (https://arxiv.org/abs/math/9205211), the first half of which extols the indicator function notation. It appears that using square brackets rather than parentheses was an innovation of (the second printing of) this book. Incidentally (related to the comment above by Jim Q), the paper says that both Knuth’s and Adriano Garsia’s usage of the indicator function trace back to Iverson (and says other mathematicians followed Garsia), and the example given on the Wikipedia article “Iverson bracket” from the 1830s (not 1930s) seems to be more historical research from Knuth’s paper (showing there was “craving” for this notation) than anything directly influential. So it seems not inconceivable that mathematical usage of indicator function notation indeed traces back in a large way to Iverson.

    Also, the manipulations in the CM book serve (IMO) as a convincing argument for putting the boolean condition at normal height and not in subscripts or superscripts (for one thing, we may want to use them in superscripts, see e.g. the equation following (1.15) in the paper).

    The CM book also introduced/popularized a lot of elegant notation, only some of which has caught on: falling factorial / rising factorial powers (instead of the “Pochhammer symbol”), the notation and terminology for “Stirling cycle numbers” and “Stirling subset numbers”, two dots for intervals — writing (a..b) instead of the overused (a, b) — and “m⊥n” for gcd(m,n)=1.

    There’s a (poor-quality, unfortunately) video of a Knuth talk from 2003 on Notation, where he discusses all this: https://www.youtube.com/watch?v=KjbuyB4dQa0

  11. Notation Notes:
    1. The “rising power” and “falling power’, which I think are due to Knuth, are useful (particularly if mucking about with hypergeometric functions) and should be more widely known and used.

    2. In discussing how many ways you can choose k things from a population of n, two issues arise: Does order matter, and, are repetitions allowed, giving four possibilities.
    For typesetting simplicity, I will write the standard combinatoric functions “combinations” and “permutations” as C(n,k) and P(n,k). When I teach this stuff, I also use S(n,k) (Strings) for “order matters, reps allowed”, and R(n,k) for order does not matter, reps allowed. Then you can put all four in a 2×2 chart and derive the mathematical formulas for the four functions.

  12. @Ralph: I agree that the rising and falling powers notation is handy. It’s symmetric and mnemonic, like floor and ceiling, while some of its alternatives are not.

    Some books use (a) for falling powers. Is there any symbol more overloaded than parentheses? And what would the opposite of parentheses be if you wanted a notation for rising powers. (Or maybe the books use (a) for rising powers. I can’t remember. Which is kinda the point.)

    I like the C(n,k) notation for convenience, but I hesitate to use it because I’m not sure how many readers would understand it. It’s tedious to have to create a displayed equation rather than inline text just to display a binomial coefficient.

  13. Notation issue that bugs me.
    I will write the LE operator as <= for simplicity.

    (start of rant)
    The <= operation is central in math. If we go up to vectors a,b, everyone knows what a <= b means. So obviously with matrices A,B, A <= B means "element wise" = 0 to mean that A is nonnegative definite, when they could just say “A is p.d.”, or use the LaTeX prec operator. In some applications, both meanings are in play at the same time.

    As far as I am concerned, this is just wrong.

    Now consider bumping math operations up to sets and particularly intervals and boxes. For intervals, [a,b] + [c,d] is well understood as “element-wise +”, as started by Minkowski, and the same should be the case for all operators.
    What about [a,b] <= [c,d] ? The Minkowski interpretation would be that this is true iff b <= c. However, many Interval Analysis works define it to be "a <= c AND b <= d". While this is a useful concept (as are many other types of <=), it should not be expressed as <=, which has an obvious meaning.
    (end of rant)

  14. above comment garbled my “A greater than or equal to 0”. Kindly fix that if you can.

Leave a Reply

Your email address will not be published.