[swift-evolution] Protocol-Oriented Number System

[Dan Kogai]

Folks,

Hi.  I just joined the list because I found this:

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002445.html

> Related:  I have been working for some time on a rewrite of all the integer types and protocols <
> https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb>.  One goal of this effort is to enable operations on mixed integer types, which as you can see is partially completed.  In-place arithmetic (anInt32 += aUInt64) is next.  Another important goal is to make the integer protocols actually useful for writing generic code, instead of what they are today: implementation artifacts used only for code sharing.  As another litmus test of the usefulness of the resulting protocols, the plan is to implement BigInt in terms of the generic operations defined on integers, and make BigInt itself conform to those protocols.

Not knowing this, I started writing what I call Protocol-Oriented Number System in Swift, or PONS for short.

<https://github.com/dankogai/swift-pons>

In PONS, BigInt is implemented exactly that way, purely in Swift.

Suppose you have:

    func fib<T:POInteger>(n:T)->T {
        if n < T(2) { return n }
        var (a, b) = (T(0), T(1))
        for _ in 2...n {
            (a, b) = (b, a+b)
        }
        return b
    }

You get this.

    let F11 = fib(11 as Int8)       // 89 as Int8
    let F13 = fib(13 as UInt8)      // 233 as UInt8
    let F23 = fib(23 as Int16)      // 28657 as Int16
    let F24 = fib(24 as UInt16)     // 46368 as UInt16
    let F46 = fib(46 as Int32)      // 1836311903 as Int32
    let F47 = fib(47 as UInt32)     // 2971215073 as UInt32
    let F92 = fib(92 as Int64)      // 7540113804746346429 as Int64
    let F93 = fib(93 as UInt64)     // 12200160415121876738 as UInt64

and of course,

    let F666 = fib(666 as BigInt)

and F666 = 6859356963880484413875401302176431788073214234535725264860437720157972142108894511264898366145528622543082646626140527097739556699078708088 as BigInt .  Yup.  Swift swallows the beast('s number) so easily.

It contains playground that lets you see it for yourself.

Because the 0th raison d'être of PONS is to bring protocol-oriented programming to numbers, BigInt is just a part of it.  It also comes with Rational with numerator and denominator in any signed integer and Complex either in integers (aka Gaussian integer) or "real" numbers -- not only Double and Float but also Rational.

Working on PONS is about 93.75% joy and 6.25% agony, with that 6.25% from swiftc puking Signal 11 (that happens rather often when I move codes from actual types to protocol extensions :-).

As for BigInt, it is far from the fastest arbitrary-precision integer on Earth but fast enough for my needs.  For one thing it can tell M127 (also happens to be Int128.max should it come) is a prime instantly.  Don't you dare try that on ruby with 'require "prime"' then "(2**127-1).prime?" :-?

And thanks to protocols it can be the denominator of Rational so I can go not just as big as I like but also as small as I like.

My heart aches a little to learn that the future Swift will definitely make PONS obsolete yet I am far more glad to report that Swift 2.1 already passed your -- our litmus test.  You got to see for yourself how beautiful litmus paper can be.

Dan the "Crusty" Swift Programmer