A function farey such that farey(x) ≅ r where r is a rational number. Implemented using a binary search of Farey sequence

fareyAlgorithm.swift

import UIKit

let n = Double.pi
let r = farey(
    n: n,
    precision: 0.03)
r.inspect() // (22, 7)

r // 3.142857142857143
n // 3.141592653589793


struct Rational {
    init(_ n: Int, _ d: Int) {
        let (n, d) = Self.reduceIterativeEuklid(n, d: d)
        self.n = n
        self.d = d
    }

    let n: Int
    let d: Int

    static func &+ (left: Rational, right: Rational) -> Rational {
        return Rational(left.n + right.n, left.d + right.d)
    }

    static func - (lhs: Rational, rhs: Double) -> Double {
        return Double(lhs) - rhs
    }

    static func < (lhs: Rational, rhs: Double) -> Bool {
        return Double(lhs) < rhs
    }

    static func > (lhs: Rational, rhs: Double) -> Bool {
        return Double(lhs) > rhs
    }

    func inspect() -> (Int, Int) {
        return (n, d)
    }

    private static func reduceIterativeEuklid(_ n: Int, d: Int) -> (Int, Int) {
        var a: Int = 0
        var b: Int = max(n, d)
        var r: Int = min(n, d)

        while r != 0 {
            a = b
            b = r
            r = a % b
        }

        b
        return (n / b, d / b)
    }
}

extension Double {
    init(_ r: Rational) {
        self = Double(r.n) / Double(r.d)
    }
}

func farey(n: Double, precision: Double) -> Rational {
    return farey(n: n,
                precision: precision,
                min: Rational(Int(floor(n)), 1),
                max: Rational(Int(ceil(n)), 1))
}

func farey(n: Double, precision: Double, min: Rational, max: Rational) -> Rational {

    let mid = min &+ max

    let ld = mid - Double(min)
    let ud = max - Double(mid)

    if ld < precision || ud < precision {
        return mid
    }

    let result: Rational
    if n < Double(mid) {
        result = farey(n: n, precision: precision, min: min, max: mid)
    } else {
        result = farey(n: n, precision: precision, min: mid, max: max)
    }

    return result
}