In mathematics and computer science, the floor and ceiling functions map a real number to
the largest previous or the smallest following integer, respectively. More precisely, floor(x)
= is the largest integer not greater than x and ceiling(x) = is the smallest integer
not less than x.
Notation Carl Friedrich Gauss introduced the square
bracket notation for the floor function in his third proof of quadratic reciprocity.
This remained the standard in mathematics until Kenneth E. Iverson introduced the names
"floor" and "ceiling" and the corresponding notations and in his 1962 book A Programming
Language. Both notations are now used in mathematics; this article follows Iverson.
The floor function is also called the greatest integer or entier function, and its value
at x is called the integral part or integer part of x; for negative values of x the latter
terms are sometimes instead taken to be the value of the ceiling function, i.e., the value
of x rounded to an integer towards 0. The language APL uses ⌊x; other computer languages
commonly use notations like entier(x), INT(x), or floor(x)(C, C++, R, and Python). In mathematics,
it can also be written with boldface or double brackets .
The ceiling function is usually denoted by ceil(x) or ceiling(x) in non-APL computer
languages that have a notation for this function. The J Programming Language, a follow on to
APL that is designed to use standard keyboard symbols, uses >. for ceiling and <. for floor.
In mathematics, there is another notation with reversed boldface or double brackets
or just using normal reversed brackets ]x[. The fractional part sawtooth function, denoted
by for real x, is defined by the formula
For all x,
Examples Typesetting
The floor and ceiling function are usually typeset with left and right square brackets
where the upper or lower horizontal bars are missing, and, e.g., in the LaTeX typesetting
system these symbols can be specified with the \lfloor, \rfloor, \lceil and \rceil commands
in math mode. HTML 4.0 uses the same names: ⌊, ⌋, ⌈, and ⌉.
Unicode contains codepoints for these symbols at U+2308–U+230B: ⌈x⌉, ⌊x⌋.
Definition and properties In the following formulas, x and y are real
numbers, k, m, and n are integers, and is the set of integers.
Floor and ceiling may be defined by the set equations
Since there is exactly one integer in a half-open interval of length one, for any real x there
are unique integers m and n satisfying
Then and may also be taken as the definition of floor and ceiling.
Equivalences These formulas can be used to simplify expressions
involving floors and ceilings.
In the language of order theory, the floor function is a residuated mapping, that is,
part of a Galois connection: it is the upper adjoint of the function that embeds the integers
into the reals.
These formulas show how adding integers to the arguments affect the functions:
The above are not necessarily true if n is not an integer; however:
Relations among the functions It is clear from the definitions that
with equality if and only if x is an integer, i.e.
In fact, since for integers n:
Negating the argument switches floor and ceiling and changes the sign:
and:
Negating the argument complements the fractional part:
The floor, ceiling, and fractional part functions are idempotent:
The result of nested floor or ceiling functions is the innermost function:
For fixed y, x mod y is idempotent:
Also, from the definitions,
Quotients If m and n are integers and n ≠ 0,
If n is positive
If m is positive
For m = 2 these imply
More generally, for positive m
The following can be used to convert floors to ceilings and vice-versa
If m and n are positive and coprime, then
Since the right-hand side is symmetrical in m and n, this implies that
More generally, if m and n are positive,
This is sometimes called a reciprocity law. Nested divisions
For positive integers m,n, and arbitrary real number x:
Continuity None of the functions discussed in this article
are continuous, but all are piecewise linear. and are piecewise constant functions, with
discontinuites at the integers. also has discontinuites at the integers, and as a function of x
for fixed y is discontinuous at multiples of y.
is upper semi-continuous and and are lower semi-continuous. x mod y is lower semicontinuous
for positive y and upper semi-continuous for negative y.
Series expansions Since none of the functions discussed in this
article are continuous, none of them have a power series expansion. Since floor and
ceiling are not periodic, they do not have uniformly convergent Fourier series expansions.
x mod y for fixed y has the Fourier series expansion
in particular {x} = x mod 1 is given by
At points of discontinuity, a Fourier series converges to a value that is the average of
its limits on the left and the right, unlike the floor, ceiling and fractional part functions:
for y fixed and x a multiple of y the Fourier series given converges to y/2, rather than
to x mod y = 0. At points of continuity the series converges to the true value.
Using the formula {x} = x − floor(x), floor(x) = x − {x} gives
Applications Mod operator
The mod operator, denoted by x mod y for real x and y, y ≠ 0, can be defined by the formula
x mod y is always between 0 and y; i.e. if y is positive,
and if y is negative,
If x is an integer and y is a positive integer,
x mod y for a fixed y is a sawtooth function. Quadratic reciprocity
Gauss's third proof of quadratic reciprocity, as modified by Eisenstein, has two basic steps.
Let p and q be distinct positive odd prime numbers, and let
First, Gauss's lemma is used to show that the Legendre symbols are given by
and
The second step is to use a geometric argument to show that
Combining these formulas gives quadratic reciprocity in the form
There are formulas that use floor to express the quadratic character of small numbers mod
odd primes p:
Rounding For an arbitrary real number , rounding to
the nearest integer with tie breaking towards negative infinity is given by .
Truncation The truncation of a nonnegative number is
given by The truncation of a nonpositive number is given by .
The truncation of any real number can be given by: , where sgn(x) is the sign function.
Number of digits The number of digits in base b of a positive
integer k is
with the right side of the equation also holding true for .
Factors of factorials Let n be a positive integer and p a positive
prime number. The exponent of the highest power of p that divides n! is given by the
formula
where is the way of writing n in base p. Note that this is a finite sum, since the floors
are zero when pk > n. Beatty sequence
The Beatty sequence shows how every positive irrational number gives rise to a partition
of the natural numbers into two sequences via the floor function.
Euler's constant There are formulas for Euler's constant γ
= 0.57721 56649 ... that involve the floor and ceiling, e.g.
and
Riemann function The fractional part function also shows up
in integral representations of the Riemann zeta function. It is straightforward to prove
that if φ(x) is any function with a continuous derivative in the closed interval [a, b],
Letting φ(n) = n−s for real part of s greater than 1 and letting a and b be integers, and
letting b approach infinity gives
This formula is valid for all s with real part greater than −1, and combined with
the Fourier expansion for {x} can be used to extend the zeta function to the entire
complex plane and to prove its functional equation.
For s = σ + i t in the critical strip,
In 1947 van der Pol used this representation to construct an analogue computer for finding
roots of the zeta function. Formulas for prime numbers
n is a prime if and only if
Let r > 1 be an integer, pn be the nth prime, and define
Then
There is a number θ = 1.3064... with the property that
are all prime. There is also a number ω = 1.9287800... with
the property that
are all prime. π(x) is the number of primes less than or
equal to x. It is a straightforward deduction from Wilson's theorem that
Also, if n ≥ 2,
None of the formulas in this section is of any practical use.
Solved problem Ramanujan submitted this problem to the Journal
of the Indian Mathematical Society. If n is a positive integer, prove that
(i) (ii)
(iii) Unsolved problem
The study of Waring's problem has led to an unsolved problem:
Are there any positive integers k, k ≥ 6, such that
Mahler has proved there can only be a finite number of such k; none are known.
Computer implementations
Many programming languages provide standard functions for floor and ceiling.
Spreadsheet software Most spreadsheet programs support some form
of a ceiling function. Although the details differ between programs, most implementations
support a second parameter—a multiple of which the given number is to be rounded to.
For example, ceiling(2, 3) rounds 2 up to the nearest multiple of 3, giving 3. The definition
of what "round up" means, however, differs from program to program.
Until Excel 2010, Microsoft Excel's ceiling function was incorrect for negative arguments;
ceiling(-4.5) was -5. . This has followed through to the Office Open XML file format.
The correct ceiling function can be implemented using "-INT(-value)". Excel 2010 now follows
the standard definition. The OpenDocument file format, as used by OpenOffice.org
and others, follows the mathematical definition of ceiling for its ceiling function, with
an optional parameter for Excel compatibility. For example, CEILING(-4.5) returns −4.
See also Nearest integer function
Step function Notes
References J.W.S. Cassels, An introduction to Diophantine
approximation, Cambridge Tracts in Mathematics and Mathematical Physics 45, Cambridge University
Press Crandall, Richard; Pomerance, Carl, Prime
Numbers: A Computational Perspective, New York: Springer, ISBN 0-387-94777-9
Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, Concrete Mathematics, Reading Ma.: Addison-Wesley,
ISBN 0-201-55802-5 Hardy, G. H.; Wright, E. M., An Introduction
to the Theory of Numbers, Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Nicholas J. Higham, Handbook of writing for the mathematical sciences, SIAM. ISBN 0-89871-420-6,
p. 25 ISO/IEC. ISO/IEC 9899::1999(E): Programming
languages — C, 1999; Section 6.3.1.4, p. 43. Iverson, Kenneth E., A Programming Language,
Wiley Lemmermeyer, Franz, Reciprocity Laws: from
Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4 Ramanujan, Srinivasa, Collected Papers, Providence
RI: AMS / Chelsea, ISBN 978-0-8218-2076-6 Ribenboim, Paulo, The New Book of Prime Number
Records, New York: Springer, ISBN 0-387-94457-5 Michael Sullivan. Precalculus, 8th edition,
p. 86 Titchmarsh, Edward Charles; Heath-Brown, David
Rodney, The Theory of the Riemann Zeta-function, Oxford: Oxford U. P., ISBN 0-19-853369-1
External links Hazewinkel, Michiel, ed., "Floor function",
Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 Štefan Porubský, "Integer rounding functions",
Interactive Information Portal for Algorithmic Mathematics, Institute of Computer Science
of the Czech Academy of Sciences, Prague, Czech Republic, retrieved 24 October 2008
Weisstein, Eric W., "Floor Function", MathWorld. Weisstein, Eric W., "Ceiling Function", MathWorld.