# Signed-integer big division wraps around to negative?

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

I observe this as well.

``````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

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