STRANGE LOOP 2012

What is Spire?

A numeric library for Scala.

Intended to be generic, fast, and precise.

Motivations

Generic numeric programming?

// direct
def gcd(a: Int, b: Int): Int =
 if (a % b == 0) b else gcd(b, a % b)


// scala generics
def gcd[A: Integral](a: A, b: A): A =
 if (a % b == implicitly[Integral[A]].zero) b else gcd(b, a % b)


// spire!
def gcd[@spec A: Integral](a: A, b: A): A =
 if (a % b === Integral[A].zero) b else gcd(b, a % b)
    

How do Scala's generics perform?

Separating precision from algorithm

...for when you can't employ a team of numerical analysts!

Separating precision from algorithm

...for when you can't employ a team of numerical analysts!

def mean[@spec A: Fractional](ns: Array[A]) =
  ns.qsum / Fractional[A].fromInt(ns.size)
    

Separating precision from algorithm

...for when you can't employ a team of numerical analysts!

def mean[@spec A: Fractional](ns: Array[A]) =
  ns.qsum / Fractional[A].fromInt(ns.size)



scala> mean[Double](Array(1e20, 1, -1e20))
res0: 0.0

scala> mean[BigDecimal](Array(1e20, 1, -1e20))
res1: BigDecimal(0.333...)
    

More precision problems

scala> 363.sqrt - 300.sqrt - 3.sqrt
    

More precision problems

scala> 363.sqrt - 300.sqrt - 3.sqrt

Double = -2.220446049250313E-15
    

More precision problems

scala> 363.sqrt - 300.sqrt - 3.sqrt

Double = -2.220446049250313E-15

BigDecimal = 
-8E-33   //       default precision
    

More precision problems

scala> 363.sqrt - 300.sqrt - 3.sqrt

Double = -2.220446049250313E-15

BigDecimal = 
-8E-33   //       default precision
-6E-99   //    100 digits precision
 2E-99   //  1'000 digits precision
-2E-9999 // 10'000 digits precision
    

Esoteric bullshit

// ok
(33.2).floor

// missing
BigDecimal(33.0).floor
    

Esoteric bullshit

// ok
(33.6).round

// won't compile
BigDecimal(33.6).round

// blech
BigDecimal(33.6).round(new java.lang.MathContext(128))

// oops
5e100.round -> 9223372036854775807L
    

Esoteric bullshit

// great
BigDecimal(2.2) pow 3

// ugly
math.pow(2.0, 3.0)

// these aren't the longs you're looking for
math.pow(19L, 3L) -> 6859.0

// too bad
BigDecimal(3.1) pow 2.5 // too bad
    

Esoteric bullshit

// ugly but useful
math.cbrt(12345.0)
math.sqrt(12345.0)

// nope
BigDecimal(12345.0).cbrt
math.cbrt(BigDecimal(12345.0))

// sorry
BigDecimal(12345.0).sqrt
math.sqrt(BigDecimal(12345.0))
    

Esoteric bullshit

// ugly but works
math.log(54321.0)

// nope, fail
BigDecimal(54321).log
math.log(BigDecimal(54321))

// don't even think about trigonometry!
    

Implementation

Typeclasses

Modular, ad-hoc polymorphism, including over primitive types.

Encoded using Scala's system of implicits.

Specialization + Macros

Scala can classes and methods on generic type parameters.

Like C++ templates but at definition site, and other differences.

Specialization + Macros

def mySum[@spec A:Ring](ns: List[A], total:A): A =
 ns match {
  case n :: ns => mySum(ns, total + n)
  case Nil => total
 }

mySum[Int](ns, 0)
    

Specialization + Macros

def mySum$mIc$sp(ns: List[Int], total:Int)
 (implicit ev:Ring$mcI$sp): Int =
  ns match {
   case n :: ns => mySum(ns, new RingOps(total)(ev).+(n))
   case Nil => total
  }

mySum$mIc$sp(ns, 0)(Ring.IntIsRing)
    

Specialization + Macros

def mySum$mIc$sp(ns: List[Int], total:Int)
 (implicit ev:Ring$mcI$sp): Int =
  ns match {
   case n :: ns => mySum(ns, ev.plus(total, n))
   case Nil => total
  }

mySum$mIc$sp(ns, 0)(Ring.IntIsRing)
    

Rational

Exact (closed) for all field operations.

Rational

Exact (closed) for all field operations.

scala> mean[Rational](List(1e20, 1, -1e20))
res0: spire.math.Rational = 1/3
    

Rational

Why implement another rational type in Java?

Because Aprational is sloooooooow!

Summing 100 rationals is 5'148x faster in Spire than Aprational.

Rational

Rational's SafeLong is a good compromise of speed + precision.

Real

Lazily-computed number type for arbitrary precision.

Exact(*) for fields and k-roots...

Real

Lazily-computed number type for arbitrary precision.

Exact(*) for fields and k-roots...

scala> Real(363).sqrt - Real(300).sqrt - Real(3).sqrt
res0: spire.math.Real = 0
    

Real

def distance(x: Real, y: Real): Real =
 ((x ** 2) + (y ** 2)).sqrt

// rational literals using macros!
val d = distance(r"33/2", r"16/3")

// rough approximation
val approx = d +/- 1e-10

// finer approximation using default math context
val huge = d.toBigDecimal
    

Real

1. On Guaranteed Accuracy Computation.
   C. K. Yap.
2. A Separation Bound for Real Algebraic Expressions.
   C. Burnikel, et al.
3. A New Constructive Root Bound for Algebraic Expressions.
   C. Li and C. Yap.

More types!

• Complex[A]
• Interval[A]
• boxed Number

More features!

• Literal number syntax macros
• Specialized sorting, summation, etc
• Optimized cfor macro
• Precise pow for Long
• Trig, log, k-roots for BigDecimal(*)

Get Involved!

MIT license

Code available at Github.

Release coming soon for Scala 2.10.0!

"Now with 100% more homepage!"

The End