1

Here's a binomial coefficient function I wrote:

extension FixedWidthInteger {
    /// Determines the binomial coefficient with the nonnegative receiver as the
    /// group size and the given value as the subset size, if it fits.
    public func choose(_ k: Self) -> Self? {
        precondition(self >= 0)
        guard 0...self ~= k else { return 0 }
        guard k > 0, k < self else { return 1 }  // Needed for the "..." below

        // Build the coefficient as (n / 1 * (n-1) / 2 * ... * (n-k+1) / k).
        // Each new increasing product is still a smaller binomial coefficient.
        var result: Magnitude = 1
        var numerator = magnitude
        for denominator in 1...Swift.min(k, self - k).magnitude {
            let intermediateResult = result.multipliedFullWidth(by: numerator)
            guard intermediateResult.high < denominator else { return nil }

            let (nextResult, r) = denominator.dividingFullWidth(intermediateResult)
            assert(r == 0)
            result = nextResult
            numerator -= 1
        }
        return Self(exactly: result)
    }

}

Note after the preamble, I work with Magnitude and convert at the end. I originally didn't have that, working directly with Self. I tested 10.choose(5) with UInt8 to get 252. When I tried with Int8 to test the return-nil-on-overflow, something weird happened. When the numerator counted down to 7, this combines with the last result of 120 to get 840, split in the two pieces of intermediateResult. However, when I fed it back to the wide division step, I got a -46 as the quotient! (All of this found out by stepping through with Xcode.) I didn't realize that the wide-division could generate negative results from positive operands. Eventually, the next cycle generated a division with a non-zero r from the now-garbage inputs, triggering the assert.

I worked around it by switching everything to Magnitude, which has to be an unsigned fixed-width integer in this context. I still want to know why wide division with FixedWidthInteger & SignedInteger worked that way.

2 Likes
2

I observe this as well.

To simplify your example:

let a: Int8 = 120
let b: Int8 = 7
let c: Int8 = 4
let prod = a.multipliedFullWidth(by: b)
let quot = c.dividingFullWidth(prod)
print(prod)   // (high: 3, low: 72)
print(quot)   // (quotient: -46, remainder: 0)

First, notice that the product represents 3*256 + 72 = 840, which is correct.

Second, the bit pattern of -46 as Int8 is 0xd2 (aka 11010010), which is the same as 210 as UInt8:

let bits = UInt8(bitPattern: quot.quotient)
print(bits)   // 210

210, of course, is the correct result of 840 / 4, but it is not representable as Int8.

• • •

Now, the documentation for dividingFullWidth() reads in part:

The resulting quotient must be representable within the bounds of the type. If the quotient is too large to represent in the type, a runtime error may occur.

This appears to be undefined behavior, which is perhaps a bit unexpected. Swift usually traps on integer overflow, but apparently not here.

2 Likes
3

Looking at the implementation, it's pretty easy to see why this happens, but I consider it a bug. At the very least, we should diagnose this in debug builds, but it's simple enough to just do the right thing, so let's fix it. Can you file a report at bugs.swift.org?

1 Like