<div dir="ltr">Dear swift-evolution,<div><br></div><div>I less want to make concrete proposals than start a conversation about expanded numerical support in Swift. In that spirit, here are some thoughts:</div><div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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. <a href="https://www.mikeash.com/pyblog/friday-qa-2015-04-17-lets-build-swiftarray.html">https://www.mikeash.com/pyblog/friday-qa-2015-04-17-lets-build-swiftarray.html</a>). 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.</div><div><br></div><div>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:</div><div><br></div><div>enum Integer {</div><div><span class="" style="white-space:pre"> </span>case Small(Int)</div><div><span class="" style="white-space:pre"> </span>case Big(ArbitraryPrecisionInteger)</div><div>}</div><div><br></div><div>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.</div><div><br></div><div>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.)</div><div><br></div><div>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).</div><div><br></div><div>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.</div><div><br></div><div>Future topics to explore include complex numbers, arbitrary-precision floating-point numbers, and fixed-precision and/or decimal number types.</div><div><br></div><div>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.</div></div><div><br></div><div>Best regards,</div><div>Austin</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Dec 3, 2015 at 6:52 PM, Austin Zheng <span dir="ltr"><<a href="mailto:austinzheng@gmail.com" target="_blank">austinzheng@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Thanks, Chris and Dmitri! I will do some research and write something up over the weekend.<span class="HOEnZb"><font color="#888888"><div><br></div><div>Austin</div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Dec 3, 2015 at 2:24 PM, Dmitri Gribenko <span dir="ltr"><<a href="mailto:gribozavr@gmail.com" target="_blank">gribozavr@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On Thu, Dec 3, 2015 at 1:14 PM, Austin Zheng <<a href="mailto:austinzheng@gmail.com" target="_blank">austinzheng@gmail.com</a>> wrote:<br>
><br>
> Hi all,<br>
><br>
> 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.<br>
<br>
><br>
> 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?<br>
<br>
</span>Hi Austin,<br>
<br>
We are interested in improving our numerics support, and we are<br>
definitely interested in hearing your ideas in this space. You don't<br>
have to write a full proposal though. Just an extended email to<br>
swift-evolution would be a good start.<br>
<br>
You can find the current prototype for library support for integers<br>
here: <a href="https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb" rel="noreferrer" target="_blank">https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb</a><br>
<span><font color="#888888"><br>
Dmitri<br>
<br>
--<br>
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if<br>
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <<a href="mailto:gribozavr@gmail.com" target="_blank">gribozavr@gmail.com</a>>*/<br>
</font></span></blockquote></div><br></div>
</div></div></blockquote></div><br></div>