Protocol-Oriented Number System

Evolution Discussion
1

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&gt;\. 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&gt;

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

2

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 Work in progress · GitHub, 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...

···

on Wed Feb 10 2016, Dan Kogai <swift-evolution@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&gt;\.

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&gt;

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

--
-Dave