owlswipe - 1 year ago 130

Swift Question

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 (http://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!

Answer Source

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

```
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)
```

For **Swift 3** replace `round(x)`

by `x.rounded(.down)`

.