Scala: π and Streams

I finished my course of "Functional Programming Principles in Scala" at coursera¹.

Go me!

Wikipedia³ has an article on how to compute π. The series is provided below (using MathML², which might not work as it should in some browsers) originally proposed by Srinivasa Ramanujan.

$$\frac{1}{\mathrm{\pi }}=\frac{2\sqrt{2}}{9801}{\displaystyle \sum _{k=0}^{\infty }\frac{\left(4k\right)!\left(1103+26390k\right)}{{\left(k!\right)}^4{\mathrm{396}}^{4k}}}$$

Factorial

To compute the equation above, I'm going to use BigDecimals⁵ and I shall have to define some math operations.

So let us start with the Scala version of Factorial, which is equivalent to the Java Version of Factorial of my earlier blog post⁴.

Notes on Scala

I really like how Scala almost always infers the correct type automatically and can redefine common math operators for classes like BigDecimal. When dealing with BigDecimals, this is great. It makes it ideal for DSL, Domain Specific Languages. Compare the factorial calculation with BigDecimals below in Java and Scala for example:

Java:
return factorial(accumulator.multiply(n), n.subtract(BigDecimal.ONE));

Scala:
factorial(accumulator * n, n - 1)

I also like the fact I can define Worksheets in Scala, that are evaluated by the IDE upon saving, printing the results at the end of the line. For mathematicians it's the computerized equivalent of paper napkins in Restaurant, only better.

Square Root

There is a Square Root function available in the math library of Scala⁶, but it doesn't work with BigDecimals (def sqrt(x: Double): Double).

A way to compute a square root is using "Heron's method"⁷. That one can also be defined using recursion, similar to the Factorial above.

It is quite obvious that there is a problem in the code above. It is recursive, and the recursion never stops, leading sooner or later to a nice StackOverflow Error.

Some ways to solve it is to limit the number of iterations, or stop once the precision is adequate. An example of the first is seen below, where the number of iterations is 100.

But, it is slightly ugly. During the course, I learned that Scala tries to adhere to the Rules of Mathematics more than to the Rules of Programming. We should be able to define a pure function, without having the computer explode.

Streams

Scala has several ways in which functions get evaluated:

strict evaluation

Functions get evaluated immediately. For normal parameters and val definitions. This is the default.

lazy evaluation

Functions get evaluated when the function is called for the first time, and the value is cached and not recomputed.

by-name evaluation

Functions get evaluated each time the function is called. For "def" functions.

Streams are a way of creating data structures that are not evaluated immediately. An example of the use is shown in the following implementation of squareRoot:
The above example, barring the Stream calls, is equivalent to the first example of the squareRoot. Thusly we have defined something much more equivalent to an infinite series.

As you can see squareRoot(2) will get evaluated to Stream(1, ?). So only the head is evaluated, the first guess, and the rest is deferred, visible by means of a "?".

In order to force the evaluation of the rest, you can try for example squareRoot(2).take(5).toList, where take creates a new Stream that has a fixed length of 5. The toList forces the evaluation, as a list only knowns strict evaluation.

Now we should have all the ingredients to implement the equation visible at the top of this blog.

Computing π

In the example above, the actual number of terms in the series is 5, which is sufficient as the series converges extraordinarily rapidly to π.

In the example above, we are also using our new squareRoot function, this time with the number of iterations set to 120.

Of course, actually producing the exact result is impossible, but in Mathematics, I find that in most cases the definition is the important part, in order to reason about it.

References

[1] Coursera - Functional Programming Principles in Scala

https://class.coursera.org/progfun-004

[2] MathML

http://www.w3.org/Math/

[3] Wikipedia - Approximations of π

http://en.wikipedia.org/wiki/Approximations_of_%CF%80

[4] Recursive Factorial in Java

http://randomthoughtsonjavaprogramming.blogspot.nl/2014/05/tail-recursion.html

[5] scala.math.BigDecimal

http://www.scala-lang.org/api/current/index.html#scala.math.BigDecimal

[6] Scala Math Package

http://www.scala-lang.org/api/current/index.html#scala.math.package

[7] Wikipedia - Methods of computing square root

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Wikipedia - Arbitrary precision arithmetic

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic