Decimal to Fraction conversion in Swift

I am building a calculator and want it to automatically convert every decimal into a fraction. So if the user calculates an expression for which the answer is "0.333333...", it would return "1/3". For "0.25" it would return "1/4". Using GCD, as found here (Decimal to fraction conversion), I have figured out how to convert any rational, terminating decimal into a decimal, but this does not work on any decimal that repeats (like .333333).

Every other function for this on stack overflow is in Objective-C. But I need a function in my swift app! So a translated version of this (https://stackoverflow.com/a/13430237/5700898) would be nice!

Any ideas or solutions on how to convert a rational or repeating/irrational decimal to a fraction (i.e. convert "0.1764705882..." to 3/17) would be great!

If you want to display the results of calculations as rational numbers then the only 100% correct solution is to use rational arithmetic throughout all calculations, i.e. all intermediate values are stored as a pair of integers (numerator, denominator), and all additions, multiplications, divisions, etc are done using the rules for rational numbers.

As soon as a result is assigned to a binary floating point number such as Double, information is lost. For example,

let x : Double = 7/10

stores in x an approximation of 0.7, because that number cannot be represented exactly as a Double. From

print(String(format:"%a", x)) // 0x1.6666666666666p-1

one can see that x holds the value

0x16666666666666 * 2^(-53) = 6305039478318694 / 9007199254740992
                           ≈ 0.69999999999999995559107901499373838305

So a correct representation of x as a rational number would be 6305039478318694 / 9007199254740992, but that is of course not what you expect. What you expect is 7/10, but there is another problem:

let x : Double = 69999999999999996/100000000000000000

assigns exactly the same value to x, it is indistinguishable from 0.7 within the precision of a Double.

So should x be displayed as 7/10 or as 69999999999999996/100000000000000000 ?

As said above, using rational arithmetic would be the perfect solution. If that is not viable, then you can convert the Double back to a rational number with a given precision. (The following is taken from Algorithm for LCM of doubles in Swift.)

Continued Fractions are an efficient method to create a (finite or infinite) sequence of fractions h_n/k_n that are arbitrary good approximations to a given real number x, and here is a possible implementation in Swift:

typealias Rational = (num : Int, den : Int)

func rationalApproximationOf(x0 : Double, withPrecision eps : Double = 1.0E-6) -> Rational {
    var x = x0
    var a = floor(x)
    var (h1, k1, h, k) = (1, 0, Int(a), 1)

    while x - a > eps * Double(k) * Double(k) {
        x = 1.0/(x - a)
        a = floor(x)
        (h1, k1, h, k) = (h, k, h1 + Int(a) * h, k1 + Int(a) * k)
    }
    return (h, k)
}

Examples:

rationalApproximationOf(0.333333) // (1, 3)
rationalApproximationOf(0.25)     // (1, 4)
rationalApproximationOf(0.1764705882) // (3, 17)

The default precision is 1.0E-6, but you can adjust that to your needs:

rationalApproximationOf(0.142857) // (1, 7)
rationalApproximationOf(0.142857, withPrecision: 1.0E-10) // (142857, 1000000)

rationalApproximationOf(M_PI) // (355, 113)
rationalApproximationOf(M_PI, withPrecision: 1.0E-7) // (103993, 33102)
rationalApproximationOf(M_PI, withPrecision: 1.0E-10) // (312689, 99532)

Swift 3 version:

typealias Rational = (num : Int, den : Int)

func rationalApproximation(of x0 : Double, withPrecision eps : Double = 1.0E-6) -> Rational {
    var x = x0
    var a = x.rounded(.down)
    var (h1, k1, h, k) = (1, 0, Int(a), 1)

    while x - a > eps * Double(k) * Double(k) {
        x = 1.0/(x - a)
        a = x.rounded(.down)
        (h1, k1, h, k) = (h, k, h1 + Int(a) * h, k1 + Int(a) * k)
    }
    return (h, k)
}

Examples:

rationalApproximation(of: 0.333333) // (1, 3)
rationalApproximation(of: 0.142857, withPrecision: 1.0E-10) // (142857, 1000000)

Or – as suggested by @brandonscript – with a struct Rational and an initializer:

struct Rational {
    let numerator : Int
    let denominator: Int

    init(numerator: Int, denominator: Int) {
        self.numerator = numerator
        self.denominator = denominator
    }

    init(approximating x0: Double, withPrecision eps: Double = 1.0E-6) {
        var x = x0
        var a = x.rounded(.down)
        var (h1, k1, h, k) = (1, 0, Int(a), 1)

        while x - a > eps * Double(k) * Double(k) {
            x = 1.0/(x - a)
            a = x.rounded(.down)
            (h1, k1, h, k) = (h, k, h1 + Int(a) * h, k1 + Int(a) * k)
        }
        self.init(numerator: h, denominator: k)
    }
}

Example usage:

print(Rational(approximating: 0.333333))
// Rational(numerator: 1, denominator: 3)

print(Rational(approximating: .pi, withPrecision: 1.0E-7))
// Rational(numerator: 103993, denominator: 33102)

So a little late here, but I had a similar problem and ended up building Swift FractionFormatter. This works because most of the irrational numbers you care about are part of the set of vulgar, or common fractions and are easy to validate proper transformation. The rest may or may not round, but you get very close on any reasonable fraction your user might generate. It is designed to be a drop in replacement for NumberFormatter.