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

  • 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
    @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