await Sliced Bread 3.0

[oscbyspro]

I've got an awesome idea. It's Sliced Bread 3.0. I'll put this project on hold while I work on it. It's a simpler design, but I need to know whether it's viable w.r.t. performance, etc. It's a reduced instruction set that leverages some of Swift's new and upcoming features 🤩

[oscbyspro]

I will take a while until it becomes benchmark-able, but the API is already pure greatness 🚀

The narrator be like: "Where did the code go?"

[oscbyspro]

I'll add two 1-bit integers too so double-and-add algorithms just work:

for bit: BitInt.Magnitude in ChunkedInt(normalizing: base, isSigned: false).reversed() {

    double()

    if  bit == 1 {
        increment()
    }
}

[oscbyspro]

Fun fact: a signed 1-bit integer cannot represent its own bit width.

[oscbyspro]

The new protocol hierarchy is fully abstract, which is really quite neat; it doesn't assume any integer type. Additionally, the requirements are so few that they fit on my 13-inch MacBook screen ⭐ 💻 ⭐

[oscbyspro]

Honorable mentions: consuming, throws(Error) and package.

[oscbyspro]

Here's an example of code that's trivial to write with error propagation:

if  let shift = try? shift.incremented(by: bitWidth) {
    XCTAssertEqual(operand &<< shift, result, file: file, line: line)
}

if  let shift = try? shift.incremented(by: bitWidth).incremented(by: bitWidth) {
    XCTAssertEqual(operand &<< shift, result, file: file, line: line)
}

if  let shift = try? shift.decremented(by: bitWidth) {
    XCTAssertEqual(operand &<< shift, result, file: file, line: line)
}

if  let shift = try? shift.decremented(by: bitWidth).decremented(by: bitWidth) {
    XCTAssertEqual(operand &<< shift, result, file: file, line: line)
}

Compare that to the following (another take on the second assertion):

attempt: do {
    var help = (partialValue: shift, overflow: false)
    
    help = help.partialValue.addingReportingOverflow(bitWidth)
    guard !help.overflow else { break attempt }
    
    help = help.partialValue.addingReportingOverflow(bitWidth)
    guard !help.overflow else { break attempt }
    
    XCTAssertEqual(operand &<< help.partialValue, result, file: file, line: line)
}

Alternatively, I could return a struct with convenience methods:

if  let shift = shift.incremented(by: bitWidth).optional()?.incremented(by: bitWidth).optional() {
    XCTAssertEqual(operand &<< shift, result, file: file, line: line)
}

if  let shift = try? shift.incremented(by: bitWidth).throwOnOverflow().incremented(by: bitWidth).throwOnOverflow() {
    XCTAssertEqual(operand &<< shift, result, file: file, line: line)
}

[oscbyspro]

Speaking of structs. I find it common to round up division. I could do:

try dividend.divided(by: divisor)        // quotient,   remainder
try dividend.divided(by: divisor).ceil() // quotient + (remainder > 0 ? 1 : 0) 

[oscbyspro]

I might need a failable version of init(integerLiteral:) to make the Fibonacci sequence work with BitInt and BitInt.Magnitude. Can't easily double() the index otherwise. These 1-bit integers can represent 0 and 2 sequence pairs. Have fun 🤣

[oscbyspro]

Hm. I think I can derive it from init(words:isSigned:) via StaticBigInt.

[oscbyspro]

Most things will be derived from a few core requirements this time around. Keep it simple.

[oscbyspro]

Core requirements should compose well. That's the idea, at least. So my new big integer will need a small-integer storage optimization, for example, because otherwise expression like x == 0 could be expensive. In Numberick I've assumed that it might be expensive, which is one reason for why there are so many customization points 🤷‍♂️

[oscbyspro]

I might make the big integer generic, because I want simple dependencies. The new CoreKit doesn't even have an integer type. Lulz.

[oscbyspro]

You could even write generic collections without concrete integer types if collections looked like the following:

protocol Collection {
    associatedtype  Stride:
    SignedInteger & SystemInteger where
    Stride.BitPattern == Word

    var count: Stride { get }
}

I don't want to rewrite the collection protocol hierarchy, so I might pretend that's what I've done whenever I use Int or UInt in a generic collection. Imagine these types being Stride or Stride.Magnitude instead.

[oscbyspro]

This is important because I want the following collections in CoreKit:

• BitCastSequence<Base, Element>
• ChunkedIntSequence<Base, Element>
• StaticBigIntWords

[oscbyspro]

Next up: chunking to/from Word without making it an integer ( 💤 ).

[oscbyspro]

Hm. The abstraction for chunking non-integers would have to be so similar to an integer that I don't see much of a point to it. I suppose I could limit the big integer to store Word sized elements. I mean, that's rather sensible, but it would have been cool ( ™️ ) to allow something like BigUInt<BitUInt>. The problem is really about converting it to a collection of words at some point. That's doable if you have a word-sized integer, but I also don't want to add a concrete type dependency.

[oscbyspro]

Hm. I thought it would be clever to give every integer a negate() method and use that to recover the magnitude of unsigned binary integer subtraction overflow. After testing it, however, it seems like that's not possible and that I need to use a twosComplement() operation instead. This is because one operation needs to be extending and one needs to be truncating, if that makes sense.

[oscbyspro]

It's is possible with fixed-width integers because they don't auto normalize. It would work with a flexible-width integer that requires manual normalization, but I've decided to not make one of those because they require too much babysitting in generic code (and a no-op on every other integer type).

[oscbyspro]

Hm. I might have to add ones complement and twos complement as binary integer requirements because I don't want to add truncating operations. &+ is too arcane in the flexible-width case. You might think it just ignores errors in generic code. Nope. Guess again. But you can't implement two's complement as a protocol extension without it; fail-able addition is not enough, it has to be truncating addition.

[oscbyspro]

I'm considering something like the following, perhaps:

protocol BinaryInteger {
    
    /// A useful operation, albeit a bit arcane in the arbitrary precision case. 
    ///
    /// - Note: It's a bit like Hasher/finalize().
    ///
    consuming func irreversibleOnesComplement() -> Self
    
    /// A useful operation, albeit a bit arcane in the arbitrary precision case. 
    ///
    /// - Note: It's a bit like Hasher/finalize().
    ///
    consuming func irreversibleTwosComplement() -> Self
}

[oscbyspro]

Hm. Is there a better normalization mode for unsigned integers? Like, can we pretend UIntXL is truly infinite-width and NOT(x) to infinity? That would make NOT(x) and twos complements reversible, at least.

[oscbyspro]

With this approach, I would need a sign-extended words model because infinity is obviously infinite.

Edit: Alternatively, I suppose I could allow the words getter to fail and throw an error in this case.

[oscbyspro]

I wonder if I could make a signed and unsigned binary integer using the same generic model.

[oscbyspro]

Unsigned big (normalized) binary integers are a bit handicapped and the question is whether the protocol should share its limitations. I could drop bit inversions, I could drop the protocol conformance, or I could make a signed big (normalized) binary integer instead. Hm.

[oscbyspro]

I would not need a 2's complement operation if I decide that negated() must be reversible for binary integers.

[oscbyspro]

Hm. If a big unsigned binary integer can represent infinity (all 1s), then both ~x and negated() would be recoverable. In that case, I could even add a static bit width to every binary integer type:

protocol BinaryInteger {
    static var bitWidth: Magnitude { get }
}

BigInt.bitWidth // BigInt.Magnitude.infinity

[oscbyspro]

I could also require all binary integers to be bit castable.

[oscbyspro]

I could give all binary integers init(repeating:) too.

[oscbyspro]

Hm. Unsigned infinite-width integers are such a headache compared to signed ones. Signed big binary integers are always well-behaved, whereas I'm not sure you can make an unsigned big integer that is recoverable and consistent. The problem is really the bitwise not (~) operation, which is either truncating and non-recoverable or extending and infinity-weird.

[oscbyspro]

I wonder if I can still do the unsigned infinity stuff if multiplication and division counts as overflow.

[oscbyspro]

Hm. A core module without a currency integer type might be a bit too anti-pragmatic. I might change that.

[oscbyspro]

Hm. I think there might be like two Guarantee<T> types that are actually useful, and that every other type is too bothersome. I like Shift<T> because it composes better than eager bit masking and it prevents the infinite &<< footgun. The other one I've been thinking about is Divisor<T>, which is just a nonzero value. I like it because removes the only undefined output. I've been trying to make Natural, Power2 and the like work, but they're not great and there's nothing in the binary integer protocol's list of requirement that benefit from them (perhaps the bit width, but it's not like they constrain any input values).

[oscbyspro]

Here's a cool piece of code:

var value = I8(0)
let error = value[raw: U8.self][{ $0.decremented() }]

print(value) // -1
print(error) // true

1. The 1st subscript reinterprets value through the type-safe BitCastable protocol.
2. The 2nd subscript turns a consuming method into a mutating method by destructuring the result.

The 2nd subscript cuts the project code in half, or some such silly amount.

Also, I've renamed init(bitPattern:) as init(raw:) because I use it a lot a lot a lot...

[oscbyspro]

I'm thinking of reimplementing the SignedInt<Magnitude> model as a proof-of-it-works. Having said that, I wonder if I should ban negative infinities. I have a sign-and-magnitude coder at the moment, which allows negative infinities as a consequence of not disallowing it, but I think there's at least some merit in having a format that cannot represent binary integers that are too negative to store in memory.

If I ban it, then infinity could be in the same regex group as "+" and "-".

[oscbyspro]

Hm. It's probably a bad idea since I would have to reject positive infinities in the init.

[oscbyspro]

I suppose I could also keep things simple by skipping this model 🤷‍♂️

[oscbyspro]

Ooo, I just added a 3rd flavor of binary integer. I wonder what it could be? 👀

[oscbyspro]

It's a useful protocol, not a new bit pattern complement 😅

[oscbyspro]

The 🧗 to 💯 unit test code coverage has begun 😣

[oscbyspro]

2024-05-10: 95%

[oscbyspro]

2024-05-14: 98%

[oscbyspro]

I have some normal code paths left, but I don't think I can get past 98% without trap testing it.

[oscbyspro]

Hm. I have a single custom collection. It's really convenient, but I'm also tempted to remove it. Keep it simple.

[oscbyspro]

Turns out that it could be replaced with something much more lightweight 👀

[oscbyspro]

I was bored so I added these to the new and improved Fibonacci<T> sequence:

/// Forms the sequence pair at `index + other.index`.
public mutating func increment(by other: Self) throws

/// Forms the sequence pair at `index - other.index`.
public mutating func decrement(by other: Self) throws

---

/// Generates new instances and uses them to check math invariants.
///
/// ### Invariants
///
/// ```
/// f(x) * f(y) == (f(x+y+1) / f(x+1) - f(y+1)) * f(x+1) + f(x+y+1) % f(x+1)
/// ```
///
/// ### Calls: Fibonacci
///
/// - Fibonacci.init(\_:)
/// - Fibonacci/increment(by:)
/// - Fibonacci/decrement(by:)
///
/// ### Calls: BinaryInteger
///
/// - BinaryInteger/plus(\_:)
/// - BinaryInteger/minus(\_:)
/// - BinaryInteger/times(\_:)
/// - BinaryInteger/quotient(\_:)
/// - BinaryInteger/division(\_:)
///
func checkMathInvariants() {
    typealias Bad = FibonacciTests.Failure
    for divisor: Divisor<Value> in [2, 3, 5, 7, 11].map(Divisor.init) {
        always: do {
            var a = self.item as Fibonacci<Value>
            let b = try Fibonacci(a.index.quotient(divisor).prune(Bad.division))
            let c = try a.next.division(Divisor(b.next, prune:Bad.divisor)).prune(Bad.division)
            try a.decrement(by: b)
            let d = try b.element.times(a.element).prune(Bad.multiplication)
            let e = try c.quotient.minus(a.next).times(b.next).plus(c.remainder).prune(Bad.any)
            try a.increment(by: b)
            test.same(d, e, "arithmetic invariant error")
            self.same(index: a.index, element: a.element, next: a.next)
            
        }   catch let error {
            test.fail("unexpected arithmetic failure: \(error)")
        }
    }
}

[oscbyspro]

Hm. Looks like I'll need an ergonomic way of propagating Divisor/init failure, etc...

[oscbyspro]

Also, the divisor stuff is only for named methods. Operators just trap on failure.

[oscbyspro]

All (or most, I'd have to double-check) named methods are recoverable, though.

[oscbyspro]

Hm. Looks like I'll need an ergonomic way of propagating Divisor/init failure, etc...

Perhaps init<E>(_:prune:) throws(E) would be nice. It looks a lot like result.prune(_:).

[oscbyspro]

veto(_:) is cute. This is from the un/signed Fibonacci/decrement() method:

try index.minus(1).veto({ $0.isNegative }).prune(Failure.overflow)

[oscbyspro]

Unsigned values overflow in minus(_:) and return a constant in $0.isNegative.

[oscbyspro]

Hm. invalidated(_:) might be a better name, however. Keep it simple English.

[oscbyspro]

I changed it to veto(_:) again because it's just so nice, sweet, and to the point.

[oscbyspro]

God, save me from writing READMEs 😣

[oscbyspro]

Zzz. I think READMEs are the way to go because nobody looked at the other stuff. Here's what I have so far:

• Introduction
  • A rock-solid foundation
  • Keep stdlib extensions to a minimum
  • Derive all the things!
  • Recover all the things!
• Nomenclature
  • What is a binary integer?
  • What is a data integer?
  • What is a systems integer?
  • What is a trusted input?
• CoreKit
  • Validation and recovery through Fallible<Value>
  • Upsize binary integer elements with DataInt<U8>
  • Lightweight text decoding and encoding with TextInt
  • Type-safe bit casts with BitCastable<BitPattern>
  • Generic logic gates with BitOperable
  • More ones and zeros with Bit, Sign and Signum
• DoubleIntKit
  • A big systems integer
  • A non-recursive model
• InfiniIntKit
  • Recoverable infinite addition (+/-)
  • Recoverable infinite multiplication
  • Recoverable infinite division
• FibonacciKit
  • The Fibonacci<Value> sequence
  • Fast sequence addition (+/-)
  • Code coverage with sequence invariants
• Installation
  • SemVer 2.0.0
  • Swift Package Manager

[oscbyspro]

These are the protocols I have at the moment:

• BinaryInteger
• BitCastable
• BitOperable
• EdgyInteger
• SignedInteger
• Signedness
• SystemsInteger
• UnsignedInteger

Maybe I'll add endianness to the mix, dunno.
In either case, I'm quite happy with this list.

[oscbyspro]

Here's a cool piece of code:

var value = I8(0)
let error = value[raw: U8.self][{ $0.decremented() }]

print(value) // -1
print(error) // true

1. The 1st subscript reinterprets value through the type-safe BitCastable protocol.
2. The 2nd subscript turns a consuming method into a mutating method by destructuring the result.

The 2nd subscript cuts the project code in half, or some such silly amount.

Also, I've renamed init(bitPattern:) as init(raw:) because I use it a lot a lot a lot...

I'm now convinced that these two subscripts are anti-patterns, so I spent today removing them and all uses of them. The subscript(raw:) is too niche to consider on its own. The closure-based subscript(_:) is the bad one, really. It's such a good stop-gap that it hid the fact that I should have added some more extensions to improve all of the most common code patterns instead.

[oscbyspro]

These are both derived so anyone crazy enough can reinstate them in their own projects.

[oscbyspro]

Also, I just noticed that x-by-y addition should take an unsigned increment. This is because the bit pattern extension of signed increments negates the benefit of having a separate algorithm. I suppose I did not notice it before because 99% of all such calls are made by unsigned wide integers. Anyhow, that will be fixed.

[oscbyspro]

This is also true for multiplication with addition, by the way.

[oscbyspro]

It turns out that Fallible<Void> is a neat error indicator. It's a Bool with ergonomic features:

data.increment(by: 1).unwrap() // Fallible<Void> -> Void + precondition(!error)

[oscbyspro]

Made a division test case super generic for no reason ™️ and found a bug in my new Karatsuba algorithm. Love it and hate it.

[oscbyspro]

I ported a similar test from this project to the new project, for anyone curious:

extension InfiniIntTests {
    func testDivisionLongCodeCoverage() {
        func whereIs<T, S>(_ type: T.Type, _ source: S.Type) where T: BinaryInteger, S: SystemsInteger & UnsignedInteger {
            //=--------------------------------------=
            func make(_ source: [S]) -> T {
                source.withUnsafeBufferPointer({ T.exactly(DataInt($0)!, mode: .unsigned).unwrap() })
            }
            //=--------------------------------------=
            var dividend: T, divisor: T, quotient: T, remainder: T
            //=--------------------------------------=
            dividend  = make([ 0,  0,  0,  0,  0, ~0, ~0, ~0] as [S])
            divisor   = make([~0, ~0, ~0, ~0,  0,  0,  0,  0] as [S])
            quotient  = make([ 0, ~0, ~0, ~0,  0,  0,  0,  0] as [S])
            remainder = make([ 0, ~0, ~0, ~0,  0,  0,  0,  0] as [S])
            
            Test().division(dividend, divisor, quotient, remainder)
            //=--------------------------------------=
            dividend  = make([~0, ~0, ~0, ~0,  0, ~0, ~0, ~0] as [S])
            divisor   = make([~0, ~0, ~0, ~0,  0,  0,  0,  0] as [S])
            quotient  = make([ 1, ~0, ~0, ~0,  0,  0,  0,  0] as [S])
            remainder = make([ 0, ~0, ~0, ~0,  0,  0,  0,  0] as [S])
            
            Test().division(dividend, divisor, quotient, remainder)
        }
        
        /// 2024-05-15: the whereIs(InfiniInt<U8>.self, U64.self) case found a Karatsuba multiplication bug.
        for type in Self.types {
            for source in coreSystemsIntegersWhereIsUnsigned {
                whereIs(type, source)
            }
        }
    }
}

[oscbyspro]

Also, I struggled to find T.exactly(_:mode:) because I had not added the T.init(_:mode:) version.

[oscbyspro]

Note: the bug was found when checking the dividend == divisor &* quotient &+ remainder invariant.

[oscbyspro]

The new project is public now, at least in some kind of alpha state. It's called: Ultimathnum.