// AdvPrPa series 1, written by Jämes Ménétrey
// Master in Engineering, University of Applied Sciences and Arts Western Switzerland

import scala.annotation.tailrec

//
// n-th root estimation
//

val epsilon = 0.0001

def abs(x: Double) = if (x < 0) -x else x
def isGoodEnough(x: Double, y: Double) = abs(x - y) < epsilon

// Only for e in [1;Inf[
def pow(x: Double, e: Int) = {
  require(x > 0)

  1.to(e).foldLeft[Double](1)((acc, _) => acc * x)
}


// The square root can be defined as x in x^2 = y. It can be rewritten f(x, y) = x^2 - y and Newton's method
// helps to find the zero of that function, using its partial derivative form on x: f'(x, y) = 2x.
// The problem can be generalized as f(x, y) = x^e - y and f'(x, y) = e * x^(e-1).
def nthRoot(n: Double, e: Int = 2): Double = {
  def f(xi: Double) = pow(xi, e) - n
  def df(xi: Double) = e * pow(xi, e - 1)

  @tailrec
  def improve(xi: Double): Double = xi - f(xi) / df(xi) match {
    case xj if isGoodEnough(xi, xj) => xj
    case xj => improve(xj)
  }

  improve(10)
}

println(s"Square root of 16: ${nthRoot(16)}")
println(s"4-th root of 16: ${nthRoot(16, 4)}")
println(s"3-th root of 27: ${nthRoot(27, 3)}")