Skip to content

Instantly share code, notes, and snippets.

@non
Last active Aug 29, 2015
Embed
What would you like to do?
Fun little program to display N digits of Pi in any base (2-36) using Spire.
// this is the build file used to compile piday.scala
name := "piday"
scalaVersion := "2.10.3"
libraryDependencies += "org.spire-math" %% "spire" % "0.7.3"
package piday
import scala.util.Try
import spire.math._
import spire.syntax.order._
object PiDay {
// we can support bases 2 - 36.
val digits36 = "0123456789abcdefghijklmnopqrstuvwxyz"
/**
* Display the first n digits of any real number in base using beta
* expansion.
*
* Base is required to be a real number (1 < base <= 36).
*/
def beta(x: Real, base: Real, n: Int): String = {
// find k such that base.pow(k) <= x < base.pow(k + 1)
// this helps figure out "where" the most significant digit its.
var k = 0
while (x / base.pow(k) >= base) k += 1
// perform beta reduction to find all the digits
def loop(k: Int, i: Int, dk: Real, rk: Real, acc: String): String = {
val xj = base * rk
val dj = xj.floor
val rj = xj - dj
val c = digits36.charAt(dk.toInt)
val acc2 = if (k == 0) acc + "." + c else acc + c
val k2 = if (k == -1) -1 else k - 1
if (i == 0) acc2
else loop(k2, i - 1, dj, rj, acc2)
}
// find the most significant digit (dk) and get things started.
val xk = x / base.pow(k)
val dk = xk.floor
val rk = xk - dk
loop(k + 1, n, dk, rk, "")
}
/**
* Display the first n digits of any real number in any base 2-36.
*/
def display(real: Real, base: Int, n: Int): String = {
if (base < 2 || 36 < base || n < 1) return "error"
// figure which digits to use in our repr, and how many bits we need
val digits = digits36.substring(0, base)
val bitsPerDigit = log(base) / log(2)
val bits = spire.math.ceil((n + 2) * bitsPerDigit).toInt
// we can multiply by base^n to get a whole number we work with.
// this is a bit janky but easy to reason about.
val r = Rational(real(bits) * SafeLong(base).pow(n), SafeLong(2).pow(bits))
val m = SafeLong(r.floor.toBigInt)
/**
* Use quotmod (/%) to get the next digit in base as well as the
* quotient. We just do this repeatedly until we hit zero.
*
* m must be positive for this to work. For negative numbers, just
* negate them and slap a "-" on the front.
*/
def loop(i: Int, m: SafeLong, ds: List[Char]): String =
if (m == 0) {
ds.mkString
} else {
val (q, r) = m /% base
val c = digits.charAt(r.toInt)
if (i > 0) loop(i - 1, q, c :: ds)
else if (i == 0) loop(-1, q, c :: '.' :: ds)
else loop(-1, q, c :: ds)
}
// let's start dividing like a champ!
if (m < 0) "-" + loop(n, -m, Nil) else loop(n, m, Nil)
}
/**
* The main method is ineveitably the ugliest part of any program.
*/
def main(args: Array[String]): Unit = {
val reals = Map("sqrt2" -> Real(2).sqrt, "e" -> Real.e, "pi" -> Real.pi)
def parse(s: String, d: Real): Real =
Try(reals.getOrElse(s, Real(s))).getOrElse(d)
def parseInt(s: String, d: Int): Int =
Try(s.toInt).getOrElse(d)
val x = parse(args(0), Real.pi)
val base = parse(args(1), Real(10))
val n = parseInt(args(2), 40)
val s = if (base.isValidInt) {
display(x, base.toInt, n)
} else {
beta(x, base, n)
}
println(s)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment