Make DoubleInt great again!

[oscbyspro]

So I wanted to see the difference (#31) makes on DoubleInt, and the difference is great. Then I compared it against my predecessor project and that one still performs divisions faster. Sigh. I haven't yet gotten around to optimizing the new abstraction, although I suppose (#31) is a step in the right direction.

---

Edit: Ultimathnum.U256 is faster if I set its integer literal to Int or Element.

---

final class Benchmarks: XCTestCase {

    /// ###### 2024-07-05 (MacBook Pro, 13-inch, M1, 2020):
    ///
    /// - `0.36 seconds`
    ///
    func testNumberick256() {
        let fib369: UInt256 = "58472848379039952684853851736901133239741266891456844557261755914039063645794"
        let fib370: UInt256 = "94611056096305838013295371573764256526437182762229865607320618320601813254535"

        for _ in 0 ..< 369 * 100 {
            var lhs = blackHoleIdentity(fib369)
            var rhs = blackHoleIdentity(fib370)
            var counter = 0

            dividing: while !rhs.isZero {
                counter += 1
                (lhs, rhs) = (rhs, lhs.remainderReportingOverflow(dividingBy: rhs).partialValue)
            }

            precondition(lhs == 1)
            precondition(rhs == 0)
            precondition(counter == 369)
        }
    }

    /// ###### 2024-07-05 (MacBook Pro, 13-inch, M1, 2020):
    ///
    /// - `1.67 seconds`
    /// - `0.88 seconds` with pointer-bit shifts
    /// - `0.31 seconds` with pointer-bit shifts and literals
    ///
    func testUltimathnum256() {
        let fib369 = U256("58472848379039952684853851736901133239741266891456844557261755914039063645794")!
        let fib370 = U256("94611056096305838013295371573764256526437182762229865607320618320601813254535")!

        for _ in 0 ..< 369 * 100 {
            var lhs = blackHoleIdentity(fib369)
            var rhs = blackHoleIdentity(fib370)
            var counter = 0

            dividing: while !rhs.isZero {
                counter += 1
                (lhs, rhs) = (rhs, lhs.remainder(Divisor(unchecked: rhs)))
            }

            precondition(lhs == 1)
            precondition(rhs == 0)
            precondition(counter == 369)
        }
    }
}

[oscbyspro]

The GCD of a Fibonacci sequence pair is not the best thing to benchmark, but still.

[oscbyspro]

But Ultimathnum.UXL is a bit faster than Numberick.UIntXL :smiley:

[oscbyspro]

I profiled it and discovered that the integer literals are slow :rofl:

Edit: Ultimathnum.U256 is faster if I set its integer literal to Int.

[oscbyspro]

A) Swift.Int literal takes it to ~300ms. B) RootInt/entropy() <= IX.size fast path takes it to ~400ms.

[oscbyspro]

I suppose another way of solving is by meticulously calling fast initializers instead of using integer literals, but that would be a downgrade in terms of ergonomics. It's just so silly that integer literals may resolve at runtime.

[oscbyspro]

Turns out that there's still some division improvements to make too. Instead of:

normalization.value >= Base.size // normalization is Shift<Self>

I can guard-cast it to a half-shift and then continue by using half-shift methods:

guard let normalization = Shift<Base>(exactly: normalization.value) else { ... }

[oscbyspro]

Hm. I can get to ~340ms by writing things like: init(load: 0 as Element.Magnitude).

[oscbyspro]

I changed the integer literal type to Element.IntegerLiteralType for the time being.