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.