46
$\begingroup$

I'm using a "programming language" that only allows basic operations: addition, subtraction, multiplication, and division.

Is it possible to emulate a floor function (i.e. drop the decimals a number) by using only those operators? I'm only interested in positive numbers

Edit: Here's the documentation describing what's possible (which is only elementary arithmetic)

$\endgroup$
  • 19
    $\begingroup$ Many programming languages will automatically floor when you divide two integers. $\endgroup$ – Arthur Dec 2 '14 at 11:48
  • 4
    $\begingroup$ You can't make comparisons in the program, can you? $\endgroup$ – Raskolnikov Dec 2 '14 at 12:13
  • 1
    $\begingroup$ By the way, another reference: w3.org/TR/css3-values/#calc-notation $\endgroup$ – Jean-Claude Arbaut Dec 2 '14 at 12:16
  • 2
    $\begingroup$ A bit roundabout, perhaps, but can you convert the type to a string? Then you'd be able to rip out the decimals with string operations and convert it back. $\endgroup$ – StephenTG Dec 2 '14 at 15:21
  • 2
    $\begingroup$ You might want to look into LESS (lesscss.org), a CSS preprocessor which has floor, ceil and many more besides. $\endgroup$ – Dancrumb Dec 2 '14 at 15:54

10 Answers 10

46
$\begingroup$

Let $$f_1(x)=x+c_1$$ $$f_2(x)=x\cdot c_2$$ where $c_1,c_2$ are some constants, and $f_1$ represents addition and subtraction, and $f_2$ represents multiplication and division. Functions $f_1$ and $f_2$ have inverse function, but $\lfloor{x}\rfloor$ does not have an inverse function. So, if we assume it is possible to find $\lfloor{x}\rfloor$ from $x$ using $f_1$ and $f_2$, then it is possible to find $x$ from $\lfloor{x}\rfloor$. Contradiction.

$\endgroup$
  • 3
    $\begingroup$ Which means it's impossible, I suppose. I will start lobbying for a floor function, then! $\endgroup$ – bfred.it Dec 2 '14 at 11:55
  • 34
    $\begingroup$ If both possitive and negative numbers are supported, a map such as $x \mapsto x \cdot x$ is not invertible (and not constant either). So we can produces maps that are not invertible, in that case. Your $f_1$ and $f_2$ are functions of one variable, whereas addition and multiplications are functions of two variables. $\endgroup$ – Jeppe Stig Nielsen Dec 2 '14 at 13:06
  • 5
    $\begingroup$ Of course, even if we only have positive numbers, some polynomials are still not invertible. For example let $g(x) = (x \cdot x) + 5 - (4 \cdot x)$, then $g(1)=g(3)$. $\endgroup$ – Jeppe Stig Nielsen Dec 2 '14 at 13:13
  • 6
    $\begingroup$ Replace invertible by continuous then. $\endgroup$ – Sean D Dec 2 '14 at 21:22
  • 6
    $\begingroup$ -1, I do not think this argument is correct. And regardless of whether it is correct or not, we need to demand more rigor from answers on a math site. For one thing, the link does not specify that one of the arguments in addition must be a <number>, so your part about $f_1$ is just wrong. For another thing, I think you have the wrong understanding of <number>; the correct meaning of <number> is pointed out by user2357112. $\endgroup$ – 6005 Dec 3 '14 at 21:03
42
$\begingroup$

The floor function has jump discontinuities.

A function obtained with elementary arithmetic is a rational function and those can only have pole (or infinite) discontinuities.

$\endgroup$
  • $\begingroup$ But actual arithmetic implementations also have discontinuities. $\endgroup$ – Ben Voigt Dec 2 '14 at 17:18
  • 5
    $\begingroup$ @BenVoigt Then the specification is wrong, which talks specifically about "Addition", "Subtraction", "Multiplication", "Division". Even in the presence of rounding errors, the precision is not specified. $\endgroup$ – Hagen von Eitzen Dec 2 '14 at 19:00
26
$\begingroup$

Yes it is possible, but depends on the available arithmetic and the rounding mode. With IEEE-double you can round a double $x$ to the nearest integer with this:

$c=2^{52};$

$x = x + c; \mathrm{round} = x - c$ for $x\ge 0\;$ and

$x = x - c; \mathrm{round} = x + c$ for $x<0.$

With the rounding to the next integer you can implement floor.

$\endgroup$
  • 6
    $\begingroup$ Just a warning for the OP: the precision in CSS (for which this question is asked) is theoretically infinite, in which case this answer would be meaningless, but in practice numbers are supposed to have "reasonably useful ranges and precisions", which will vary across implementations, even across different versions of the same browser. $\endgroup$ – hvd Dec 2 '14 at 12:31
  • 2
    $\begingroup$ You are onto something as calc(2.9999px + 9007199254740992px - 9007199254740992px) actually produces 2px in Chrome ($c=2^{53}$)! As @hvd said this is likely to depend on the implementation but I can run some tests. Worst case scenario I cause the browser to crash /s $\endgroup$ – bfred.it Dec 2 '14 at 14:18
  • $\begingroup$ Firefox on the other hand caps at $c=2^{24}$, which kind of breaks this solution (anything higher produces 0) $\endgroup$ – bfred.it Dec 2 '14 at 15:08
  • $\begingroup$ @bfred.it: That doesn't necessarily break it. How did you test? Can you link me a fiddle or something I can meddle with a little? Because when I try, the browser seems to be rounding everything to the nearest px. $\endgroup$ – Ben Voigt Dec 3 '14 at 0:03
16
$\begingroup$

If you can use a loop and extra variables, you can repeatedly subtract one until left with only the decimal part.

Something like:

floor(x):
floor = 0
While x >= 1
    floor += 1
    x -= 1
End While

Not the greatest, and will take a long time for large numbers, but it could be tweaked.

It also won't work for negative values, but that's easily fixed.

$\endgroup$
  • 1
    $\begingroup$ I didn't realize your "programming language" was css. I highly doubt this will work in css natively. $\endgroup$ – Brian J Dec 2 '14 at 20:24
  • $\begingroup$ Not in CSS but otherwise this is working solution for a language that would allow it. +1 $\endgroup$ – bfred.it Dec 3 '14 at 8:31
  • 1
    $\begingroup$ This is going to return floor(1) = 0, isn't it? $\endgroup$ – Don Hatch Nov 25 '18 at 8:31
  • $\begingroup$ @DonHatch you're absolutely right. If I change it from $>$ to $>=$ I think it might fix it. $\endgroup$ – Brian J Nov 25 '18 at 13:30
12
$\begingroup$

You can do integer division using complex arithmetic, but there's a different function for each divisor. For example,

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

for $x$ an integer. For higher $k$ you'll use $k$th roots of unity.

$\endgroup$
  • 1
    $\begingroup$ This solution requires exponentiation, which is not among the allowed operations. $\endgroup$ – Christian Semrau Dec 3 '14 at 22:30
  • $\begingroup$ @ChristianSemrau the given ops do not allow complex math (exact, not floating point) or arbitrary roots of unity either. The true answer is either 'no' because of the reason given in the top answer, or 'yes' because the domain is integers and integer division already gives the floor. $\endgroup$ – Mitch Dec 3 '14 at 22:54
  • $\begingroup$ Indeed. Seeing that the indented programming language is CSS, neither is allowed, and the answer is no. $\endgroup$ – Christian Semrau Dec 3 '14 at 23:05
  • $\begingroup$ @Mitch Is there a generalization of this formula ($\lfloor \frac{m}{n} \rfloor$ for $m,\ n$ integer, for instance)? A reference to this idea is also appreciated. $\endgroup$ – Felix Fourcolor Nov 6 '18 at 18:24
8
$\begingroup$

For overkill, if you also have sine you can use the Fourier expansion:

$$\lfloor x \rfloor = x- \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^{\infty} \frac{\sin 2 \pi k x}{k}$$

(except when $x$ is already an integer, I think). If you don't have sine you can build that up using a Taylor's series. Also $\pi$.

$\endgroup$
  • $\begingroup$ Since all your ops are on integers, the output of each op will be integers. The default implementation of integer division and so will be to 'round to 0' which is equivalent to 'floor' on non-negative integers. Which means you don't need a special 'floor' function because you already have it by default. $\endgroup$ – Mitch Dec 2 '14 at 20:09
4
$\begingroup$

If you are able to use a javascript library as well as CSS (maybe not possible if you are using something like eBay) you can use http://lesscss.org/functions/ to extend your CSS to allow a floor function.

$\endgroup$
1
$\begingroup$

Programming languages typically use floating-point arithmetic defined by the IEEE 754 standard. Roughly speaking, if the exact result of an operation calculated using mathematical real arithmetic has an absolute value $2^k ≤ x < 2^{k+1}$, then x will be rounded to the nearest integer multiple of $2^{k-52}$. The exception is the case where x is exactly between the two nearest integer multiples of $2^{k-52}$, in which case x will be rounded to the even multiple.

If the absolute value x is between $2^{52} ≤ x < 2^{53}$, then x will be rounded to the nearest integer or the nearest even integer if x is exactly between two integers. Any floating-point numbers with an absolute value $x ≥ 2^{52}$ are actually integers. And any floating-point operation where the exact result is an integer with $-2^{53} ≤ x ≤ 2^{53}$ will give the exact result.

This gives a simple implementation: If the absolute value of x is $2^{52}$ or greater then x is an integer and floor (x) = x. Otherwise; first add then subtract $2^{52}$ from x if x >= 0, but first subtract then add $2^{52}$ to x if x < 0. This rounds x to one of the two nearest integers. If the result is greater than the original value of x, subtract 1.

I think this is quite close to the implementation that is typically used by current compilers.

$\endgroup$
0
$\begingroup$

try modulo 1 : x=x-(x mod 1) It works with both + and - numbers.

$\endgroup$
  • 7
    $\begingroup$ mod is not among the available operations $\endgroup$ – bfred.it Dec 2 '14 at 14:02
  • $\begingroup$ ... and modulo is only defined for integers. $\endgroup$ – Tomas Dec 5 '14 at 12:09
  • 1
    $\begingroup$ Modulo is defined for non integer numbers... $\endgroup$ – The Great Duck Feb 25 '16 at 7:29
  • $\begingroup$ Can you do the same for ceil()? $\endgroup$ – Dzmitry Lazerka Oct 10 '18 at 3:25
0
$\begingroup$

I know I'm a little late to this party but thought it was worth noting that given a basic round function you can find the floor by doing round(x - .5)

$\endgroup$
  • 6
    $\begingroup$ round() is not among the available operations $\endgroup$ – bfred.it Dec 2 '14 at 14:52
  • $\begingroup$ @bfred.it: See gammatester's answer to see how to induce rounding. $\endgroup$ – Ben Voigt Dec 2 '14 at 17:20
  • $\begingroup$ @BenVoigt Already done and answered, it depends on the implementation. $\endgroup$ – bfred.it Dec 2 '14 at 22:09
  • $\begingroup$ This is at best a supplement to an existing answer. As such I flagged this. $\endgroup$ – Dennis Jaheruddin Dec 4 '14 at 16:45

protected by user642796 Dec 4 '14 at 20:11

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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