STRANGE LOOP 2012

Spire

Better Numerics for Scala

Erik Osheim (@d6) and Tom Switzer (@tixxit)

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?

Benchmarks using Caliper with 1M iterations/elements

slowdown vs direct code
benchmarkscala.mathspire.math
pairwise add14.51.0
increment18'674'145.0(*)1.0
min/max4.81.0
gcd1.61.0
scale4.91.0

* This is not a typo!

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!

More features!

Get Involved!

MIT license

Code available at Github.

Release coming soon for Scala 2.10.0!

"Now with 100% more homepage!"

The End