Skip to content

Instantly share code, notes, and snippets.

@fay59
Forked from jdh30/deriv.swift
Last active December 29, 2017 00:19
Show Gist options
  • Save fay59/ae33bb970a08632cfb2925e2049f9e7a to your computer and use it in GitHub Desktop.
Save fay59/ae33bb970a08632cfb2925e2049f9e7a to your computer and use it in GitHub Desktop.
Swift code to compute the nth derivative of x^x
precedencegroup ExponentPrecedence {
associativity: right
higherThan: MultiplicationPrecedence
}
infix operator **: ExponentPrecedence
fileprivate enum Expr: CustomStringConvertible {
case Int(n: Int)
indirect case Var(x: String)
indirect case Add(f: Expr, g: Expr)
indirect case Mul(f: Expr, g: Expr)
indirect case Pow(f: Expr, g: Expr)
indirect case Ln(f: Expr)
static let minusOne = Expr.Int(n: -1)
static let zero = Expr.Int(n: 0)
static let one = Expr.Int(n: 1)
var count: Int {
switch self {
case .Int, .Var: return 1
case let .Ln(f): return f.count
case let .Add(f, g), let .Mul(f, g), let .Pow(f, g):
return f.count + g.count
}
}
var description: String {
let n = self.count
return n > 100 ? "<<\(n)>>" : self.toString()
}
private func toString() -> String {
switch self {
case let .Int(n): return String(n)
case let .Var(x): return x
case let .Add(f, g): return "(\(f.toString()) + \(g.toString()))"
case let .Mul(f, g): return "(\(f.toString()) * \(g.toString()))"
case let .Pow(f, g): return "(\(f.toString())^\(g.toString()))"
case let .Ln(f): return "ln(\(f.toString()))"
}
}
}
fileprivate func +(_ f: Expr, _ g: Expr) -> Expr {
switch (f, g) {
case let (.Int(m), .Int(n)): return .Int(n: m + n)
case (.Int(0), _): return g
case (_, .Int(0)): return f
case (_, .Int): return g + f
case let (_, .Add(.Int(n), g)): return .Int(n: n) + (f + g)
case let (.Add(f, g), h): return f + (g + h)
default: return .Add(f: f, g: g)
}
}
fileprivate func *(f: Expr, g: Expr) -> Expr {
switch (f, g) {
case let (.Int(m), .Int(n)): return .Int(n: m * n)
case (.Int(0), _): return .zero
case (_, .Int(0)): return .zero
case (.Int(1), _): return g
case (_, .Int(1)): return f
case (_, .Int): return g * f
case let (_, .Mul(.Int(n), g)): return .Int(n: n) * (f * g)
case let (.Mul(f: f, g: g), h): return f * (g * h)
default: return .Mul(f: f, g: g)
}
}
fileprivate func **(_ left: Int, _ right: Int) -> Int {
switch right {
case 0: return 1
case 1: return left
default:
let c = left ** (right / 2)
return c * c * (right % 2 == 0 ? 1 : left)
}
}
fileprivate func **(f: Expr, g: Expr) -> Expr {
switch (f, g) {
case let (.Int(m), .Int(n)): return .Int(n: m ** n)
case (_, .Int(0)): return .one
case let (f, .Int(1)): return f
case (.Int(0), _): return .zero
default: return .Pow(f: f, g: g)
}
}
fileprivate func ln(_ f: Expr) -> Expr {
switch f {
case .Int(1) : return .zero
default: return .Ln(f: f)
}
}
fileprivate func d(_ x: String, _ f: Expr) -> Expr {
switch f {
case .Int: return .zero
case let .Var(y): return .Int(n: x == y ? 1 : 0)
case let .Add(f, g): return d(x, f) + d(x, g)
case let .Mul(f, g): return f * d(x, g) + g * d(x, f)
case let .Pow(f, g): return f ** g * (g * d(x, f) * (f ** .minusOne) + (ln(f) * d(x, g)))
case let .Ln(f): return d(x, f) * f ** .minusOne
}
}
fileprivate func main() {
let n = Int(CommandLine.arguments[1])!
let x = Expr.Var(x: "x")
var f = x ** x
for _ in 0..<n {
let df = d("x", f)
print("D(\(f)) = \(df)")
f = df
}
}
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment