[swift-evolution] Epic: Typesafe calculations

[Stephen Canon]

Even with cancellation, the number of bits required to represent the exact terms involved in computing the inverse grow like O(n log n) in the typical case, IIRC.  So exact arithmetic rapidly becomes unfeasible for even modestly large matrices.

Aside from purely symbolic matrices that come up in theoretical physics and matrices over finite fields, the entries of a matrix are rarely known exactly, so the rich set of approximate-rank-revealing and numerically stable methods that we have for floating-point turn out to be much more useful anyway.

That’s not to say that it isn’t fun to play around with these concepts, of course =)

– Steve

> On Jan 13, 2016, at 11:27 PM, Matt Whiteside <mwhiteside.dev at gmail.com> wrote:
> 
> 
>> On Jan 13, 2016, at 11:16, Stephen Canon <scanon at apple.com <mailto:scanon at apple.com>> wrote:
>> 
>> … in exact arithmetic, not in floating-point, which is what people tend to actually use for matrices.  For that matter, the entire notion of “invertible” as a binary attribute is problematic when dealing with approximate arithmetic; a matrix may be formally invertible but so ill-conditioned that the result is effectively meaningless.
>> 
>> Not really trying to shoot you down, just observing that this is an extremely subtle example with lots of hidden sharp edges.
>> 
>> – Steve
> 
> That’s a good point.  So then I wonder if exact arithmetic wouldn’t be good enough for a lot of entry level math & science applications, especially the ones where this type of approach would come to mind in the first place.
> 
> Something like,
> 
> struct Rational:CustomDebugStringConvertible{
> 	let numerator, denominator: Int
> 	var debugDescription:String{
> 	  get{
> 	   return "\(Double(numerator)/Double(denominator))"
> 	    }
> 	}
> }
> 
> func *(lhs:Rational,rhs:Rational) -> Rational{
>   return Rational(numerator: lhs.numerator*rhs.numerator, 
>                 denominator: lhs.denominator * rhs.denominator)
> }
> 
> func *(lhs:Int,rhs:Rational) -> Rational{
>   return Rational(numerator: lhs*rhs.numerator, 
>                 denominator: rhs.denominator)
> }
> 
> let π = Rational(numerator: 355, denominator: 113)
> let two_π = 2 * π
> 
> 
> might get you pretty far with 64 bits.
> 
> Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160114/530c5c10/attachment.html>