For any real , put . Since is integer-valued,
Continuity of the cumulative distribution function of therefore gives
The strict inequality matters before using the absence of point masses. The resulting probability distribution is discrete, with probability mass function
Thus has no ordinary probability density function with respect to length on the real line. Its cumulative distribution function is a step function; its derivative is zero almost everywhere and does not recover its probabilities. The floor function has converted a density into masses on the integers.
Because , exponentiation to base is strictly increasing. The definition of the floor function gives , so the equivalent characterization of the integer logarithm is
Here is a nonnegative integer; gives .
Let contain the multiples of among . Its cardinality is , using the floor function. Because are pairwise coprime, their pairwise intersections correspond to divisibility by , and their triple intersection to divisibility by . The inclusion-exclusion principle gives
The floor function is constant at on the four consecutive integers . Consequently the partition of a set is . Different blocks are disjoint and every nonnegative integer has exactly one quotient and remainder upon division by .
The nonnegative integer-valued tail-sum formula for expectation gives
This is finite because . Here is the Riemann zeta function on its convergent real domain. The floor function is nonnegative on the support, so the tail-sum identity applies directly.
Part (a) gives . Therefore the ceiling function and floor function satisfy almost surely. Both are integrable, since and . Thus .
Now take expectations in :
Writing , which ranges over every , and rearranging yields
These are the zeta bounds from rounded Pareto variables: rounding below and above converts one elementary expected value into bounds on an infinite series.
Phase folding of a light curve maps timestamps onto a trial cycle of duration . Given a reference time , define the phase in cycles by
where is the fractional part, using the floor function also for negative . Plot brightness against rather than ; measurements separated by an integer multiple of occupy the same phase. For a periodic function , this reveals the shared shape of many cycles. Folding changes coordinates; it neither averages samples nor chooses the correct by itself. Welsh et al.'s folded Kepler plot separates the exoplanet transit and orbital brightness modulation. [ref].
The second figure uses a completely synthetic trapezoidal dip: days, day, and the same depth and four-hour duration as the first figure. Different colours identify four successive cycles. Correct folding superimposes the dips; a wrong trial orbital period spreads them out. If , the centre of the th repeated event shifts by approximately cycles when folded on , for . With days, the fourth plotted event is displaced by cycles. Transit-timing variations can also smear a constant-period fold, so retain the original timestamps and inspect individual events.
Figure 1.
Toy phase folding: repeated synthetic dips align at the correct period; a flux dip becomes a positive magnitude change
. Details.
One may combine nearby phases with a weighted mean, but the uncertainty reduction requires assumptions. For independent measurements with common standard deviation and effectively the same expected brightness within the bin, their arithmetic mean has standard deviation . Thus sixteen independent -precision samples give precision on that phase-bin mean. Shared calibration errors, changing starspots, and bins wide enough to mix ingress with out-of-transit brightness violate these assumptions. A folded plot can conceal changes between cycles. Gaussian process models can represent correlated variability and interpolate irregular samples, but their predictions and uncertainties depend on their assumed covariance function.
The bottom panels show the same model as relative brightness and as magnitude difference in one fixed photometric passband with a fixed magnitude zero point:
A dip to gives magnitudes: fainter means a larger apparent magnitude. The figure places larger magnitude differences lower on the page so the two dip shapes are easy to compare; reversing that plotting convention does not change the formula. For and small , expansion of the logarithm gives . The exact transform is nonlinear: transforming an exposure's mean brightness is generally different from averaging its instantaneous apparent magnitudes. The ordinary logarithm cannot be applied to a nonpositive background-subtracted measurement; keep such measurements and their uncertainties in brightness units for an appropriate statistical model.
Pointwise convergence Created 2026-09-24 Updated 2026-10-14
For a sequence of functions , pointwise convergence to a function means
It is the ordinary limit of a sequence at each fixed input. The threshold may depend on the input. Uniform convergence instead requires one threshold for the entire domain of a function.[ref]
Consider the polynomial functions , for positive integers , on the interval . For the geometric sequence tends to zero, while . Thus
Each is a continuous function, but its pointwise limit is discontinuous at one. Holding an input still hides what happens near that endpoint. The analogous even-power example on appears in the source.[ref]
For and , taking the logarithm of and dividing by the negative real number reverses the inequality:
The floor function followed by adding one handles the strict inequality even when the ratio is an integer. For tolerance , the first successful indices at , , and are respectively , , and . At , fails and succeeds. At and , the error from this pointwise limit is already zero, so works. Nevertheless, grows without bound as from below. A finite list of accurate test inputs cannot establish uniform convergence.
Figure 1.
Pointwise convergence of powers changes character when the domain of a function stops before one
. On the pointwise limit is zero except for its value one at the endpoint: the open circle and filled circle distinguish these values. On the pointwise limit is zero everywhere, and the largest error is . All curves are original evaluations of . Details.
An even sharper warning concerns integration. On , define the continuous functions
Their supports are , with height at and value zero at both ends. Every fixed eventually lies beyond the support, and always, so pointwise convergence gives the zero function. Nevertheless, each integral is the area of a triangle: . Shrinking width compensates increasing height. Hence the limit of a sequence of these integrals differs from the integral of the pointwise limit; interchanging them requires additional conditions, such as uniform convergence preserves integrals on a compact interval.
Reduction modulo one Created 2026-10-31 Updated 2026-11-05
For a real number , its reduction modulo one is its fractional part
The floor function is used, including at negative inputs: . Truncating toward zero would instead give , outside the required interval.
Figure 1.
The fractional part lies in even for negative numbers
. Filled points at integers have value zero; open points show the excluded limiting value one. The highlighted point is , whose fractional part is . Details.
Two real numbers have the same fractional part exactly when their difference is an integer. Thus reduction chooses representatives for the quotient group , the circle group. Applied to two coordinates, it selects representatives in for a torus, obtained from a closed unit square by identifying opposite edges.
The rounded Bernstein polynomial replaces each coefficient in the unnormalized basis by its floor function. It therefore has integer coefficients in the ordinary monomial basis. If , only interior rounding errors remain and
To prove this, bound each interior rounding error by one. On , sum the resulting powers as a geometric series of ratio at most and maximize ; reflect for . On the middle interval each degree- product is at most . integer endpoints are necessary for this convergence: a noninteger endpoint produces a fixed nonzero rounding error there.
Sample depth Created 2026-10-14 Updated 2026-11-05
The sample depth is the number of bits allocated to one stored sample. An unsigned -bit integer has codes, . This is per component, not automatically per pixel: three eight-bit components require 24 payload bits per pixel. A raster image with pixels and such components requires payload bits before data compression, padding or a file header.
For a toy normalized shade , define uniform quantization with endpoints included by
The floor function implements rounding to the nearest code, with exact halves rounded upward. The reconstruction step is , and . For , the levels are ; for they are . Increasing sample depth refines this value grid without changing the spatial grid. These levels are uniform in ; if is encoded sRGB, they are not uniform in relative luminance.
PNG uses a bit-depth field per sample or palette index. Its grayscale type without alpha permits 1, 2, 4, 8 or 16 bits per sample; its truecolour type permits 8 or 16 bits per component. These are format-specific restrictions, not a rule for every raster image.[ref]
Let the numerical support of a probability distribution be . Its cumulative distribution function counts how many values have been passed:
It is zero below , equals on for , and is one at and above . Every jump is , even when the horizontal gaps differ.
For inverse transform sampling, take an ideal continuous uniform distribution for on . Partition that interval into intervals of width and output
Each interval has probability , proving the desired discrete uniform distribution. Using the floor function, the index is ; for consecutive integer values the output is . With the usual quantile function convention , one instead writes for , using the ceiling function. The endpoint conventions differ only at a finite set of points with probability zero under the ideal continuous uniform distribution.
For , the four intervals , , , and select , respectively. Thus selects , while selects . The upper half of the interval selects values at least four, recovering probability . Equal widths refer to the sampling probability coordinate, not to distances between output values. This is an exact mathematical construction assuming an ideal continuous uniform distribution; a finite computer random-number source needs its own justification of equal output chances.
Spatial locality 2026-10-13
Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.
Consider a array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row and column , with , the address and cache block number are
Here is the floor function. Each row occupies exactly one cache line: row zero begins at addresses , row one at , and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.
Figure 1.
Two traversal paths through the same row-major array, coloured by physical cache line
. Details.
Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.
Figure 2.
All sixteen memory references and their cache hits or cache misses with capacity one cache line
. Details.
Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.
This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. [ref]
// Destination: computer-science.bigb
Squarefree counting function Created 2026-10-20 Updated 2026-11-05
For a nonnegative real number , the squarefree counting function counts positive square-free integers:
For example, , counting . The Möbius function gives the exact formula
To see why, consider . Only square-free integers contribute. Choosing their prime factors from the primes whose squares divide gives the product . This is one when there are no such prime factors and zero otherwise, so it is the indicator function of squarefreeness. Summing over the positive integers and exchanging two finite sums leaves multiples of each . The floor function makes the formula exact for nonintegral too.
A rigid body's axial moment of inertia and a constant resisting torque give constant angular acceleration . Hence and the angular displacement is the displayed expression. Equivalently, the lost rotational kinetic energy equals the resisting work . The total number of revolutions is ; the number of whole revolutions completed is its floor function.
For , consider on . On each negative branch of the tangent, the left side increases strictly, while the right side decreases strictly. A unique intersection exists precisely when the branch starts at , since the difference increases from negative infinity to a positive value or positive infinity. Consequently the number of trapped normal modes is . The floor function expression agrees except at , where it counts an inadmissible cutoff state with zero exterior exponential decay rate.
Truncation toward zero 2026-10-14
Truncation toward zero removes the fractional magnitude of a real number, giving the integer obtained by applying the floor function to its absolute value and restoring the original sign; a magnitude below one gives zero. More precisely,
The result is zero for . For example, and , whereas . Python's math.trunc uses this towards-zero convention, so replacing it by math.floor changes calculations with negative noninteger inputs. [ref].
Figure 1.
Truncation toward zero is symmetric in sign, while the fractional part defined by the floor function is always nonnegative
. Left: exact integer endpoint values distinguish the two sign-dependent truncation rules; a whole neighborhood of zero maps to zero. Right: takes the sign of a noninteger input, while lies in on both sides of zero. Open endpoints show excluded limiting values. Details.
For every real number ,
The discarded difference has the sign of when is noninteger. In contrast, the fractional part is always in . At , these two differences are and . Thus specifying a signed fractional remainder requires specifying which integer-valued operation is used.
Unlike the floor function and ceiling function, truncation toward zero need not commute with adding an integer. At and , , whereas . This matters if negative coordinates are assigned to equal-width bins by converting a quotient to an integer: belongs to the bin under the floor function, but truncation gives zero. The appropriate operation follows from the declared bin intervals.
Truncation toward zero is a nondecreasing function with a discontinuity of a function at each nonzero integer. It has no discontinuity of a function at zero, because it is identically zero on . Its agreement with the floor function on the positive side and the ceiling function on the negative side explains the different closed endpoints in the diagram.
Turán graph Created 2026-09-29 Updated 2026-10-14
The Turán graph is a complete multipartite graph with independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when .[ref]
Figure 1.
The Turán graph has three independent sets of sizes , giving edges and no four-vertex clique
. Details.
In this example, the independent sets are , and . Count the edges between each pair of parts:
Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form . Conversely, every choice of one vertex from each part is a triangle in a graph, giving triangles in a graph. Clique exclusion here does not mean triangle-free.
For the exact count, Euclidean division writes , where uses the floor function and is the remainder, with . There are parts of size and of size . For any part sizes summing to , count cross edges by expanding the square:
Therefore
For , we have , giving . The Quadratic Turan edge bound gives instead: the exact correction subtracts .
Balancing is an integer optimization with a simple reason. If two part sizes satisfy , moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares by
so it increases the edge count by . For eight vertices, parts give edges; moving one vertex produces and edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.
Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.
For a virtual address , extract the root index , lower-level index , and offset by Euclidean division:
Here is the floor function and denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into , , and ; its binary numeral system representation is 0001 | 0010 | 00110100.
Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:
RecordPhysical address of recordReference held in the page table entryPresence and permissions
Root entry 10x8000 + 1*4 = 0x8004Lower-level table at 0x9000Present; user; read/write; no execute
Lower-level entry 20x9000 + 2*4 = 0x9008Data page frame 0x07, base 0x0700Present; user; read-only; no execute
The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:
The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.
Figure 1.
The model's 4+4+8-bit address split and complete read translation from 0x1234 to 0x0734
. Details.
Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.
With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. [ref]