[swift-evolution] Expanded support for numeric types in stdlib?

[Austin Zheng]

Dear swift-evolution,

I less want to make concrete proposals than start a conversation about
expanded numerical support in Swift. In that spirit, here are some thoughts:

Arbitrary-precision integers (bigints) are a logical first step. Bigints
then enable practical support for rationals. (With bigints, rational
operations need not fail because of integer overflow.) Adding at least
these two numerical types would bring Swift far closer wrt numerical
support wrt languages like Clojure or Ruby.

Many languages make a distinction between fixed precision integers and
bigints (i.e. Haskell's Int vs Integer). I propose the definition of two
related types: ArbitraryPrecisionInteger and Integer.

ArbitraryPrecisionInteger is a struct wrapping a pointer to a byte buffer,
much like how Swift's Array, Set, and Dictionary collection types work
(c.f.
https://www.mikeash.com/pyblog/friday-qa-2015-04-17-lets-build-swiftarray.html).
It wraps an arbitrarily large integer within a container adhering to value
semantics. Perhaps this can be exposed as part of the stdlib, or a
'private' implementation detail.

Integer is intended to be used by application developers, and most of the
arithmetic/comparison functionality exposed by the stdlib deals with
arguments and return values of type Integer. Integers are enums:

enum Integer {
case Small(Int)
case Big(ArbitraryPrecisionInteger)
}

Like ArbitraryPrecisionInteger, Integer represents an arbitrary-precision
integer. It wraps either a fixed-size (64-bit) signed integer, or a bigint.
Integer's invariant is that integers within the range of an Int are always
stored as an Int. This is enforced by the mathematical operations defined
on arguments of type Integer. This allows for a slow path (consisting of
operations that are conducted on ArbitraryPrecisionIntegers), and a fast
path (consisting of checked operations on Ints, with automatic promotion to
ArbitraryPrecisionInteger as necessary). Fast path operations, in the best
case, need not allocate heap memory or invoke retain/release operations.

Integers can be unconditionally constructed (promoted) from Ints, and can
be conditionally demoted to Ints ( () -> Int? ). (All Ints are Integers,
but not all Integers are Ints.)

A useful compiler support feature might be a "BigIntegerLiteralConvertible"
protocol, which allows literal integers out of the range of Ints to be
assigned to Integer values. Swift can already tell if an integer literal is
out of range (e.g. "let x : Int8 = 123456"), so there is some precedent.
This would be a more elegant solution than requiring bigints to be
initialized via strings (as some other arbitrary precision arithmetic
libraries do).

Rational numbers are represented by the Rational struct which encapsulates
two Integers, the numerator and denominator. Rationals can be conditionally
constructed explicitly from two Integers (as long as the denominator isn't
0), or from a single Integer (all Integers are Rationals, but the opposite
is not true). A good invariant for Rationals might be having them always
represented in the most simplified form - for example, Rational(2, 6)
should be represented internally as 1/3 when constructed.

Future topics to explore include complex numbers, arbitrary-precision
floating-point numbers, and fixed-precision and/or decimal number types.

Given that I'm little more than a dabbler in these topics (most of my
expertise came from trying to reverse-assemble Clojure's numerical
support), feedback from someone with experience and/or expertise wrt
numerical/scientific computing, bignum libraries, numerical towers, etc.
would be hugely appreciated.

Best regards,
Austin


On Thu, Dec 3, 2015 at 6:52 PM, Austin Zheng <austinzheng at gmail.com> wrote:

> Thanks, Chris and Dmitri! I will do some research and write something up
> over the weekend.
>
> Austin
>
> On Thu, Dec 3, 2015 at 2:24 PM, Dmitri Gribenko <gribozavr at gmail.com>
> wrote:
>
>> On Thu, Dec 3, 2015 at 1:14 PM, Austin Zheng <austinzheng at gmail.com>
>> wrote:
>> >
>> > Hi all,
>> >
>> > There are quite a few programming languages that provide support for
>> numeric types apart from the customary floating-point and fixed-width
>> integer types. Prominent examples of additional numeric types include
>> rational numbers, arbitrary-width integer types, and fixed-point numbers.
>> Many of these numeric types are applicable to a wide variety of problem
>> domains.
>>
>> >
>> > Swift seems like it would be a good fit for stdlib implementation of
>> some of these numeric types. Structs and value semantics, literal
>> initialization, and operator overloading would allow such types to be
>> treated as first-class citizens. Is the community amenable to such a
>> proposal, which would entail the data structures themselves, arithmetic
>> operations, and interoperation between different numeric types to form a
>> numerical tower of sorts?
>>
>> Hi Austin,
>>
>> We are interested in improving our numerics support, and we are
>> definitely interested in hearing your ideas in this space.  You don't
>> have to write a full proposal though.  Just an extended email to
>> swift-evolution would be a good start.
>>
>> You can find the current prototype for library support for integers
>> here:
>> https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb
>>
>> Dmitri
>>
>> --
>> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
>> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151203/c8c3026e/attachment.html>