1
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ You might want to clarify that you are not asking an entirely mathematical question, but, rather, that it also involves (as I see from your link) implementation issues in computing situations. Otherwise you'll have people telling you the definition, which I gather is not what you want. $\endgroup$ Aug 18, 2017 at 0:14
  • 1
    $\begingroup$ There is nothing going on behind the scenes. Can you describe better what aspect of the floor function you want to see explained in more detail, or what aspect of the floor function you are having difficulty with? $\endgroup$
    – user14972
    Aug 18, 2017 at 0:18
  • $\begingroup$ Right, i just want an explanation on how the floor function calculates the largest integer less than x. I already know what it is, and how to use it. $\endgroup$
    – eshanrh
    Aug 18, 2017 at 0:19
  • $\begingroup$ For positive numbers, the floor of $x$ is the digits place. For example,$$\lfloor\pi\rfloor=\lfloor\color{red}3.1415926\dots\rfloor=3$$Something like that? $\endgroup$ Aug 18, 2017 at 0:20
  • 2
    $\begingroup$ The given "formula with no explanation" only holds for integer values of $x$, and can be seen by considering even and odd cases. $\endgroup$ Aug 18, 2017 at 0:27

5 Answers 5

3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ I think "simply" isn't quite the right word, maybe "effectively." IEEE 754 format (in normal form) stores numbers as $\pm 1.bbb...bb \times 2^n$, so to compute the floor it would first need to figure out where the decimal place is, and then replaces the corresponding digits (if any) to 0, and if the result would be 0, then the format switches to denormalized form. The floor of a denormalized floating point number is easier because the floor is $0$ or $-1$, depending on the sign. One thing that is interesting about this is that if $n>0$ is big enough, there are no representable non-integers. $\endgroup$ Aug 18, 2017 at 1:13
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I want to say that this is the way assembly(the most basic programing language) can do it, there are languages that each one do it differently $\endgroup$
    – ℋolo
    Aug 18, 2017 at 1:35
  • $\begingroup$ Maybe specify "the integer" is the biased exponent? Otherwise it seems you are talking about the integer part of a number. Also, while that is 3.5 as an IEEE754 floating point number, using your binary encoding for "the integer" it is not the correct exponent. (01111111 is 0 and 10000000 is 1.) What is special about 12 bits? With that exponent, isn't floor determined by the first 10? $\endgroup$ Aug 18, 2017 at 1:47
  • $\begingroup$ @KyleMiller i changed the exponent part to be more clear and changed my encoding to IEEE754 floating point, thanks for saying that. About the 12, i thought about what you need for the float number and made a stupid mistake, you are right $\endgroup$
    – ℋolo
    Aug 18, 2017 at 3:14
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.$$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yes, the first answer was exactly what i was looking for. Thanks! $\endgroup$
    – eshanrh
    Aug 18, 2017 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.