how does a floor function work?

Question

I understand what a floor function does, and got a few explanations here, but none of them had a explanation, which is what i'm after.

Can someone explain to me what is going on behind the scenes of a floor function?

Edit: To clarify, what i want to know, is when i use floor(x), what is the computer actually doing to give me the result of the largest integer below x. For example,someone responded in the linked thread,

$$\left\lfloor \frac{x}{2} \right\rfloor = \frac{x}{2} - \frac{1 - (-1)^x}{4} $$

However, there was no explanation. So, what i really am after is a method of solving floor() mathematically, with an explanation/proof

Answer 1

I'm answering a question which I suspect was meant to be asked. Suppose $p$ and $q$ are integers. Floor division $\lfloor p/q\rfloor$ is an operation which is associated with the modulo operator $p\mathbin{\mathrm{mod}}q$, at least when modulo is defined as the remainder in the division algorithm (the Euclidean division theorem). That is, they are related by $$p=q\lfloor p/q\rfloor+(p\mathbin{\mathrm{mod}}q)$$ where $0\leq p\mathbin{\mathrm{mod}}q<q$.

Computationally, an efficient way to compute $\lfloor p/q\rfloor$ is to do something like long division, then ignore the remainder. Because of this, digital computers have an instruction which produces both values simultaneously (if it has a built-in divider at all -- otherwise one can implement long division in software).

However, digital computers tend to use a different division convention, which is to round $p/q$ toward $0$, which explains why modulo on a computer gives different values from expected when $p/q$ is negative.

You can take advantage of the division algorithm to get the identity $\lfloor x/2\rfloor=x/2-(1-(-1)^x)/4$ (when $x$ is an integer, of course). We have $x=2\lfloor x/2\rfloor+(x\mathbin{\mathrm{mod}}2)$ by division, and one can prove $x \mathbin{\mathrm{mod}}2=(1-(-1)^x)/2$ (if $x$ is even, then $(-1)^x=1$ so the expression evaluates to $0$, and if $x$ is odd, then $(-1)^x=-1$, so the expression evaluates to $1$). Then simply solve for $\lfloor x/2\rfloor$.

Answer 2

The floor of a real number is just the largest integer that is smaller than or equal to the number. That is, given $x$ the floor $\lfloor x \rfloor$ is given by $$ \lfloor x \rfloor := \max\{z\in \mathbb{Z} \mid z \leq x\}. $$

Some examples: $\lfloor 10.9 \rfloor=10$, $\lfloor \pi \rfloor=3$, $\lfloor -5.1 \rfloor=-6$, $\lfloor 29 \rfloor=29$

Edit: The clarified question is more suited towards stack overflow. In fact, here's a similar one: https://stackoverflow.com/questions/5122993/floor-int-function-implementaton

Answer 3

The floor function takes in a real number $x$ (like 6.81) and returns the largest integer less than $x$ (like 6).

Such a function is useful when you are dealing with quantities that can't be split up. For example, if a snack costs \$1.50, and you have \$10.00, you want to know how many snacks you can buy. \$10.00/\$1.50 is around 6.66. Because you presumably can't buy a fraction of a snack, in this application you can buy exactly 6 snacks, no more.

You compute the floor of the division instead, to account for the fact that you can't buy a part of a snack: $$\left\lfloor \frac{\$10.00}{\$1.50} \right\rfloor = 6.$$

Answer 4

This is better suited for the programming forums but....

Your computer program is probably working with a binary representation of a number. To compute the floor function, the computer does exactly the same thing you do: e.g. if it holds a representation of the positive binary numeral

$$ 100110.01011101 $$

then it simply replaces every digit to the right of the point with a zero:

$$ 100110.00000000 $$

The processor your program runs on likely has assembly language instructions for performing this exact operation when a number is stored in a register in IEEE 724 format (which is almost always used to store floating-point numbers).

Answer 5

if you are asking about what the computer does it is like this: you have the variable $x$

$\lfloor x\rfloor=max\{m\in\mathbb{Z}~|~m\le x\}$

which means that out off all the integers that beneath $x$ take the largest.

now the computer doesn't has the function $\in$ or the group $\mathbb{Z}$ or any of those stuff so he do it differently, the computer save memory with $0$'s and $1$'s, bits, integer he saves with 32-bits(usually)

for understanding with 8-bits it looks like this:

$1111~1111$bits$=-127$

$1000~0000$bits$=1$

$0111~1111$bits$=0$

now for float he has a different method, 32-bit format looks like this:

$\underbrace{0}_{0=positive\\1=negative}\underbrace{00000000}_{the~exponent }~~\underbrace{00000000000000000000000}_{the~fraction~part}$

now how exactly this format works is not important now, but you can see from this format that if you have the float, for example, $0~~10000000~11000000000000000000000(=3.5)$ the computer can just ignore the last 22 bits and take only $0~~10000000~1$, the computer can extract all he needs from the first 10 bits if you do interested in how the float itself works:

the computer look at the first bit and put it in var name AXL(for this example) and do $AX=(-1)^{AXL}$ now he takes the last part and do $DX=1+\text{[the bit]}^\text{[the bit position]}+\text{[the bit]}^\text{[the bit position]}+...$

and the end result is:

$AX\times (DX\times 2^{\text{[the middle part value]}})$

now because that every part after the 10th bit is quarter or less you don't need them when you use floor