Does division take longer when dividing perfect factors?

Question

I'm writing a big integer library for Swift, and am running into weird occurrences with testing my division algorithm. It seems to be correct, but when I speed test it, it runs significantly slower when I do division with no remainder than when I try dividing random numbers.

In particular, the tests I'm doing are:

Perfect Division:

for _ in 1...trials {
    let divisor = UBN.random(bytes: maxBytes)
    let knownQuotient = UBN.random(bytes: maxBytes)
    let product = divisor * knownQuotient

    let (quotient, remainder) = product.quotientAndRemainder(dividingBy: divisor)

    XCTAssertEqual(knownQuotient, quotient)
    XCTAssertEqual(remainder, 0)
}

Random Division

for _ in 1...trials {
    let dividend = UBN.random(bytes: maxBytes)
    let divisor = UBN.random(bytes: maxBytes)

    let (quotient, remainder) = dividend.quotientAndRemainder(dividingBy: divisor)

    XCTAssertEqual(divisor * quotient + remainder, dividend)
}

And the random division steps end up running way faster. I am aware that in the perfect division tests, product is much larger than divisor, so it's performing division on larger numbers, but even when I accounted for this, the perfect division still takes way longer.

Is this behavior to be expected? Or is this indicative of some greater error in my division algorithm?

Answer 1

Your test for random division will almost always have a very small quotient (on the order of 0-2), while your perfect division will almost always (minus a negligible fraction) have a quotient of something extremely large.

To think about why the expected quotient will always be small for random numbers, think about a random number between 0 and 100. Half of those numbers are larger than 50, so you have a 1:4 chance that your quotient will be either 0 or 1 depending on which is larger. This is true at any scale. 25% of values being 0 or 1 will dramatically shrink your average. On top of that, 1/2 of all values will have a quotient of 0, since this will happen every time the dividend is smaller than the divisor (this double-counts, so it's not 75% or anything, but it's a lot). The only way to get a large value (i.e. slow to compute) is to pick from the largest dividends and smallest divisors, which is a small selection of all possible choices.

Conversely, the expected quotient for your perfect division is 1/2 * the maximum of UBN, which I presume is enormous.

When you say you accounted for this, you'll need to show some code, because the code above definitely will produce the condition you're describing.