1
$\begingroup$

Is there an algorithm to compute ceil and floor on fractions without computing the division between the numerator and denominator (to avoid losing precision on big numbers)?

A trivial example: $\lfloor{\frac{713813}{329230}}\rfloor = 2$, but how to calculate that?

Thank you,
rubik

  • 0
    What precision are we trying not to lose? You do realize that the floor function *rounds*...2011-12-07
  • 0
    I want to implement a new number representation, in which every number is being represented as a fraction, so I have to compute floor and ceil on fractions. In this case there isn't any precision to lose, but if I succeed in representing floats as fractions I won't have precision problems.2011-12-07
  • 0
    @QiaochuYuan: Yes, you hit the point2011-12-07
  • 0
    Usually, programming languages have remainder (modulo) and quotient operations as a pair...2011-12-07
  • 0
    @J.M.: Are you referring at Python's divmod? http://docs.python.org/library/functions.html#divmod2011-12-07
  • 0
    Something like that.2011-12-07
  • 0
    You should realize that the floor you are asking for is exactly the remainder in euclidean division. This is not the same as floating point division, and there is no uncertainty in the result, so if that's what you worry about you'll be OK. But if you don't want euclidean division, you're asking to find the quotient without doing a division, and the only way to do that would just be a *more* roundabout way of finding the same result.2011-12-07
  • 0
    @Marc van Leeuwen: Thank you. In fact I've found this formula, which is great for me: $\displaystyle floor(n, m) = \frac{n - n \mod{m}}{m}$2011-12-11
  • 1
    @rubik: The formula you give is equivalent to $n\bmod m = n - m\,\mathrm{floor}(n,m)$, which is the *definition* of the mod operation, and the way it is computed. The euclidean quotient $\mathrm{floor}(n,m)$ is the largest (assuming that $m>0$) $q$ such that $n-qm\geq0$, and this remainder $n-qm$ is by definition $n\bmod m$; so computing $n\bmod m$ one has $q=\mathrm{floor}(n,m)$ as by-product. By the way, excuse me for saying remainder instead of quotient in my previous comment.2011-12-11

2 Answers 2

2

Integer division is exact, and requires space as large as the denominator. Are you perhaps asking what the most efficient method is for integer division without remainder? Have a look at the division algorithm: if $a=qb+r$ with $0\le r<|b|$, then $\lfloor\frac{a}{b}\rfloor=q$, and $\lceil\frac{a}{b}\rceil$ is either also $q$ (if $r=0$) or else $q+1$ (for $r>0$). The work required to find $q$ given arbitrary $a$ & $b$ is equivalent to division, but under special conditions (e.g. if $b$ is fixed, or is a power of two) can be implemented much more efficiently. Check out Knuth's Seminumerical Algorithms chapter 4 (Arithmetic) if such a special case might apply, or if you are concerned about accuracy. Is your concern how to program this efficiently on any given platform in any given language to arbitrary precision? Or do you just want to be able to calculate at will (for example with a computer algebra system such as sage)?

In fact, if we start by truncating $a$ and $b$ to fewer digits of accuracy, the estimated quotient will still be within $\pm1$ of $q$ provided that we haven't truncated too much of $b$ away, as @deinst illustrates. Are you looking for such a guarantee?

  • 0
    Thank you for your reply. Yes, I'm looking for a very efficient method to find the floor given a numerator and a denominator. Unfortunately I don't have fixed conditions, so I'll stick with division algorithm (I can obtain $q$ and $r$ at the same time). I've also heard about a modified Newton method to compute the floor but I didn't find an implementation.2012-04-06
0

It depends what you mean by compute the division. You know that $$\frac{700000}{400000}<\frac{713813}{329230}<\frac{800000}{300000}$$ which is enough to let you see that the floor is either $1$ or $2$ as $\lfloor 7/4\rfloor=1$ and $\lfloor 8/3\rfloor=2$. Similarly, $$\frac{710000}{330000}<\frac{713813}{329230}<\frac{720000}{320000}$$ which is enough to tell you that the floor is 2.

However, computing one significant digit of $7/4$ on a computer is just as hard as computing one significant digit of $713813/329230$ so unless your numbers are very large (more than one computer word, there is no significant benefit.

  • 0
    Did you mean $\lfloor 8/3 \rfloor = 2$?2011-12-07
  • 0
    The problem is I don't want to compute division at all. All numbers should be represented as fractions. Is it possible at least?2011-12-07
  • 0
    @rubik Doh! Thanks2011-12-07
  • 0
    @rubik Well, you can do repeated additions of the denominator until the sum gets larger than the numerator, but that is essentially division.2011-12-07