[swift-evolution] Protocol-Oriented Number System

[Dave Abrahams]

on Wed Feb 10 2016, Dan Kogai <swift-evolution at swift.org> wrote:

> 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

Dan, this is supercool.  Max Moiseev has taken over the integer effort,
and Steve Canon has been working on the same kinds of changes for
floating point; it would be fantastic if you could work together with
them to ensure that PONS can be built atop our new protocols.

Thanks!

P.S. if you're interested in generic mixed-precision arithmetic, there's
also https://gist.github.com/dabrahams/ddeda3fbf919f71593d1, which could
be seen as a foundation for building BigInt and others.  (The reason for
making it all so generic is so that it could be exhaustively tested with
small units of precision).  But I wouldn't spend too much energy digging
into this code...

-- 
-Dave