Is a > c / b a safer equivalent (but avoiding overflow) version of a * b > c for positive integer division?

Question

This came up in a C++ program I am writing for iterating over a loop, where it was pointed out that the for loop condition a * b > c could overflow. I am rusty with integer math but I think, mathematically ignoring overflow, a * b > c is equivalent to a > c // b, so the second form can be used to avoid overflow in C++ code. For the sake of clarity, I will use the python syntax of / means rational division and // means integer division:

• Forward: a * b > c implies a > c / b >= c // b. (by defn of floor. Same for a * b >= c)
• Backwards: a * b <= c implies a <= c / b < (c // b) + 1, so I think it must be that a <= c // b. (For integers, a <= b iff a < b + 1.) By contrapositive, a > c // b implies a * b > c.

Is this correct? The definition of floor I use is for any real x, floor(x) is the integer satisfying floor(x) <= x < floor(x) + 1.

The same question applies for whether a * b >= c is equivalent to a >= c // b. The forward argument I think holds, but backwards fails for a=2, b=2, c=5, since 2 >= 5 // 2 but NOT 2 * 2 >= 5 as Mark Glisse points out in the comments. In that case, how can a * b >= c be safely tested without overflow?

Answer 1

The > case is obvious if you phrase c//b as being “the largest integer which, when multiplied by b, does not exceed c”. The >= case can be handled by simply rewriting it as a*b > c-1, reducing it to the previous.

All this for positive b, of course, since dividing by a negative changes the direction of the inequalities. (Also, in C++ dividing by negative integers isn’t floor division and dividing by -1 can itself overflow.)

Answer 2

Addendum: Martin Brown points out in the comments that promoting to a 128-bit integer and doing the multiply is going to be much faster than the 64-bit integer divide. A single mul instruction computes the 128-bit result in rdx:rax (which also happens to be the registers for the return value in 64-bit Linux ABI if you returned immediately).

https://godbolt.org/z/cTrcb11vx

bool check1(uint64_t a, uint64_t b, uint64_t c)
{
    return (unsigned __int128)a * b > c;
}

This is as its own function, but inline it will avoid the calling convention boilerplate and probably rearrange the instructions to use the registers more efficiently. sbb uses the carry flag as a borrow from a previous subtraction.

        mov     rax, rdi  ; rax = a (rdi)
                          ; rsi = b (rsi)
        mov     rcx, rdx  ; rcx = c (rdx)
        xor     edi, edi  ; rdi = 0
        mul     rsi       ; rdx:rax = rax * rsi
        cmp     rcx, rax  ; CF = (rcx - rax < 0)
        mov     rcx, rdi  ; rcx = 0
        sbb     rcx, rdx  ; rcx -= rdx + CF, i.e. set CF = -(rdx + CF) < 0
        setc    al        ; rax = CF
        ret

On modern processors, MUL (R64) has an impressive throughput of 1 cycle per multiply!

bool check2(uint64_t a, uint64_t b, uint64_t c)
{
    return a > c / b;
}

                          ; rdi = a, rsi = b
        mov     rax, rdx  ; rax = c
        xor     edx, edx  ; rdx = 0
        div     rsi       ; divide rdx:rax by rsi, rax = quotient
        cmp     rax, rdi  ; CF = (rax - rdi < 0)
        setb    al
        ret

DIV (R64) is slow, and actually it does a 128-bit divide by 64-bit, but we only use the lower 64-bits of the dividend. On Haswell it has a throughput of 21 cycles, however on a newer Rocket Lake it's only 10 cycles.