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@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@gmail.com> > wrote:
On Thu, Dec 3, 2015 at 1:14 PM, Austin Zheng <austinzheng@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@gmail.com>*/