How to divide a nonnegative variable integer by a constant fixed-point rational ≥1 without overflow (at all, if possible)?

Question

How to compute ⌊𝑥÷𝑐⌋ for a variable integer 𝑥 and a fixed-point rational number 𝑐≥1 precisely? The input 𝑥 ∈ [0, INT_MAX] is stored in a variable of type int, 𝑐 ∈ [1, INT_MAX] is given as a decimal literal with a decimal separator in the form 𝑑𝑑𝑑𝑑𝑑.𝑑𝑑 (you may alternatively represent it as a fraction, say, 𝑑𝑑𝑑𝑑𝑑𝑑𝑑/100, if this helps, or as a product of prime powers divided by another product of prime powers), and the output should be a value of type int. Here, ÷ is mathematical division. Our running example is ⌊𝑥÷65781.76⌋; within this example, you can assume that int is at least 3 bytes wide (as otherwise the result would be trivially 0). How to do this in C properly?

Clearly, (int)(𝑥/65781.76f) would involve floating-point arithmetic (and, according to http://www.h-schmidt.net/FloatConverter/IEEE754.html, 65781.76, as most constants, is not precisely representable at least on my machine), whereas 100*𝑥/6578176L and 25*𝑥/1644544L risk an overflow too much. In any case, to my knowledge, adding the suffix L or LL (as in, e.g., 25LL*𝑥/1644544L) is pointless because the types long long, long, and int are not guaranteed to be of different widths. Any other options? I'm interested in solutions involving integer arithmetic only and (most importantly) a proper explanation.

Ideally, we'd like to have a precise and portable solution; if possible, let's stick to C89/C90 without external libraries.

Answer 1

Specific Number

For the specific number in the question, we want ⌊𝑥/65781.76⌋ = ⌊𝑥•25/(2048•803)⌋ = ⌊𝑥•(16+8+1)/2048 / 803⌋ = ⌊(𝑥/128 + 𝑥/256 + 𝑥/2048) / 803⌋.

Next, we separate the integer and fraction portions of 𝑥/128, 𝑥/256, and 𝑥/2048: ⌊(⌊𝑥/128⌋ + 𝑥%128/128 + ⌊𝑥/256⌋ + 𝑥%256/256 + ⌊𝑥/2048⌋ + x%2048/2048) / 803⌋.

Then we group the fractions, using “%” to indicate the remainder operation: ⌊(⌊𝑥/128⌋ + ⌊𝑥/256⌋ + ⌊𝑥/2048⌋ + 𝑥%128/128 + 𝑥%256/256 + x%2048/2048) / 803⌋.

And consolidate them into one term: ⌊(⌊𝑥/128⌋ + ⌊𝑥/256⌋ + ⌊𝑥/2048⌋ + (𝑥%128•16 + 𝑥%256•8 + x%2048)/2048) / 803⌋.

Now the only fraction in the sum is in (𝑥%128•16 + 𝑥%256•8 + x%2048)/2048, so we may discard it, taking its integer portion: ⌊(⌊𝑥/128⌋ + ⌊𝑥/256⌋ + ⌊𝑥/2048⌋ + ⌊(𝑥%128•16 + 𝑥%256•8 + x%2048)/2048⌋) / 803⌋.

So all parts may be calculated with integer arithmetic: (x/128 + x/256 + x/2048 + (x % 128 * 16 + x % 256 * 8 + x % 2048)/2048) / 803.

Observe that all multiplications, remainders, and divisions except the division by 803 may be computed with bit shifts and masks.

General Cases

The above relies on the fact that the quotient in question had a power of two in its factorization. In general, given p and q with p•(q−1) ≤ INT_MAX, we can compute ⌊x•p/q⌋ with x/q*p + x%q*p/q, because ⌊x•p/q⌋ = ⌊x/q•p⌋ = ⌊(⌊x/q⌋+x/q−⌊x/q⌋)•p⌋ = ⌊⌊x/q⌋•p + (x/q−⌊x/q⌋)•p⌋ = ⌊⌊x/q⌋•p + (x%q/q⌋)•p⌋ = ⌊x/q⌋•p + ⌊x%q/q•p⌋ = ⌊x/q⌋•p + ⌊x%q•p/q⌋.

Thus, for the number in question, we seek ⌊x•25/1,644,544⌋, so we can use x / 1644544 * 25 + x % 1644544 * 25 / 1644544.

This uses two divisions, one to compute the quotient and remainder of x when divided by q and then a second division by q.