Преобразование десятичной дроби в Swift

Question

Я создаю калькулятор и хочу, чтобы он автоматически конвертировал каждую десятичную дробь в дроби. Поэтому, если пользователь вычисляет выражение, для которого ответ «0.333333 ...», он возвращает «1/3». Для «0.25» оно вернет «1/4». Используя GCD, как найдено здесь (Decimal to fraction conversion), я выяснил, как преобразовать любое рациональное, завершающее десятичное число в десятичное число, но это не работает ни на одной десятичной, которая повторяется (например .333333).

Каждая другая функция для этого переполнения стека находится в Objective-C. Но мне нужна функция в моем быстром приложении! Так что переведенная версия этого (https://stackoverflow.com/a/13430237/5700898) будет приятной!

Любые идеи или решения по как преобразовать рациональную или повторяющегося/нерациональное десятичной к фракции (т.е. преобразовать «0.1764705882 ...» в 3/17) было бы здорово!

Answer 1

Если вы хотите отобразить результаты расчетов как рациональных чисел тогда только 100% правильное решение использовать рациональную арифметику во всех расчетах, то есть все промежуточные значения сохраняются в виде пары целых чисел (numerator, denominator), и все дополнения, умножения, деления и т. д. выполняются с использованием правил для рациональных номеров .

Как только результат присваивается двоичный плавающем числа в , таких как Double, информация теряется. Например,

let x : Double = 7/10 

хранит в xприближения из 0.7, потому что число не может быть представлено точно как Double. От

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

можно увидеть, что x имеет значение

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

Так правильное представление x как рациональное число будет 6305039478318694/9007199254740992, но это, конечно, не то, что вы ожидаете. Что вы ожидаете, это 7/10, но есть еще одна проблема:

let x : Double = 69999999999999996/100000000000000000 

присваивает точно такое же значение для x, он неотличим от 0.7 в прецизионности Double.

Должно ли x отображаться как 7/10 или как 69999999999999996/100000000000000000?

Как было сказано выше, использование рациональной арифметики было бы идеальным решением. Если это нежизнеспособно, то вы можете преобразовать Double в рациональный номер с заданной точностью. (Ниже взято из Algorithm for LCM of doubles in Swift.)

Continued Fractions представляет собой эффективный метод для создания (конечную или бесконечной) последовательности фракций ч _п/к _п, которые являются произвольным хорошим приближением к заданному действительному числу х, и здесь является возможной реализация в 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) 
} 

Примеры:

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

точность по умолчанию 1.0E-6, но вы можете настроить, что для ваших потребностей:

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 версия:

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

Примеры:

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