Floor and ceiling on fractions 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
 A: 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?
A: 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.
