A large fixed-width integer Swift package

Hi! I have published a Swift package, AwesomeNumbersKit, using Swift 5.7 and Swift Package Manager. It contains various numeric models, protocols, and extensions leveraging Swift's generic type system. It's a bit experimental but also complete enough that somebody interested in Swift may find something that piques their interest.

It contains three modules: ANKFoundation, ANKFullWidthKit, and ANKSignedKit. I want to keep this post short, so I'll focus on the second module and maybe highlight some cool things about Swift. As revealed by its name, it hosts the ANKFullWidth<High, Low> model. The latter is a large, fixed-width, two's complement integer - that composes in the following fashion:

typealias  ANKInt256 = ANKFullWidth< ANKInt128, ANKUInt128>
typealias ANKUInt256 = ANKFullWidth<ANKUInt128, ANKUInt128>

This partition may remind you of AnimatablePair<First, Second>. Well, as it turns out, this design pattern also lends itself to modeling fixed-width integers! The DoubleWidth<Base> prototype is another example, in the same spirit but with different constraints. This prototype is also quite clever, as it propagates signed-ness using the protocol conformances of its Base type. Similarly, the model I'm presenting uses its High type.

extension ANKFullWidth:   SignedInteger where High:   SignedInteger { }
extension ANKFullWidth: UnsignedInteger where High: UnsignedInteger { }

Given that ANKFullWidth<High, Low> is not as divide-and-conquer-able as the DoubleWidth<Base> model (± constant-folded strategies), it leverages instead a set of withUnsafe[Mutable]WordsPointer(_:) methods to implement word-based algorithms. Viewing it as a collection of [U]Int words (à la BigInt), using pointers rather than high and low partitions, also enables a set of digit arithmetic overloads. These overloads keep the cost of small-integer arithmetic low and are particularly well-suited for chunk-wise calculations (like text de/encoding). In the future, however, I hope to retire all withUnsafePyramidOfDoom(_:) methods in favor of safer and more ergonomic BufferView accessors.

extension ANKFullWidth {
    static func +(lhs: Self, rhs: Self ) -> Self
    static func +(lhs: Self, rhs: Digit) -> Self // 🙏 where Digit != Self 🙏
}

That's it: a neat integer model powered by Swift. Perhaps it piques your interest. Cheers!

6 Likes

This is really cool! Have you thought of (or already) applied this approach to fixed point numbers?

I'm happy to hear it! No, I have not thought about it. But the idea is neat. I don't have an immediate use for it - but I will think about it! :thinking:

I do have some immediate thoughts on the topic, however. I think the preferred generic model is decorative, as opposed to compositive. While the partitioning strategy works well for its use case, it puts some constraints on the size of the struct and its partitions. You cannot create a 16-bit U(10, 6) fixed-point number with a generic FixedPoint<Integer, Fraction> model, for example, because 10-bit and 6-bit partitions don't exist. If I had to guess, the preferred generic model is instead something along the lines of: FixedPoint<BitPattern, ScaleFactor> where BitPattern is a FixedWidthInteger and ScaleFactor is a piece of metadata describing the location of the point. Using this approach, you can express U(10, 6) using existing integer types.

1 Like