kyodai_in_scala.md

巨大数 in Scala

@kuzuha よりネタ投下していただいたので、Scalaで実装してみた。

ネタ元: 裏サンデー | 寿司 虚空編 | 第1話

import scala.annotation.tailrec

class BigDecimalOps(self: BigDecimal) {

  private def pow(b: BigDecimal, p: BigDecimal): BigDecimal = {
    @tailrec
    def pow0(result: BigDecimal, c: BigDecimal): BigDecimal = {
      if (c == BigDecimal(0)) result else pow0(result * b, c - 1)
    }
    pow0(b, p - 1)
  }

  private def fill(n: BigDecimal)(v: => BigDecimal): List[BigDecimal] = {
    @tailrec
    def fill0(result: List[BigDecimal], n: BigDecimal): List[BigDecimal] = 
      if (n == BigDecimal(0)) result else fill0(v :: result, n - 1)
    fill0(List.empty, n)
  }

  private def tower1(d: BigDecimal, n: BigDecimal) = pow(d, n)
  private def tower2(d: BigDecimal, n: BigDecimal) = fill(n)(tower1(d, n)).reduceRight(pow(_, _))
  private def tower3(d: BigDecimal, n: BigDecimal) = fill(n)(tower2(d, n)).reduceRight(pow(_, _))

  def ↑(n: BigDecimal): BigDecimal = tower1(self, n)
  def ↑↑(n: BigDecimal): BigDecimal = tower2(self, n)
  def ↑↑↑(n: BigDecimal): BigDecimal = tower3(self, n)

}

object BigDecimalOps {
  implicit def toBigDecimalOps(self: BigDecimal) = new BigDecimalOps(self)
  implicit def fromIntToBigDecimalOps(self: Int) = new BigDecimalOps(BigDecimal(self))
}

object Main extends App {

  import BigDecimalOps._

  // BigDecimal
  println("BigDecimal(3) ↑ BigDecimal(2) = " + BigDecimal(3) ↑ BigDecimal(2))
  println("BigDecimal(3) ↑↑ BigDecimal(2) = " + BigDecimal(3) ↑↑ BigDecimal(2))
  try {
    println("BigDecimal(3) ↑↑↑ BigDecimal(2) = " + BigDecimal(3) ↑↑↑ BigDecimal(2))
  } catch {
    case ex: Exception => ex.printStackTrace()
  }

  // Intでも
  println("3 ↑ 2 = " + 3 ↑ 2)
  println("3 ↑↑ 2 = " + 3 ↑↑ 2)
  try {
    println("3 ↑↑↑ 2 = " + 3 ↑↑↑ 2)
  } catch {
    case ex: Exception => ex.printStackTrace()
  }
}

• 動かし方

$ brew install scala
$ # 上のソースコードをBigValue.scalaとして保存
$ scalac BigValue.scala # コンパイル
$ scala Main # 実行

• 実行結果

うひゃー、JVMではだめかーって感じっぽい。

3 ↑ 2 = 9

3 ↑↑ 2 = 387420489

// 3 ↑↑ 3 
java.lang.ArithmeticException: Overflow
	at java.math.BigDecimal.checkScale(BigDecimal.java:3691)
	at java.math.BigDecimal.doRound(BigDecimal.java:3749)
	at java.math.BigDecimal.multiply(BigDecimal.java:1348)
	at scala.math.BigDecimal.$times(BigDecimal.scala:252)
	at BigDecimalOps.pow0$1(b.scala:9)
	at BigDecimalOps.BigDecimalOps$$pow(b.scala:11)
	at BigDecimalOps$$anonfun$tower3$2.apply(b.scala:23)
	at BigDecimalOps$$anonfun$tower3$2.apply(b.scala:23)
	at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131)
	at scala.collection.immutable.List.reduceRight(List.scala:84)
	at BigDecimalOps.tower3(b.scala:23)