1

A novel binary integer abstraction

Hello, everybody! I'm working on a novel binary integer abstraction on GitHub.

I thought I'd share it in case some of you find it interesting. It unifies fixed-width and variable-width representations and brings recovery mechanisms to generic code. It's experimental, and I don't expect it to stabilize anytime soon, but it's still super neat in its current state. It's more or less at the point where I want to build something with it and iterate based on that experience.

I'm 5 months and (128,665 ++, 102,232 --) deep into it.

It features 8-bit to 64-bit integers, a generic un/signed double-width model, and a generic un/signed big-integer type. It also introduces a notion of infinity to ensure invariants like ~(~(x)) == x for all x.

The README.md is a work in progress, but it explains the new concepts.

Also, I have seen @wadetregaskis mention my predecessor project Numberick a few times, and I appreciate the positive commentary. Thanks! Having said that, I don't plan on maintaining the old project since the new abstraction is much more powerful.

Example: constant-foldable generic comparisons... 
extension BinaryInteger {
    @inlinable public func compared<Other>(to other: Other) -> Signum where Other: BinaryInteger {
        if  let lhsSize = UX(size: Self.self), let rhsSize = UX(size: Other.self) {
            if  lhsSize < rhsSize {
                return Other(load: self).compared(to: other)
                
            }   else if lhsSize > rhsSize {
                return self.compared(to: Self(load: other))
                
            }   else if Self.isSigned, !Other.isSigned {
                return self .isNegative ? Signum.less : Other(load: self).compared(to: other)
                
            }   else if !Self.isSigned, Other.isSigned {
                return other.isNegative ? Signum.more : self.compared(to: Self(load:  other))
                
            }   else {
                return self.compared(to: Self(load: other))
            }
            
        }   else {
            //  note that the elements must be rebindable one way or the other
            if  Other.elementsCanBeRebound(to: Self.Element.Magnitude.self) {
                return self.withUnsafeBinaryIntegerElements { lhs in
                    (other).withUnsafeBinaryIntegerElements(as: Self.Element.Magnitude.self) { rhs in
                        DataInt.compare(
                            lhs: lhs, lhsIsSigned: Self .isSigned,
                            rhs: rhs, rhsIsSigned: Other.isSigned
                        )
                    }!
                }
                
            }   else {
                Swift.assert(Self.elementsCanBeRebound(to: Other.Element.Magnitude.self))
                return self.withUnsafeBinaryIntegerElements(as: Other.Element.Magnitude.self) { lhs in
                    (other).withUnsafeBinaryIntegerElements { rhs in
                        DataInt.compare(
                            lhs: lhs, lhsIsSigned: Self .isSigned,
                            rhs: rhs, rhsIsSigned: Other.isSigned
                        )
                    }
                }!
            }
        }
    }
}
Example: a fully generic and fully recoverable Fibonacci sequence... 
@frozen public struct Fibonacci<Value> where Value: BinaryInteger {
    
    //=------------------------------------------------------------------------=
    // MARK: State
    //=------------------------------------------------------------------------=
    
    @usableFromInline var i: Value
    @usableFromInline var a: Value
    @usableFromInline var b: Value
    
    //=------------------------------------------------------------------------=
    // MARK: Initializers
    //=------------------------------------------------------------------------=
    
    /// Creates the first sequence pair.
    @inlinable public init() {
        self.i = 0
        self.a = 0
        self.b = 1
    }
    
    /// Creates the sequence pair at the given `index`.
    @inlinable public init(_ index: Value) throws {
        if  Bool(index.appendix) {
            throw Value.isSigned ? Failure.indexOutOfBounds : Failure.overflow
        }
        
        self.init()
        
        try index.withUnsafeBinaryIntegerElementsAsBytes {
            let x = $0.body.count(.nondescending(.zero))
            for i in (0 ..< x).reversed() {
                try self.double()
                
                if  $0.body[unchecked: i &>> 3] &>> U8(load: i) & 1 != 0 {
                    try self.increment()
                }
            }
        }
    }
    
    //=------------------------------------------------------------------------=
    // MARK: Accessors
    //=------------------------------------------------------------------------=
    
    /// The sequence `index`.
    @inlinable public var index: Value { 
        self.i
    }
    
    /// The sequence `element` at `index`.
    @inlinable public var element: Value {
        self.a
    }
    
    /// The sequence `element` at `index + 1`.
    @inlinable public var next: Value { 
        self.b
    }
    
    //=------------------------------------------------------------------------=
    // MARK: Transformations
    //=------------------------------------------------------------------------=
    
    /// Forms the sequence pair at `index + 1`.
    @inlinable public mutating func increment() throws {
        let ix = try i.plus(1).prune(Failure.overflow)
        let bx = try a.plus(b).prune(Failure.overflow)
        
        self.i = consume ix
        self.a = b
        self.b = consume bx
    }
    
    /// Forms the sequence pair at `index - 1`.
    @inlinable public mutating func decrement() throws {
        let ix = try i.minus(1).veto({ $0.isNegative }).prune(Failure.indexOutOfBounds)
        let ax = try b.minus(a).prune(Failure.overflow)
        
        self.i = consume ix
        self.b = a
        self.a = consume ax
    }
    
    //=------------------------------------------------------------------------=
    // MARK: Transformations
    //=------------------------------------------------------------------------=
    
    /// Forms the sequence pair at `index * 2`.
    @inlinable public mutating func double() throws {
        let ix = try i.times(2).prune(Failure.overflow)
        let ax = try b.times(2).minus(a).times (a).prune(Failure.overflow)
        let bx = try b.squared().plus(a.squared()).prune(Failure.overflow)

        self.i = consume ix
        self.a = consume ax
        self.b = consume bx
    }
    
    /// Forms the sequence pair at `index + x.index`.
    @inlinable public mutating func increment(by x: Self) throws {
        let ix = try i.plus (x.i).prune(Failure.overflow)
        let ax = try a.times(x.b).plus(b.minus(a).times(x.a)).prune(Failure.overflow)
        let bx = try b.times(x.b).plus(       (a).times(x.a)).prune(Failure.overflow)

        self.i = consume ix
        self.a = consume ax
        self.b = consume bx
    }
    
    /// Forms the sequence pair at `index - x.index`.
    @inlinable public mutating func decrement(by x: Self) throws {
        let ix = try i.minus(x.i).veto({ $0.isNegative }).prune(Failure.indexOutOfBounds)
        
        var a0 = b.times(x.a).value
        var a1 = a.times(x.b).value
        var b0 = b.plus(a).times(x.a).value
        var b1 = b.times(x.b).value
        
        if  Bool(x.i.leastSignificantBit) {
            Swift.swap(&a0, &a1)
            Swift.swap(&b0, &b1)
        }
        
        self.i = consume ix
        self.a = a1.minus(a0).value
        self.b = b1.minus(b0).value
    }
    
    //*========================================================================*
    // MARK: * Failure
    //*========================================================================*
    
    public enum Failure: Error {
        
        /// Tried to form a sequence pair that cannot be represented.
        case overflow
        
        /// Tried to form a sequence pair at an index less than zero.
        case indexOutOfBounds
    }
}
5 Likes
2

Looks nice! I created a PR with some typos fixed

1 Like
3

Neat! Apologies if I missed it, but I read through the readme and didn't see a direct performance comparison to the stdlib integers. Do you have benchmarks somewhere?

I understand many ops may constant fold, I'm curious how many do in practice. Additionally would a notion of const be helpful for ensuring constant folding anywhere in this library?

1 Like
4

Neat! Apologies if I missed it, but I read through the readme and didn't see a direct performance comparison to the stdlib integers. Do you have benchmarks somewhere?

I performed a lot of micro benchmarks in Numberick, but there was little payoff and nobody cared until quite recently when somebody noticed that this process had made the fib sequence quite speedy. Still, there has been no real payoff, so I've omitted benchmarking. Instead, I have focused on abstraction, complexity, and recovery in generic code. I would rather build something cool and measure the performance by proxy. I have compared the fib sequence, however, and it's a bit faster than it was in Numberick. So the transition from mutating methods to consuming methods seems to have gone well (± the occasional nonzero exit code).

//   MacBook Pro, 13-inch, M1, 2020, -O, code coverage disabled
try! Fibonacci<UXL>( 1_000_000) // 0.04s
try! Fibonacci<UXL>(10_000_000) // 1.65s from 2.30s in Numberick

I understand many ops may constant fold, I'm curious how many do in practice. Additionally would a notion of const be helpful for ensuring constant folding anywhere in this library?

In my experience, constants :tm: almost always fold if you follow the rules to the point that a function call can be specialized. At least, that's my experience looking at Swift.FixedWidthInteger assembly on Godbolt. Again, I don't know if they do in this project, because I have not looked at that level of detail. I suppose a compiler hint would be useful if it could guarantee that they are evaluated at compile time. I'm not sure how such a hint would work with the dynamic any stuff, which I rely on a lot for testing purposes, however.

2 Likes
5

Good performance is something people rarely comment on, even though it matters to them. And with relatively uncommon domains, like arbitrary-precision integers, people don't have a good intuition for what the performance should be, so they might just accept whatever they get.

I think Numberick may have also simply suffered from being ranked lower in searches than BigInt, in part down to simple things like the name not being as self-explanatory.

Also, your readme on Numberick does say that it's basically abandoned, so that's going to discourage people from using it. :slightly_smiling_face:

2 Likes
6

My point is that benchmarking is an unpaid time sink. I'd need food, not GitHub stars.

2 Likes
7

Here's a cute measurement for those of you who like benchmarks:

MacBook Pro, 13-inch, M1, 2020, -O, code coverage disabled.
let fib1e6 = try! Fibonacci<UXL>(1_000_000)

let fib1e6r10 = fib1e6.element.description(as:     .decimal) // 0.924s (208988 digits)
let fib1e6r16 = fib1e6.element.description(as: .hexadecimal) // 0.002s (173561 digits)

try! UXL(fib1e6r10, as:     .decimal) // 0.040s (208988 digits)
try! UXL(fib1e6r16, as: .hexadecimal) // 0.002s (173561 digits)

This example is on the asymptotic side of things, and there might be better
algorithms for silly numbers, but silly examples are more fun. It also shows
that hexadecimal is king.

The conversion model uses the same non-generic and non-inlinable algorithms for all binary integers. So it's really optimized for size rather than performance, but it's still quite decent—as you can see.

The encoding strategy is more or less the algorithm I wrote for the Foundation project but generalized over the various radices. I would have proposed an arbitrary-precision decoding strategy as well if Swift.BinaryInteger did not make it so difficult. The problem is that it lacks recovery options (1) or a bitwise initializer (2). It is still possible to implement generic arbitrary-precision decoding, but it requires a Swift.BigInt model because of (1) and (2).

2 Likes
8

So it turns out that using StaticBigInt made DoubleInt<T> super slow. I suppose this is one such case where it would be nice to have compile-time constants. Tangentially, StaticBigInt does not provide access to a buffer pointer, unlike its StaticString sibling. While I'm unfamiliar with its built-in model, I think it would be appropriate to provide a buffer-pointer-view-thing-y if StaticBigInt happens to be represented as binary integer words in memory.

Also, I've made things even more generic and fixed like a gazillion bugs. I believe even the comparison example is incorrect, but I can't edit it. It's like embarrassment etched in stone.

9

The original pitch had a buffer pointer, but it was removed for various reasons.

Future directions of StaticBigInt:

10

I wanted to fuzz something, so I've added a new module and some randomness features:

.product(name: "Ultimathnum",  package: "Ultimathnum"), // umbrella
.product(name: "CoreKit",      package: "Ultimathnum"),
.product(name: "DoubleIntKit", package: "Ultimathnum"),
.product(name: "FibonacciKit", package: "Ultimathnum"),
.product(name: "InfiniIntKit", package: "Ultimathnum"),
.product(name: "RandomIntKit", package: "Ultimathnum"), // oh, so shiny!
.product(name: "StdlibIntKit", package: "Ultimathnum"),

Random number generation is fully generic over BinaryInteger, so it also works with signed and unsigned arbitrary-precision integers:

extension Ultimathnum.BinaryInteger {

    /// Generates a random value in the given `range` from the given source of `randomness`.
    ///
    /// - Requires: The `range` must be finite.
    ///
    public static func random(in range: ClosedRange<Self>, using randomness: inout some Randomness) -> Self { ... }
         
    /// Generates a random value in the given `range` from the given source of `randomness`.
    ///
    /// - Requires: The `range` must be finite.
    ///
    public static func random(in range: Range<Self>, using randomness: inout some Randomness) -> Optional<Self> { ... }
         
    /// Generates random bits through the given `index`.
    ///
    /// Signed integers are extended by the most significant bit whereas unsigned
    /// integers are extended by zero. You may bit-cast a different type to adopt
    /// its behavior.
    ///
    ///                ┌──────────┬──────────┬──────────┐
    ///                │ index: 0 │ index: 1 │ index: 2 │
    ///     ┌──────────┼──────────┤──────────┤──────────┤
    ///     │   Signed │ -1 ... 0 │ -2 ... 1 │ -4 ... 3 │
    ///     ├──────────┼──────────┤──────────┤──────────┤
    ///     │ Unsigned │  0 ... 1 │  0 ... 3 │  0 ... 7 │
    ///     └──────────┴──────────┴──────────┴──────────┘
    ///
    /// - Note: The result is always finite.
    ///
    /// - Requires: The request must not exceed the entropy limit.
    ///
    public static func random(through index: Shift<Magnitude>, using randomness: inout some Randomness) -> Self { ... }
}

Arbitrary integers and systems integers derive different algorithms, which is possible because I've hoisted 1-by-1-as-2 multiplication to BinaryInteger:

U32.max.times(U32.max) // value: 1, error: true
UXL.max.times(UXL.max) // value: 1, error: true

U32.max.multiplication(U32.max) // low: 1, high: ~1
UXL.max.multiplication(UXL.max) // low: 1, high: ~1

It turns out that computing the high part of multiplication is trivial in both the signed and the unsigned case, making the latter even more infinite! Lol.

11

I wrote some division-by-magic-constant-multiplication for my unified text decoding and encoding model, which made the earlier decimal encoding case more than three times faster. I've added 1-by-1 and 2-by-1 magic constant finders.

Note that the 2-by-1 model is responsible for the performance improvement. I first tried reducing the chunking size to 32 bits and performing the 2-by-1 division using a 64-bit version of the 1-by-1 model, but that only improved it by ~20%.

How does it work?

You can add a rounding error to a rational number and get the same quotient, provided that the rounding error is sufficiently insignificant:

       a            a               a            1 
floor( - ) = floor( - + e ) for all - if 0 ≤ e < -
       b            b               b            b

Dividing is expensive and complicated, so we could instead replace it with an unsigned right shift and a sufficiently close approximation of c = (2^k)/b:

       a            2^k    a  
floor( - ) = floor( --- * --- ) = ( c * a ) >> k
       b             b    2^k

We can always find a good same-size approximation if we allow ourselves to round the multiplier either up or down. We must compensate the latter case with an increment, turning our division algorithm into a multiplication, addition, and shift. The bounds are thus given by the following, where x is the multiplier's rounding error:

The rounding-up case (the increment is zero)
a   2^k + x   a + 0   a   1              
- ≤ ------- * ----- < - + - when 0 ≤ x ≤ 2^(k - size)
b      b       2^k    b   b
The rounding-down case (the increment is equal to the multiplier)
a   2^k - x   a + 1   a   1
- ≤ ------- * ----- < - + - when 0 < x ≤ 2^(k - size)
b      b       2^k    b   b

At least one case is guaranteed to have a good approximation when k - size ≥ log2(b). This mul-add-shr operation also works for power-of-two divisors if we contrive a downward rounding error of 1. It's magic :sparkles:

1 Like