Algoritmo para simplificar o decimal em frações

Eu tentei escrever um algoritmo para simplificar um decimal para uma fração e percebi que não era muito simples. Surpreendentemente, eu olhei online e todos os códigos que encontrei eram muito longos ou não funcionavam em alguns casos. O que era ainda mais irritante era que eles não funcionavam para decimais recorrentes. Eu queria saber se haveria um matemático / programador aqui que entendesse todos os processos envolvidos para simplificar um decimal em uma fração. Alguém?

O algoritmo que as outras pessoas lhe deram obtém a resposta calculando a fração contínua do número. Isto dá uma seqüência fracional que é garantida para convergir muito, muito rapidamente. No entanto, não é garantido que você tenha a menor fração que esteja dentro de uma distância epsilon de um número real. Para descobrir que você tem que andar na tree Stern-Brocot .

Para fazer isso, você subtrai a palavra para obter o número no intervalo [0, 1], então sua estimativa mais baixa é 0 e sua estimativa superior é 1. Agora faça uma pesquisa binária até chegar perto o suficiente. Em cada iteração, se o seu inferior é a / beo seu superior é c / d, o seu meio é (a + c) / (b + d). Teste seu meio contra x e faça o meio na parte superior, inferior ou retorne sua resposta final.

Aqui está um Python muito não-idiomático (e, portanto, esperançosamente legível, mesmo que você não saiba a linguagem) que implementa esse algoritmo.

 def float_to_fraction (x, error=0.000001): n = int(math.floor(x)) x -= n if x < error: return (n, 1) elif 1 - error < x: return (n+1, 1) # The lower fraction is 0/1 lower_n = 0 lower_d = 1 # The upper fraction is 1/1 upper_n = 1 upper_d = 1 while True: # The middle fraction is (lower_n + upper_n) / (lower_d + upper_d) middle_n = lower_n + upper_n middle_d = lower_d + upper_d # If x + error < middle if middle_d * (x + error) < middle_n: # middle is our new upper upper_n = middle_n upper_d = middle_d # Else If middle < x - error elif middle_n < (x - error) * middle_d: # middle is our new lower lower_n = middle_n lower_d = middle_d # Else middle is our best fraction else: return (n * middle_d + middle_n, middle_d) 

(código melhorado em fevereiro de 2017 – vá até ‘otimização’ …)

(tabela de comparação de algoritmo no final desta resposta)

Eu implementei a resposta de Btilly em C # e …

  • adicionado suporte para números negativos
  • forneça um parâmetro de accuracy para especificar o lance máximo erro relativo, não o max. erro absoluto; 0.01 encontraria uma fração dentro de 1% do valor.
  • fornecer uma otimização
  • Double.NaN e Double.Infinity não são suportados; você pode querer lidar com esses ( exemplo aqui ).
 public Fraction RealToFraction(double value, double accuracy) { if (accuracy <= 0.0 || accuracy >= 1.0) { throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1."); } int sign = Math.Sign(value); if (sign == -1) { value = Math.Abs(value); } // Accuracy is the maximum relative error; convert to absolute maxError double maxError = sign == 0 ? accuracy : value * accuracy; int n = (int) Math.Floor(value); value -= n; if (value < maxError) { return new Fraction(sign * n, 1); } if (1 - maxError < value) { return new Fraction(sign * (n + 1), 1); } // The lower fraction is 0/1 int lower_n = 0; int lower_d = 1; // The upper fraction is 1/1 int upper_n = 1; int upper_d = 1; while (true) { // The middle fraction is (lower_n + upper_n) / (lower_d + upper_d) int middle_n = lower_n + upper_n; int middle_d = lower_d + upper_d; if (middle_d * (value + maxError) < middle_n) { // real + error < middle : middle is our new upper upper_n = middle_n; upper_d = middle_d; } else if (middle_n < (value - maxError) * middle_d) { // middle < real - error : middle is our new lower lower_n = middle_n; lower_d = middle_d; } else { // Middle is our best fraction return new Fraction((n * middle_d + middle_n) * sign, middle_d); } } } 

O tipo de Fraction é apenas uma estrutura simples. Claro, use o seu tipo preferido ... (Eu gosto desse aqui de Rick Davin.)

 public struct Fraction { public Fraction(int n, int d) { N = n; D = d; } public int N { get; private set; } public int D { get; private set; } } 

Em fevereiro de 2017

Para determinados valores, como 0.01 , 0.001 , etc., o algoritmo passa por centenas ou milhares de iterações lineares. Para consertar isso, implementei uma maneira binária de encontrar o valor final - graças a essa ideia. Dentro do if -statement substitua o seguinte:

 // real + error < middle : middle is our new upper Seek(ref upper_n, ref upper_d, lower_n, lower_d, (un, ud) => (lower_d + ud) * (value + maxError) < (lower_n + un)); 

e

 // middle < real - error : middle is our new lower Seek(ref lower_n, ref lower_d, upper_n, upper_d, (ln, ld) => (ln + upper_n) < (value - maxError) * (ld + upper_d)); 

Aqui está a implementação do método Seek :

 ///  /// Binary seek for the value where f() becomes false. ///  void Seek(ref int a, ref int b, int ainc, int binc, Func f) { a += ainc; b += binc; if (f(a, b)) { int weight = 1; do { weight *= 2; a += ainc * weight; b += binc * weight; } while (f(a, b)); do { weight /= 2; int adec = ainc * weight; int bdec = binc * weight; if (!f(a - adec, b - bdec)) { a -= adec; b -= bdec; } } while (weight > 1); } } 

Tabela de comparação de algoritmos

Você pode querer copiar a tabela para o seu editor de texto para visualização em canvas cheia.

 Accuracy: 1.0E-3 | Stern-Brocot OPTIMIZED | Eppstein | Richards Input | Result Error Iterations Iterations | Result Error Iterations | Result Error Iterations ======================| =====================================================| =========================================| ========================================= 0 | 0/1 (zero) 0 0 0 | 0/1 (zero) 0 0 | 0/1 (zero) 0 0 1 | 1/1 0 0 0 | 1001/1000 1.0E-3 1 | 1/1 0 0 3 | 3/1 0 0 0 | 1003/334 1.0E-3 1 | 3/1 0 0 -1 | -1/1 0 0 0 | -1001/1000 1.0E-3 1 | -1/1 0 0 -3 | -3/1 0 0 0 | -1003/334 1.0E-3 1 | -3/1 0 0 0.999999 | 1/1 1.0E-6 0 0 | 1000/1001 -1.0E-3 2 | 1/1 1.0E-6 0 -0.999999 | -1/1 1.0E-6 0 0 | -1000/1001 -1.0E-3 2 | -1/1 1.0E-6 0 1.000001 | 1/1 -1.0E-6 0 0 | 1001/1000 1.0E-3 1 | 1/1 -1.0E-6 0 -1.000001 | -1/1 -1.0E-6 0 0 | -1001/1000 1.0E-3 1 | -1/1 -1.0E-6 0 0.50 (1/2) | 1/2 0 1 1 | 999/1999 -5.0E-4 2 | 1/2 0 1 0.33... (1/3) | 1/3 0 2 2 | 999/2998 -3.3E-4 2 | 1/3 0 1 0.67... (2/3) | 2/3 0 2 2 | 999/1498 3.3E-4 3 | 2/3 0 2 0.25 (1/4) | 1/4 0 3 3 | 999/3997 -2.5E-4 2 | 1/4 0 1 0.11... (1/9) | 1/9 0 8 4 | 999/8992 -1.1E-4 2 | 1/9 0 1 0.09... (1/11) | 1/11 0 10 5 | 999/10990 -9.1E-5 2 | 1/11 0 1 0.62... (307/499) | 8/13 2.5E-4 5 5 | 913/1484 -2.2E-6 8 | 8/13 2.5E-4 5 0.14... (33/229) | 15/104 8.7E-4 20 9 | 974/6759 -4.5E-6 6 | 16/111 2.7E-4 3 0.05... (33/683) | 7/145 -8.4E-4 24 10 | 980/20283 1.5E-6 7 | 10/207 -1.5E-4 4 0.18... (100/541) | 17/92 -3.3E-4 11 10 | 939/5080 -2.0E-6 8 | 17/92 -3.3E-4 4 0.06... (33/541) | 5/82 -3.7E-4 19 8 | 995/16312 -1.9E-6 6 | 5/82 -3.7E-4 4 0.1 | 1/10 0 9 5 | 999/9991 -1.0E-4 2 | 1/10 0 1 0.2 | 1/5 0 4 3 | 999/4996 -2.0E-4 2 | 1/5 0 1 0.3 | 3/10 0 5 5 | 998/3327 -1.0E-4 4 | 3/10 0 3 0.4 | 2/5 0 3 3 | 999/2497 2.0E-4 3 | 2/5 0 2 0.5 | 1/2 0 1 1 | 999/1999 -5.0E-4 2 | 1/2 0 1 0.6 | 3/5 0 3 3 | 1000/1667 -2.0E-4 4 | 3/5 0 3 0.7 | 7/10 0 5 5 | 996/1423 -1.0E-4 4 | 7/10 0 3 0.8 | 4/5 0 4 3 | 997/1246 2.0E-4 3 | 4/5 0 2 0.9 | 9/10 0 9 5 | 998/1109 -1.0E-4 4 | 9/10 0 3 0.01 | 1/100 0 99 8 | 999/99901 -1.0E-5 2 | 1/100 0 1 0.001 | 1/1000 0 999 11 | 999/999001 -1.0E-6 2 | 1/1000 0 1 0.0001 | 1/9991 9.0E-4 9990 15 | 999/9990001 -1.0E-7 2 | 1/10000 0 1 1E-05 | 1/99901 9.9E-4 99900 18 | 1000/99999999 1.0E-8 3 | 1/99999 1.0E-5 1 0.33333333333 | 1/3 1.0E-11 2 2 | 1000/3001 -3.3E-4 2 | 1/3 1.0E-11 1 0.3 | 3/10 0 5 5 | 998/3327 -1.0E-4 4 | 3/10 0 3 0.33 | 30/91 -1.0E-3 32 8 | 991/3003 1.0E-5 3 | 33/100 0 2 0.333 | 167/502 -9.9E-4 169 11 | 1000/3003 1.0E-6 3 | 333/1000 0 2 0.7777 | 7/9 1.0E-4 5 4 | 997/1282 -1.1E-5 4 | 7/9 1.0E-4 3 0.101 | 10/99 1.0E-4 18 10 | 919/9099 1.1E-6 5 | 10/99 1.0E-4 3 0.10001 | 1/10 -1.0E-4 9 5 | 1/10 -1.0E-4 4 | 1/10 -1.0E-4 2 0.100000001 | 1/10 -1.0E-8 9 5 | 1000/9999 1.0E-4 3 | 1/10 -1.0E-8 2 0.001001 | 1/999 1.0E-6 998 11 | 1/999 1.0E-6 3 | 1/999 1.0E-6 1 0.0010000001 | 1/1000 -1.0E-7 999 11 | 1000/999999 9.0E-7 3 | 1/1000 -1.0E-7 2 0.11 | 10/91 -1.0E-3 18 9 | 1000/9091 -1.0E-5 4 | 10/91 -1.0E-3 2 0.1111 | 1/9 1.0E-4 8 4 | 1000/9001 -1.1E-5 2 | 1/9 1.0E-4 1 0.111111111111 | 1/9 1.0E-12 8 4 | 1000/9001 -1.1E-4 2 | 1/9 1.0E-12 1 1 | 1/1 0 0 0 | 1001/1000 1.0E-3 1 | 1/1 0 0 -1 | -1/1 0 0 0 | -1001/1000 1.0E-3 1 | -1/1 0 0 -0.5 | -1/2 0 1 1 | -999/1999 -5.0E-4 2 | -1/2 0 1 3.14 | 22/7 9.1E-4 6 4 | 964/307 2.1E-5 3 | 22/7 9.1E-4 1 3.1416 | 22/7 4.0E-4 6 4 | 732/233 9.8E-6 3 | 22/7 4.0E-4 1 3.14... (pi) | 22/7 4.0E-4 6 4 | 688/219 -1.3E-5 4 | 22/7 4.0E-4 1 0.14 | 7/50 0 13 7 | 995/7107 2.0E-5 3 | 7/50 0 2 0.1416 | 15/106 -6.4E-4 21 8 | 869/6137 9.2E-7 5 | 16/113 -5.0E-5 2 2.72... (e) | 68/25 6.3E-4 7 7 | 878/323 -5.7E-6 8 | 87/32 1.7E-4 5 0.141592653589793 | 15/106 -5.9E-4 21 8 | 991/6999 -7.0E-6 4 | 15/106 -5.9E-4 2 -1.33333333333333 | -4/3 2.5E-15 2 2 | -1001/751 -3.3E-4 2 | -4/3 2.5E-15 1 -1.3 | -13/10 0 5 5 | -992/763 1.0E-4 3 | -13/10 0 2 -1.33 | -97/73 -9.3E-4 26 8 | -935/703 1.1E-5 3 | -133/100 0 2 -1.333 | -4/3 2.5E-4 2 2 | -1001/751 -8.3E-5 2 | -4/3 2.5E-4 1 -1.33333337 | -4/3 -2.7E-8 2 2 | -999/749 3.3E-4 3 | -4/3 -2.7E-8 2 -1.7 | -17/10 0 5 5 | -991/583 -1.0E-4 4 | -17/10 0 3 -1.37 | -37/27 2.7E-4 7 7 | -996/727 1.0E-5 7 | -37/27 2.7E-4 5 -1.33337 | -4/3 -2.7E-5 2 2 | -999/749 3.1E-4 3 | -4/3 -2.7E-5 2 0.047619 | 1/21 1.0E-6 20 6 | 1000/21001 -4.7E-5 2 | 1/21 1.0E-6 1 12.125 | 97/8 0 7 4 | 982/81 -1.3E-4 2 | 97/8 0 1 5.5 | 11/2 0 1 1 | 995/181 -5.0E-4 2 | 11/2 0 1 0.1233333333333 | 9/73 -3.7E-4 16 8 | 971/7873 -3.4E-6 4 | 9/73 -3.7E-4 2 0.7454545454545 | 38/51 -4.8E-4 15 8 | 981/1316 -1.9E-5 6 | 38/51 -4.8E-4 4 0.01024801004 | 2/195 8.2E-4 98 9 | 488/47619 2.0E-8 13 | 2/195 8.2E-4 3 0.99011 | 91/92 -9.9E-4 91 8 | 801/809 1.3E-6 5 | 100/101 -1.1E-5 2 0.9901134545 | 91/92 -9.9E-4 91 8 | 601/607 1.9E-6 5 | 100/101 -1.5E-5 2 0.19999999 | 1/5 5.0E-8 4 3 | 1000/5001 -2.0E-4 2 | 1/5 5.0E-8 1 0.20000001 | 1/5 -5.0E-8 4 3 | 1000/4999 2.0E-4 3 | 1/5 -5.0E-8 2 5.0183168565E-05 | 1/19908 9.5E-4 19907 16 | 1000/19927001 -5.0E-8 2 | 1/19927 5.2E-12 1 3.909E-07 | 1/2555644 1.0E-3 2555643 23 | 1/1 2.6E6 (!) 1 | 1/2558199 1.1E-8 1 88900003.001 |88900003/1 -1.1E-11 0 0 |88900004/1 1.1E-8 1 |88900003/1 -1.1E-11 0 0.26... (5/19) | 5/19 0 7 6 | 996/3785 -5.3E-5 4 | 5/19 0 3 0.61... (37/61) | 17/28 9.7E-4 8 7 | 982/1619 -1.7E-5 8 | 17/28 9.7E-4 5 | | | Accuracy: 1.0E-4 | Stern-Brocot OPTIMIZED | Eppstein | Richards Input | Result Error Iterations Iterations | Result Error Iterations | Result Error Iterations ======================| =====================================================| =========================================| ========================================= 0.62... (307/499) | 227/369 -8.8E-5 33 11 | 9816/15955 -2.0E-7 8 | 299/486 -6.7E-6 6 0.05... (33/683) | 23/476 6.4E-5 27 12 | 9989/206742 1.5E-7 7 | 23/476 6.4E-5 5 0.06... (33/541) | 28/459 6.6E-5 24 12 | 9971/163464 -1.9E-7 6 | 33/541 0 5 1E-05 | 1/99991 9.0E-5 99990 18 | 10000/999999999 1.0E-9 3 | 1/99999 1.0E-5 1 0.333 | 303/910 -9.9E-5 305 12 | 9991/30003 1.0E-7 3 | 333/1000 0 2 0.7777 | 556/715 -1.0E-4 84 12 | 7777/10000 0 8 | 1109/1426 -1.8E-7 4 3.14... (pi) | 289/92 -9.2E-5 19 8 | 9918/3157 -8.1E-7 4 | 333/106 -2.6E-5 2 2.72... (e) | 193/71 1.0E-5 10 9 | 9620/3539 6.3E-8 11 | 193/71 1.0E-5 7 0.7454545454545 | 41/55 6.1E-14 16 8 | 9960/13361 -1.8E-6 6 | 41/55 6.1E-14 5 0.01024801004 | 7/683 8.7E-5 101 12 | 9253/902907 -1.3E-10 16 | 7/683 8.7E-5 5 0.99011 | 100/101 -1.1E-5 100 8 | 901/910 -1.1E-7 6 | 100/101 -1.1E-5 2 0.9901134545 | 100/101 -1.5E-5 100 8 | 8813/8901 1.6E-8 7 | 100/101 -1.5E-5 2 0.26... (5/19) | 5/19 0 7 6 | 9996/37985 -5.3E-6 4 | 5/19 0 3 0.61... (37/61) | 37/61 0 10 8 | 9973/16442 -1.6E-6 8 | 37/61 0 7 

Comparação de desempenho

Eu realizei testes de velocidade detalhados e plotei os resultados. Não olhando qualidade e só velocidade:

  • A otimização Stern-Brocot reduz a velocidade no máximo em um fator 2, mas o Stern-Brocot original pode ser centenas ou milhares de vezes mais lento quando atinge os valores azarados mencionados. Isso ainda é apenas alguns microssegundos por chamada.
  • Richards é consistentemente rápido.
  • Eppstein é cerca de 3 vezes mais lento que os outros.

Stern-Brocot e Richards compararam:

  • Ambos retornam boas frações.
  • Richards geralmente resulta em um erro menor. Também é um pouco mais rápido.
  • Stern-Brocot desce a tree SB. Ele encontra a fração do menor denominador que atende à precisão exigida e, em seguida, para.

Se você não requer a menor fração do denominador, Richards é uma boa escolha.

Eu sei que você disse que pesquisou online, mas se você perdeu o seguinte artigo, pode ser de alguma ajuda. Inclui um exemplo de código em Pascal.

Algoritmo para converter um decimal em uma fração *

Como alternativa, como parte de sua biblioteca padrão, Ruby possui código que lida com números racionais. Pode converter de carros alegóricos em racionais e vice-versa. Eu acredito que você pode olhar através do código também. A documentação é encontrada aqui . Eu sei que você não está usando Ruby, mas pode ajudar a ver os algoritmos.

Além disso, você pode chamar o código Ruby de C # (ou até mesmo escrever código Ruby dentro de um arquivo de código C #) se você usar o IronRuby , que é executado sobre a estrutura .net.

* Atualizado para um novo link, já que parece que o URL original está quebrado ( http://homepage.smc.edu/kennedy_john/DEC2FRAC.pdf )

Eu encontrei o mesmo papel que Matt referenciou, e eu peguei um segundo e o implementei em Python. Talvez ver a mesma ideia no código seja mais claro. Concedido, você solicitou uma resposta em C # e eu estou dando a você em Python, mas é um programa bastante trivial, e tenho certeza que seria fácil de traduzir. Os parâmetros são num (o número decimal que você gostaria de converter em racional) e epsilon (a diferença máxima permitida entre num e o racional calculado). Algumas execuções de teste rápidas descobrem que normalmente são necessárias duas ou três iterações para convergir quando o epsilon estiver em torno de 1e-4.

 def dec2frac(num, epsilon, max_iter=20): d = [0, 1] + ([0] * max_iter) z = num n = 1 t = 1 while num and t < max_iter and abs(n/d[t] - num) > epsilon: t += 1 z = 1/(z - int(z)) d[t] = d[t-1] * int(z) + d[t-2] # int(x + 0.5) is equivalent to rounding x. n = int(num * d[t] + 0.5) return n, d[t] 

Edit: Acabei de notar sua nota sobre querer que eles trabalhem com decimais recorrentes. Eu não conheço nenhum idioma que tenha syntax para suportar decimais recorrentes, então não tenho certeza de como alguém poderia lidar com eles, mas executar 0.6666666 e 0.166666 através desse método retorna os resultados corretos (2/3 e 1/6, respectivamente).

Outro Edit (eu não acho que isso seria tão interessante!): Se você quiser saber mais sobre a teoria por trás deste algoritmo, a Wikipedia tem uma excelente página sobre o algoritmo euclidiano

Você não pode representar um decimal recorrente em .net, então vou ignorar essa parte da sua pergunta.

Você pode representar apenas um número finito e relativamente pequeno de dígitos.

Existe um algoritmo extremamente simples:

  • tomar decimal x
  • contar o número de dígitos após o ponto decimal; chame isso de n
  • crie uma fração (10^n * x) / 10^n
  • remover fatores comuns do numerador e denominador.

então se você tiver 0,44, você contaria 2 lugares, o ponto decimal – n = 2, e então escreverá

  • (0.44 * 10^2) / 10^2
  • = 44 / 100
  • fatoração (remoção do fator comum de 4) dá 11 / 25

Aqui está uma versão em C # do exemplo python de Will Brown. Eu também mudei para lidar com números inteiros separados (por exemplo, “2 1/8” em vez de “17/8”).

  public static string DoubleToFraction(double num, double epsilon = 0.0001, int maxIterations = 20) { double[] d = new double[maxIterations + 2]; d[1] = 1; double z = num; double n = 1; int t = 1; int wholeNumberPart = (int)num; double decimalNumberPart = num - Convert.ToDouble(wholeNumberPart); while (t < maxIterations && Math.Abs(n / d[t] - num) > epsilon) { t++; z = 1 / (z - (int)z); d[t] = d[t - 1] * (int)z + d[t - 2]; n = (int)(decimalNumberPart * d[t] + 0.5); } return string.Format((wholeNumberPart > 0 ? wholeNumberPart.ToString() + " " : "") + "{0}/{1}", n.ToString(), d[t].ToString() ); } 

Eu escrevi uma class rápida que corre bastante rápido e dá os resultados que eu esperaria. Você pode escolher sua precisão também. É muito mais simples de qualquer código que vi e corre rápido também.

 //Written By Brian Dobony public static class Fraction { public static string ConvertDecimal(Double NumberToConvert, int DenominatorPercision = 32) { int WholeNumber = (int)NumberToConvert; double DecimalValue = NumberToConvert - WholeNumber; double difference = 1; int numerator = 1; int denominator = 1; // find closest value that matches percision // Automatically finds Fraction in simplified form for (int y = 2; y < DenominatorPercision + 1; y++) { for (int x = 1; x < y; x++) { double tempdif = Math.Abs(DecimalValue - (double)x / (double)y); if (tempdif < difference) { numerator = x; denominator = y; difference = tempdif; // if exact match is found return it if (difference == 0) { return FractionBuilder(WholeNumber, numerator, denominator); } } } } return FractionBuilder(WholeNumber, numerator, denominator); } private static string FractionBuilder(int WholeNumber, int Numerator, int Denominator) { if (WholeNumber == 0) { return Numerator + @"/" + Denominator; } else { return WholeNumber + " " + Numerator + @"/" + Denominator; } } } 

Esta é a versão C # do algoritmo de Ian Richards / John Kennedy. Outras respostas aqui usando este mesmo algoritmo:

  • Matt (links para o jornal de Kennedy apenas)
  • Haldean Brown (Python)
  • Jeremy Herrman (c #)
  • PinkFloyd (C)

Não manipula infinidades e NaN.

Esse algoritmo é rápido .

Por exemplo, valores e uma comparação com outros algoritmos, veja minha outra resposta

 public Fraction RealToFraction(double value, double accuracy) { if (accuracy <= 0.0 || accuracy >= 1.0) { throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1."); } int sign = Math.Sign(value); if (sign == -1) { value = Math.Abs(value); } // Accuracy is the maximum relative error; convert to absolute maxError double maxError = sign == 0 ? accuracy : value * accuracy; int n = (int) Math.Floor(value); value -= n; if (value < maxError) { return new Fraction(sign * n, 1); } if (1 - maxError < value) { return new Fraction(sign * (n + 1), 1); } double z = value; int previousDenominator = 0; int denominator = 1; int numerator; do { z = 1.0 / (z - (int) z); int temp = denominator; denominator = denominator * (int) z + previousDenominator; previousDenominator = temp; numerator = Convert.ToInt32(value * denominator); } while (Math.Abs(value - (double) numerator / denominator) > maxError && z != (int) z); return new Fraction((n * denominator + numerator) * sign, denominator); } 

Eu chego com uma resposta muito tardia. O código é retirado de um artigo de Richards publicado em 1981 e escrito em c .

 inline unsigned int richards_solution(double const& x0, unsigned long long& num, unsigned long long& den, double& sign, double const& err = 1e-10){ sign = my::sign(x0); double g(std::abs(x0)); unsigned long long a(0); unsigned long long b(1); unsigned long long c(1); unsigned long long d(0); unsigned long long s; unsigned int iter(0); do { s = std::floor(g); num = a + s*c; den = b + s*d; a = c; b = d; c = num; d = den; g = 1.0/(gs); if(err>std::abs(sign*num/den-x0)){ return iter; } } while(iter++<1e6); std::cerr<<__PRETTY_FUNCTION__<<" : failed to find a fraction for "< 

Eu reescrevi aqui minha implementação do btilly_solution :

 inline unsigned int btilly_solution(double x, unsigned long long& num, unsigned long long& den, double& sign, double const& err = 1e-10){ sign = my::sign(x); num = std::floor(std::abs(x)); x = std::abs(x)-num; unsigned long long lower_n(0); unsigned long long lower_d(1); unsigned long long upper_n(1); unsigned long long upper_d(1); unsigned long long middle_n; unsigned long long middle_d; unsigned int iter(0); do { middle_n = lower_n + upper_n; middle_d = lower_d + upper_d; if(middle_d*(x+err)middle_n) { lower_n = middle_n; lower_d = middle_d; } else { num = num*middle_d+middle_n; den = middle_d; return iter; } } while(iter++<1e6); den = 1; std::cerr<<__PRETTY_FUNCTION__<<" : failed to find a fraction for "< 

E aqui proponho alguns testes com um erro de 1e-10 :

 ------------------------------------------------------ | btilly 0.166667 0.166667=1/6 in 5 iterations | 1/6 richard 0.166667 0.166667=1/6 in 1 iterations | ------------------------------------------------------ | btilly 0.333333 0.333333=1/3 in 2 iterations | 1/3 richard 0.333333 0.333333=1/3 in 1 iterations | ------------------------------------------------------ | btilly 0.142857 0.142857=1/7 in 6 iterations | 1/7 richard 0.142857 0.142857=1/7 in 1 iterations | ------------------------------------------------------ | btilly 0.714286 0.714286=5/7 in 4 iterations | 5/7 richard 0.714286 0.714286=5/7 in 4 iterations | ------------------------------------------------------ | btilly 1e-07 1.001e-07=1/9990010 in 9990009 iteration | 0.0000001 richard 1e-07 1e-07=1/10000000 in 1 iterations | ------------------------------------------------------ | btilly 3.66667 3.66667=11/3 in 2 iterations | 11/3 richard 3.66667 3.66667=11/3 in 3 iterations | ------------------------------------------------------ | btilly 1.41421 1.41421=114243/80782 in 25 iterations | sqrt(2) richard 1.41421 1.41421=114243/80782 in 13 iterations | ------------------------------------------------------ | btilly 3.14159 3.14159=312689/99532 in 317 iterations | pi richard 3.14159 3.14159=312689/99532 in 7 iterations | ------------------------------------------------------ | btilly 2.71828 2.71828=419314/154257 in 36 iterations | e richard 2.71828 2.71828=517656/190435 in 14 iterations | ------------------------------------------------------ | btilly 0.390885 0.390885=38236/97819 in 60 iterations | random richard 0.390885 0.390885=38236/97819 in 13 iterations | 

Como você pode ver, os dois methods dão mais ou menos os mesmos resultados, mas o dos richards é muito mais eficiente e fácil de implementar.

Editar

Para compilar meu código você precisa de uma descrição para o my::sign que é simplesmente uma function que retorna o sinal de uma variável. Aqui está minha implementação

  namespace my{ template inline constexpr int sign_unsigned(Type x){ return Type(0) inline constexpr int sign_signed(Type x){ return (Type(0) inline constexpr int sign(Type x) { return std::is_signed()?sign_signed(x):sign_unsigned(x); } } 

Desculpa

Eu acho que essa resposta se refere ao mesmo algoritmo. Eu não vi isso antes ...

Esse algoritmo de David Eppstein, UC Irvine, baseado na teoria das frações contínuas e originalmente em C, foi traduzido para C # por mim. As frações que ele gera satisfazem a margem de erro, mas na maioria das vezes não parecem tão boas quanto as soluções em minhas outras respostas. Por exemplo, 0.5 passa a ser 999/1999 enquanto 1/2 seria preferido quando exibido para um usuário (se precisar, veja minhas outras respostas ).

Há uma sobrecarga para especificar a margem de erro como um double (relativo ao valor, não ao erro absoluto). Para o tipo de Fraction , veja minha outra resposta.

By the way, se suas frações podem ficar grandes, altere os int relevantes para long . Em comparação com os outros algoritmos, este é propenso a transbordar.

Por exemplo, valores e uma comparação com outros algoritmos, veja minha outra resposta

 public Fraction RealToFraction(double value, int maxDenominator) { // http://www.ics.uci.edu/~eppstein/numth/frap.c // Find rational approximation to given real number // David Eppstein / UC Irvine / 8 Aug 1993 // With corrections from Arno Formella, May 2008 if (value == 0.0) { return new Fraction(0, 1); } int sign = Math.Sign(value); if (sign == -1) { value = Math.Abs(value); } int[,] m = { { 1, 0 }, { 0, 1 } }; int ai = (int) value; // Find terms until denominator gets too big while (m[1, 0] * ai + m[1, 1] <= maxDenominator) { int t = m[0, 0] * ai + m[0, 1]; m[0, 1] = m[0, 0]; m[0, 0] = t; t = m[1, 0] * ai + m[1, 1]; m[1, 1] = m[1, 0]; m[1, 0] = t; value = 1.0 / (value - ai); // 0x7FFFFFFF = Assumes 32 bit floating point just like in the C implementation. // This check includes Double.IsInfinity(). Even though C# double is 64 bits, // the algorithm sometimes fails when trying to increase this value too much. So // I kept it. Anyway, it works. if (value > 0x7FFFFFFF) { break; } ai = (int) value; } // Two approximations are calculated: one on each side of the input // The result of the first one is the current value. Below the other one // is calculated and it is returned. ai = (maxDenominator - m[1, 1]) / m[1, 0]; m[0, 0] = m[0, 0] * ai + m[0, 1]; m[1, 0] = m[1, 0] * ai + m[1, 1]; return new Fraction(sign * m[0, 0], m[1, 0]); } public Fraction RealToFraction(double value, double accuracy) { if (accuracy <= 0.0 || accuracy >= 1.0) { throw new ArgumentOutOfRangeException("accuracy", "Must be > 0 and < 1."); } int maxDenominator = (int) Math.Ceiling(Math.Abs(1.0 / (value * accuracy))); if (maxDenominator < 1) { maxDenominator = 1; } return RealToFraction(value, maxDenominator); } 

Um decimal recorrente pode ser representado por dois decimais finitos: a parte da esquerda antes da repetição e a parte de repetição. Por exemplo, 1.6181818... = 1.6 + 0.1*(0.18...) . Pense nisso como a + b * sum(c * 10**-(d*k) for k in range(1, infinity)) (em notação em Python aqui). No meu exemplo, a=1.6 , b=0.1 , c=18 , d=2 (o número de dígitos em c ). A sum infinita pode ser simplificada ( sum(r**k for r in range(1, infinity)) == r / (1 - r) se bem me lembro corretamente), gerando a + b * (c * 10**-d) / (1 - c * 10**-d)) , uma relação finita. Isto é, comece com a , b , c , d como números racionais, e você acaba com outro.

(Isso elabora a resposta de Kirk Broadhurst, que está certa, mas não cobre decimais repetidos. Não prometo que não cometi erros acima, embora esteja confiante de que a abordagem geral funciona.)

Recentemente tive que executar essa tarefa de trabalhar com um tipo de dados decimal, que é armazenado em nosso database do SQL Server. Na camada de apresentação, esse valor foi editado como um valor fracionário em um TextBox. A complexidade aqui foi trabalhar com o tipo de dados decimal que contém alguns valores muito grandes em comparação com int ou long. So to reduce the opportunity for data overrun, I stuck with the Decimal Data Type throughout the conversion.

Before I begin, I want to comment on Kirk’s previous answer. He is absolutely correct as long as there are no assumptions made. However, if the developer only looks for repeating patterns within the confines of the Decimal Data Type .3333333… can be represented as 1/3. An example of the algorithm can be found at basic-mathematics.com . Again, this means you have to make assumptions based on the information available and using this method only captures a very small subset of repeating decimals. However for small numbers should be okay.

Moving forward, let me give you a snapshot of my solution. If you want to read a complete example with additional code I created a blog post with much more detail.

Convert Decimal Data Type to a String Fraction

 public static void DecimalToFraction(decimal value, ref decimal sign, ref decimal numerator, ref decimal denominator) { const decimal maxValue = decimal.MaxValue / 10.0M; // eg .25/1 = (.25 * 100)/(1 * 100) = 25/100 = 1/4 var tmpSign = value < decimal.Zero ? -1 : 1; var tmpNumerator = Math.Abs(value); var tmpDenominator = decimal.One; // While numerator has a decimal value while ((tmpNumerator - Math.Truncate(tmpNumerator)) > 0 && tmpNumerator < maxValue && tmpDenominator < maxValue) { tmpNumerator = tmpNumerator * 10; tmpDenominator = tmpDenominator * 10; } tmpNumerator = Math.Truncate(tmpNumerator); // Just in case maxValue boundary was reached. ReduceFraction(ref tmpNumerator, ref tmpDenominator); sign = tmpSign; numerator = tmpNumerator; denominator = tmpDenominator; } public static string DecimalToFraction(decimal value) { var sign = decimal.One; var numerator = decimal.One; var denominator = decimal.One; DecimalToFraction(value, ref sign, ref numerator, ref denominator); return string.Format("{0}/{1}", (sign * numerator).ToString().TruncateDecimal(), denominator.ToString().TruncateDecimal()); } 

This is pretty straight forward where the DecimalToFraction(decimal value) is nothing more than a simplified entry point for the first method which provides access to all the components which compose a fraction. If you have a decimal of .325 then divide it by 10 to the power of number of decimal places. Lastly reduce the fraction. And, in this example .325 = 325/10^3 = 325/1000 = 13/40.

Next, going the other direction.

Convert String Fraction to Decimal Data Type

 static readonly Regex FractionalExpression = new Regex(@"^(?[-])?(?\d+)(/(?\d+))?$"); public static decimal? FractionToDecimal(string fraction) { var match = FractionalExpression.Match(fraction); if (match.Success) { // var sign = Int32.Parse(match.Groups["sign"].Value + "1"); var numerator = Int32.Parse(match.Groups["sign"].Value + match.Groups["numerator"].Value); int denominator; if (Int32.TryParse(match.Groups["denominator"].Value, out denominator)) return denominator == 0 ? (decimal?)null : (decimal)numerator / denominator; if (numerator == 0 || numerator == 1) return numerator; } return null; } 

Converting back to a decimal is quite simple as well. Here we parse out the fractional components, store them in something we can work with (here decimal values) and perform our division.

Meus 2 centavos. Here’s VB.NET version of btilly’s excellent algorithm:

  Public Shared Sub float_to_fraction(x As Decimal, ByRef Numerator As Long, ByRef Denom As Long, Optional ErrMargin As Decimal = 0.001) Dim n As Long = Int(Math.Floor(x)) x -= n If x < ErrMargin Then Numerator = n Denom = 1 Return ElseIf x >= 1 - ErrMargin Then Numerator = n + 1 Denom = 1 Return End If ' The lower fraction is 0/1 Dim lower_n As Integer = 0 Dim lower_d As Integer = 1 ' The upper fraction is 1/1 Dim upper_n As Integer = 1 Dim upper_d As Integer = 1 Dim middle_n, middle_d As Decimal While True ' The middle fraction is (lower_n + upper_n) / (lower_d + upper_d) middle_n = lower_n + upper_n middle_d = lower_d + upper_d ' If x + error < middle If middle_d * (x + ErrMargin) < middle_n Then ' middle is our new upper upper_n = middle_n upper_d = middle_d ' Else If middle < x - error ElseIf middle_n < (x - ErrMargin) * middle_d Then ' middle is our new lower lower_n = middle_n lower_d = middle_d ' Else middle is our best fraction Else Numerator = n * middle_d + middle_n Denom = middle_d Return End If End While End Sub 

Well, seems I finally had to do it myself. I just had to create a program simulating the natural way I would solve it myself. I just submitted the code to codeproject as writing out the whole code here won’t be suitable. You can download the project from here Fraction_Conversion , or look at the codeproject page here .

Veja como isso funciona:

  1. Find out whether given decimal is negative
  2. Convert decimal to absolute value
  3. Get integer part of given decimal
  4. Get the decimal part
  5. Check whether decimal is recurring. If decimal is recurring, we then return the exact recurring decimal
  6. If decimal is not recurring, start reduction by changing numerator to 10^no. of decimal, else we subtract 1 from numerator
  7. Then reduce fraction

Code Preview:

  private static string dec2frac(double dbl) { char neg = ' '; double dblDecimal = dbl; if (dblDecimal == (int) dblDecimal) return dblDecimal.ToString(); //return no if it's not a decimal if (dblDecimal < 0) { dblDecimal = Math.Abs(dblDecimal); neg = '-'; } var whole = (int) Math.Truncate(dblDecimal); string decpart = dblDecimal.ToString().Replace(Math.Truncate(dblDecimal) + ".", ""); double rN = Convert.ToDouble(decpart); double rD = Math.Pow(10, decpart.Length); string rd = recur(decpart); int rel = Convert.ToInt32(rd); if (rel != 0) { rN = rel; rD = (int) Math.Pow(10, rd.Length) - 1; } //just a few prime factors for testing purposes var primes = new[] {41, 43, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2}; foreach (int i in primes) reduceNo(i, ref rD, ref rN); rN = rN + (whole*rD); return string.Format("{0}{1}/{2}", neg, rN, rD); } 

Thanks @ Darius for given me an idea of how to solve the recurring decimals 🙂

The most populair solutions to this problem are Richards’ algorithm and the Stern-Brocot algorithm , implemented by btilly with speed optimalization by btilly and Jay Zed. Richards’ algorithm is the fastest, but does not guarantee to return the best fraction.

I have an solution to this problem which always gives the best fraction and is also faster than all of the algorithms above. Here is the algorithm in C# (explanation and speed test below).

This is a short algorithm without comments. An complete version is provided in the source code at the end.

 public static Fraction DoubleToFractionSjaak(double value, double accuracy) { int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); int a = 0; int b = 1; int c = 1; int d = (int)(1 / maximumvalue); while (true) { int n = (int)((b * minimalvalue - a) / (c - d * minimalvalue)); if (n == 0) break; a += n * c; b += n * d; n = (int)((c - d * maximumvalue) / (b * maximumvalue - a)); if (n == 0) break; c += n * a; d += n * b; } int denominator = b + d; return new Fraction(sign * (integerpart * denominator + (a + c)), denominator); } 

Where Fraction is a simple class to store a fraction, like the following:

 public class Fraction { public int Numerator { get; private set; } public int Denominator { get; private set; } public Fraction(int numerator, int denominator) { Numerator = numerator; Denominator = denominator; } } 

Como funciona

Like the other solutions mentioned, my solution is based on continued fraction. Other solutions like the one from Eppstein or solutions based on repeating decimals proved to be slower and/or give suboptimal results.

Continued fraction
Solutions based on continued fraction are mostly based on two algorithms, both described in an article by Ian Richards published here in 1981. He called them the “slow continued fraction algorithm” and the “fast continued fraction algorithm”. The first is known as the the Stern-Brocot algorithm while the latter is known as Richards’ algorithm.

My algorithm (short explanation)
To fully understand my algorithm, you need to have read the article by Ian Richards or at least understand what a Farey pair is. Furthermore, read the algorithm with comments at the end of this article.

The algorithm is using a Farey pair, containing a left and a right fraction. By repeatedly taking the mediant it is closing in on the target value. This is just like the slow algorithm but there are two major differences:

  1. Multiple iterations are performed at once as long as the mediant stay on one side of the target value.
  2. The left and right fraction cannot come closer to the target value than the given accuracy.

Alternately the right and left side of the target value are checked. If the algorithm cannot produce a result closer to the target value, the process ends. The resulting mediant is the optimal solution.

Speed test

I did some speed tests on my laptop with the following algorithms:

  1. Improved slow algorithm by Kay Zed and btilly
  2. John Kennedy’s implementation of the Fast algorithm, converted to C# by Kay Zed
  3. My implementation of the Fast algorithm (close to the original by Ian Richards)
  4. Jeremy Herrman’s implementation of the Fast algorithm
  5. My algorithm above

I omitted the original slow algorithm by btilly , because of its bad worst-case performance.

Test set
I choose a set of target values (very arbitrary) and calculated the fraction 100000 times with 5 different accuracies. Because possible some (future) algorithms couldn’t handle improper fractions, only target values from 0.0 to 1.0 were tested. The accuracy was taken from the range from 2 to 6 decimal places (0.005 to 0.0000005). The following set was used:

 0.999999, 0.000001, 0.25 0.33, 0.333, 0.3333, 0.33333, 0.333333, 0.333333333333, 0.666666666666, 0.777777777777, 0.090909090909, 0.263157894737, 0.606557377049, 0.745454545454, 0.000050183168565, pi - 3, e - 2.0, sqrt(2) - 1 

Resultados

I did 13 test runs. The result is in milliseconds needed for the whole data set.

  Run 1 Run 2 Run 3 Run 4 Run 5 Run 6 Run 7 Run 8 Run 9 Run 10 Run 11 Run 12 Run 13 1. 9091 9222 9070 9111 9091 9108 9293 9118 9115 9113 9102 9143 9121 2. 7071 7125 7077 6987 7126 6985 7037 6964 7023 6980 7053 7050 6999 3. 6903 7059 7062 6891 6942 6880 6882 6918 6853 6918 6893 6993 6966 4. 7546 7554 7564 7504 7483 7529 7510 7512 7517 7719 7513 7520 7514 5. 6839 6951 6882 6836 6854 6880 6846 7017 6874 6867 6828 6848 6864 

Conclusion (skipping the analysis)
Even without a statistical analysis, it’s easy to see that my algorithm is faster than the other tested algorithms. The difference with the fastest variant of “fast algorithm” however is less than 1 percent. The Improved slow algorithm is 30%-35% slower than the fastest algorithm”.

On the other hand, even the slowest algorithm performs a calculation on average in less than a microsecond. So under normal circumstances speed is not really an issue. In my opinion the best algorithm is mainly a matter of taste, so choose any of the tested algorithms on other criteria.

  • Does the algorithm gives the best result?
  • Is the algorithm available in my favorite language?
  • What is the code size of the algorithm?
  • Is the algorithm readable, understandable?

Source code

The source code below contains all used algorithms. It includes:

  • My original algorithm (with comments)
  • A even faster version of my algorithm (but less readable)
  • The original slow algorithm
  • All tested algorithms
 public class DoubleToFraction { // =================================================== // Sjaak algorithm - original version // public static Fraction SjaakOriginal(double value, double accuracy) { // Split value in a sign, an integer part, a fractional part int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; // check if the fractional part is near 0 double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); // check if the fractional part is near 1 double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); // The left fraction (a/b) is initially (0/1), the right fraction (c/d) is initially (1/1) // Together they form a Farey pair. // We will keep the left fraction below the minimumvalue and the right fraction above the maximumvalue int a = 0; int b = 1; int c = 1; int d = (int)(1 / maximumvalue); // The first interation is performed above. Calculate maximum n where (n*a+c)/(n*b+d) >= maximumvalue // This is the same as n <= 1/maximumvalue - 1, d will become n+1 = floor(1/maximumvalue) // repeat forever (at least until we cannot close in anymore) while (true) { // Close in from the left n times. // Calculate maximum n where (a+n*c)/(b+n*d) <= minimalvalue // This is the same as n <= (b * minimalvalue - a) / (cd*minimalvalue) int n = (int)((b * minimalvalue - a) / (c - d * minimalvalue)); // If we cannot close in from the left (and also not from the right anymore) the loop ends if (n == 0) break; // Update left fraction a += n * c; b += n * d; // Close in from the right n times. // Calculate maximum n where (n*a+c)/(n*b+d) >= maximumvalue // This is the same as n <= (c - d * maximumvalue) / (b * maximumvalue - a) n = (int)((c - d * maximumvalue) / (b * maximumvalue - a)); // If we cannot close in from the right (and also not from the left anymore) the loop ends if (n == 0) break; // Update right fraction c += n * a; d += n * b; } // We cannot close in anymore // The best fraction will be the mediant of the left and right fraction = (a+c)/(b+d) int denominator = b + d; return new Fraction(sign * (integerpart * denominator + (a + c)), denominator); } // =================================================== // Sjaak algorithm - faster version // public static Fraction SjaakFaster(double value, double accuracy) { int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); //int a = 0; int b = 1; //int c = 1; int d = (int)(1 / maximumvalue); double left_n = minimalvalue; // b * minimalvalue - a double left_d = 1.0 - d * minimalvalue; // c - d * minimalvalue double right_n = 1.0 - d * maximumvalue; // c - d * maximumvalue double right_d = maximumvalue; // b * maximumvalue - a while (true) { if (left_n < left_d) break; int n = (int)(left_n / left_d); //a += n * c; b += n * d; left_n -= n * left_d; right_d -= n * right_n; if (right_n < right_d) break; n = (int)(right_n / right_d); //c += n * a; d += n * b; left_d -= n * left_n; right_n -= n * right_d; } int denominator = b + d; int numerator = (int)(value * denominator + 0.5); return new Fraction(sign * (integerpart * denominator + numerator), denominator); } // =================================================== // Original Farley - Implemented by btilly // public static Fraction OriginalFarley(double value, double accuracy) { // Split value in a sign, an integer part, a fractional part int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; // check if the fractional part is near 0 double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); // check if the fractional part is near 1 double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); // The lower fraction is 0/1 int lower_numerator = 0; int lower_denominator = 1; // The upper fraction is 1/1 int upper_numerator = 1; int upper_denominator = 1; while (true) { // The middle fraction is (lower_numerator + upper_numerator) / (lower_denominator + upper_denominator) int middle_numerator = lower_numerator + upper_numerator; int middle_denominator = lower_denominator + upper_denominator; if (middle_denominator * maximumvalue < middle_numerator) { // real + error < middle : middle is our new upper upper_numerator = middle_numerator; upper_denominator = middle_denominator; } else if (middle_numerator < minimalvalue * middle_denominator) { // middle < real - error : middle is our new lower lower_numerator = middle_numerator; lower_denominator = middle_denominator; } else { return new Fraction(sign * (integerpart * middle_denominator + middle_numerator), middle_denominator); } } } // =================================================== // Modified Farley - Implemented by btilly, Kay Zed // public static Fraction ModifiedFarley(double value, double accuracy) { // Split value in a sign, an integer part, a fractional part int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; // check if the fractional part is near 0 double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); // check if the fractional part is near 1 double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); // The lower fraction is 0/1 int lower_numerator = 0; int lower_denominator = 1; // The upper fraction is 1/1 int upper_numerator = 1; int upper_denominator = 1; while (true) { // The middle fraction is (lower_numerator + upper_numerator) / (lower_denominator + upper_denominator) int middle_numerator = lower_numerator + upper_numerator; int middle_denominator = lower_denominator + upper_denominator; if (middle_denominator * maximumvalue < middle_numerator) { // real + error < middle : middle is our new upper ModifiedFarleySeek(ref upper_numerator, ref upper_denominator, lower_numerator, lower_denominator, (un, ud) => (lower_denominator + ud) * maximumvalue < (lower_numerator + un)); } else if (middle_numerator < minimalvalue * middle_denominator) { // middle < real - error : middle is our new lower ModifiedFarleySeek(ref lower_numerator, ref lower_denominator, upper_numerator, upper_denominator, (ln, ld) => (ln + upper_numerator) < minimalvalue * (ld + upper_denominator)); } else { return new Fraction(sign * (integerpart * middle_denominator + middle_numerator), middle_denominator); } } } private static void ModifiedFarleySeek(ref int a, ref int b, int ainc, int binc, Func f) { // Binary seek for the value where f() becomes false a += ainc; b += binc; if (f(a, b)) { int weight = 1; do { weight *= 2; a += ainc * weight; b += binc * weight; } while (f(a, b)); do { weight /= 2; int adec = ainc * weight; int bdec = binc * weight; if (!f(a - adec, b - bdec)) { a -= adec; b -= bdec; } } while (weight > 1); } } // =================================================== // Richards implementation by Jemery Hermann // public static Fraction RichardsJemeryHermann(double value, double accuracy, int maxIterations = 20) { // Split value in a sign, an integer part, a fractional part int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; // check if the fractional part is near 0 double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); // check if the fractional part is near 1 double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); // Richards - Implemented by Jemery Hermann double[] d = new double[maxIterations + 2]; d[1] = 1; double z = value; double n = 1; int t = 1; while (t < maxIterations && Math.Abs(n / d[t] - value) > accuracy) { t++; z = 1 / (z - (int)z); d[t] = d[t - 1] * (int)z + d[t - 2]; n = (int)(value * d[t] + 0.5); } return new Fraction(sign * (integerpart * (int)d[t] + (int)n), (int)d[t]); } // =================================================== // Richards implementation by Kennedy // public static Fraction RichardsKennedy(double value, double accuracy) { // Split value in a sign, an integer part, a fractional part int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; // check if the fractional part is near 0 double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); // check if the fractional part is near 1 double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); // Richards double z = value; int previousDenominator = 0; int denominator = 1; int numerator; do { z = 1.0 / (z - (int)z); int temp = denominator; denominator = denominator * (int)z + previousDenominator; previousDenominator = temp; numerator = (int)(value * denominator + 0.5); } while (Math.Abs(value - (double)numerator / denominator) > accuracy && z != (int)z); return new Fraction(sign * (integerpart * denominator + numerator), denominator); } // =================================================== // Richards implementation by Sjaak // public static Fraction RichardsOriginal(double value, double accuracy) { // Split value in a sign, an integer part, a fractional part int sign = value < 0 ? -1 : 1; value = value < 0 ? -value : value; int integerpart = (int)value; value -= integerpart; // check if the fractional part is near 0 double minimalvalue = value - accuracy; if (minimalvalue < 0.0) return new Fraction(sign * integerpart, 1); // check if the fractional part is near 1 double maximumvalue = value + accuracy; if (maximumvalue > 1.0) return new Fraction(sign * (integerpart + 1), 1); // Richards double z = value; int denominator0 = 0; int denominator1 = 1; int numerator0 = 1; int numerator1 = 0; int n = (int)z; while (true) { z = 1.0 / (z - n); n = (int)z; int temp = denominator1; denominator1 = denominator1 * n + denominator0; denominator0 = temp; temp = numerator1; numerator1 = numerator1 * n + numerator0; numerator0 = temp; double d = (double)numerator1 / denominator1; if (d > minimalvalue && d < maximumvalue) break; } return new Fraction(sign * (integerpart * denominator1 + numerator1), denominator1); } } 

Here’s an algorithm implemented in VB that converts Floating Point Decimal to Integer Fraction that I wrote many years ago.

Basically you start with a numerator = 0 and a denominator = 1, then if the quotient is less than the decimal input, add 1 to the numerator and if the quotient is greater than the decimal input, add 1 to the denominator. Repeat until you get within your desired precision.

If I were you I’d handle the “no repeating decimals in .NET” problem by having it convert strings with the recurrence marked somehow.

Eg 1/3 could be represented “0.R3” 1/60 could be represented “0.01R6”

I’d require an explicit cast from double or decimal because such values could only be converted into a fraction that was close. Implicit cast from int is ok.

You could use a struct and store your fraction (f) in two longs p and q such that f=p/q, q!=0, and gcd(p, q) == 1.

Here, you can have the method for converting Decimal into Fractions:

 ///  /// Converts Decimals into Fractions. ///  /// Decimal value /// Fraction in string type public string DecimalToFraction(double value) { string result; double numerator, realValue = value; int num, den, decimals, length; num = (int)value; value = value - num; value = Math.Round(value, 5); length = value.ToString().Length; decimals = length - 2; numerator = value; for (int i = 0; i < decimals; i++) { if (realValue < 1) { numerator = numerator * 10; } else { realValue = realValue * 10; numerator = realValue; } } den = length - 2; string ten = "1"; for (int i = 0; i < den; i++) { ten = ten + "0"; } den = int.Parse(ten); num = (int)numerator; result = SimplifiedFractions(num, den); return result; } ///  /// Converts Fractions into Simplest form. ///  /// Numerator /// Denominator /// Simplest Fractions in string type string SimplifiedFractions(int num, int den) { int remNum, remDen, counter; if (num > den) { counter = den; } else { counter = num; } for (int i = 2; i <= counter; i++) { remNum = num % i; if (remNum == 0) { remDen = den % i; if (remDen == 0) { num = num / i; den = den / i; i--; } } } return num.ToString() + "/" + den.ToString(); } } 

Here’s an algorithm I wrote for a project not too long ago. It takes a different approach, which is more akin to something you would do by hand. I can’t guarantee its efficiency, but it gets the job done.

  public static string toFraction(string exp) { double x = Convert.ToDouble(exp); int sign = (Math.Abs(x) == x) ? 1 : -1; x = Math.Abs(x); int n = (int)x; // integer part x -= n; // fractional part int mult, nm, dm; int decCount = 0; Match m = Regex.Match(Convert.ToString(x), @"([0-9]+?)\1+.?$"); // repeating fraction if (m.Success) { m = Regex.Match(m.Value, @"([0-9]+?)(?=\1)"); mult = (int)Math.Pow(10, m.Length); // We have our basic fraction nm = (int)Math.Round(((x * mult) - x)); dm = mult - 1; } // get the number of decimal places else { double t = x; while (t != 0) { decCount++; t *= 10; t -= (int)t; } mult = (int)Math.Pow(10, decCount); // We have our basic fraction nm = (int)((x * mult)); dm = mult; } // can't be simplified if (nm < 0 || dm < 0) return exp; //Simplify Stack factors = new Stack(); for (int i = 2; i < nm + 1; i++) { if (nm % i == 0) factors.Push(i); // i is a factor of the numerator } // check against the denominator, stopping at the highest match while(factors.Count != 0) { // we have a common factor if (dm % (int)factors.Peek() == 0) { int f = (int)factors.Pop(); nm /= f; dm /= f; break; } else factors.Pop(); } nm += (n * dm); nm *= sign; if (dm == 1) return Convert.ToString(nm); else return Convert.ToString(nm) + "/" + Convert.ToString(dm); } 

Simple solution/breakdown of repeating decimal.

I took the logic that the numbers 1-9 divided by 9 are repeating. AKA 7/9 = .77777

My solution would be to multiply the whole number by 9, add the repeating number, and then divide by 9 again.

  Ex: 28.66666 28*9=252 252+6=258 258/9=28.66666 

This method is rather easy to program as well. Truncate decimal digit, multiply by 9, add first decimal, then divide by 9.

The only thing missing is that the fraction may need to be simplified if the left number is dividable by 3.

Here are two Swift 4 conversions of popular answers to this problem:

 public func decimalToFraction(_ d: Double) -> (Int, Int) { var df: Double = 1 var top: Int = 1 var bot: Int = 1 while df != d { if df < d { top += 1 } else { bot += 1 top = Int(d * bot) } df = top / bot } return (top, bot) } public func realToFraction(_ value: Double, accuracy: Double = 0.00005) -> (Int, Int)? { var value = value guard accuracy >= 0 && accuracy <= 1 else { Swift.print(accuracy, "Must be > 0 and < 1.") return nil } let theSign = sign(value) if theSign == -1 { value = abs(value) } // Accuracy is the maximum relative error; convert to absolute maxError let maxError = theSign == 0 ? accuracy : value * accuracy let n = floor(value) value -= n if value < maxError { return (Int(theSign * n), 1) } if 1 - maxError < value { return (Int(theSign * (n + 1)), 1) } // The lower fraction is 0/1 var lowerN: Double = 0 var lowerD: Double = 1 // The upper fraction is 1/1 var upperN: Double = 1 var upperD: Double = 1 while true { // The middle fraction is (lowerN + upperN) / (lowerD + upperD) let middleN = lowerN + upperN let middleD = lowerD + upperD if middleD * (value + maxError) < middleN { // real + error < middle : middle is our new upper upperN = middleN upperD = middleD } else if middleN < (value - maxError) * middleD { // middle < real - error : middle is our new lower lowerN = middleN lowerD = middleD } else { // Middle is our best fraction return (Int(n * middleD + middleN * theSign), Int(middleD)) } } }