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

I eventually solved the Self vs Digit overload ambiguity, by marking the Digit overloads as @_disfavoredOverload. My prior solution used a ANKLargeBinaryIntegerWhereDigitIsNotSelf marker protocol, making it possible to build ANKSigned<UInt>. The benefit of using @_disfavoredOverload over a marker protocol, however, is that the former also makes it possible to disambiguate untyped integer literals, meaning that UInt256(1) + 2 can be inferred as UInt256(1) + UInt256(2).

I say this because the documentation states the following. But, there's is no other way of achieving this effect. So, whoever is in charge of @_disfavoredOverload: please be mindful. I need it, or something like it :pleading_face:

Use @_disfavoredOverload to work around known bugs in the overload resolution rules that cannot be immediately fixed without a source break. Don't use it to adjust overload resolution rules that are otherwise sensible but happen to produce undesirable results for your particular API; it will likely be removed or made into a no-op eventually, and then you will be stuck with an overload set that cannot be made to function in the way you intend.

v2.0.0 - The Great Simplification™

I simplified, merged, and removed a bunch of stuff. So now it's a straightforward set of refinements of Swift's standard library. If anybody's interested, here's the new architecture:

  1. ANKBigEndianTextCodable
  2. ANKBinaryInteger
  3. ANKBitPatternConvertible
  4. :x: ANKContiguousBytes
  5. ANKCoreInteger
  6. ANKFixedWidthInteger
  7. :x: ANKIntOrUInt
  8. :x: ANKLargeBinaryInteger
  9. :x: ANKLargeFixedWidthInteger
  10. :x: ANKMutableContiguousBytes
  11. :x: ANKSignedFixedWidthInteger
  12. ANKSignedInteger
  13. :x: ANKSignedLargeBinaryInteger
  14. :x: ANKSignedLargeFixedWidthInteger
  15. :x: ANKTrivialContiguousBytes
  16. :x: ANKUnsignedFixedWidthInteger
  17. ANKUnsignedInteger
  18. :x: ANKUnsignedLargeBinaryInteger
  19. :x: ANKUnsignedLargeFixedWidthInteger
  20. :x: ANKWords
4 Likes

I'm glad you found it useful. If you encounter any issues or have any suggestions, please make them known on GitHub :pray:

Numberick v0.1.0

I have spent the last few weeks redesigning ANK, and this is the result:

I kept what worked and removed what didn't. Here are some highlights:

  • there's one model: NBKDoubleWidth<High>
  • the collection API has been fixed (no more pointers)
  • fast recursive division by C. Burnikel and J. Ziegler
  • DocC documentation on GitHub Pages
  • 100% code coverage (minus preconditions)

Thanks for this, I'll be having another look. Simpler is always better. An unfortunate name, however, because in English, ick tends to mean disgusting :wink:.

Cheers. It should be faster ...and the name is clever :persevere:

Maybe Numerick might be better? English speakers would say this like Numeric.

At any rate "what's in a name"?

Why is there an NBK prefix on all the types?

Maybe Numerick might be better? English speakers would say this like Numeric.

It's "number" + "magick". Had I called it "Numerick" or "Numberic", you'd call me dyslectic instead.

Why is there an NBK prefix on all the types?

Because overloading existing protocols, and inventing new names for them, both sound like bad ideas...

It's too bad that it is no longer possible to have types like UInt192 and UInt384 because of the doubling approach of the types. Only types like UInt128, UInt256, and UInt512 are possible. Not sure if this is a serious problem as long as performance of the new types is better.

It's a more pragmatic design, for sure. I have some cool ideas for irregular sizes like UInt192 and UInt384, but it turns out that powers-of-two are still the kings of binary. There's not that much performance to squeeze out in between doubled widths, and any and every drop of it is paid in code size (although there might be some overlap for tripled widths). In the case of oddly sized bit patterns, it's probably™ better to extend them. At least, that's my hot take on it.