¿Cómo saber el decimal que se repite en una fracción?

Ya sé cuando una fracción está repitiendo decimales. Aquí está la función.

public bool IsRepeatingDecimal { get { if (Numerator % Denominator == 0) return false; var primes = MathAlgorithms.Primes(Denominator); foreach (int n in primes) { if (n != 2 && n != 5) return true; } return false; } } 

Ahora, estoy tratando de obtener el número repetido. Estoy revisando este sitio web: http://en.wikipedia.org/wiki/Repeating_decimal

 public decimal RepeatingDecimal() { if (!IsRepeatingDecimal) throw new InvalidOperationException("The fraction is not producing repeating decimals"); int digitsToTake; switch (Denominator) { case 3: case 9: digitsToTake = 1; break; case 11: digitsToTake = 2; break; case 13: digitsToTake = 6; break; default: digitsToTake = Denominator - 1; break; } return MathExtensions.TruncateAt((decimal)Numerator / Denominator, digitsToTake); } 

Pero realmente me di cuenta de que algunos números tienen un finito decimal parcial y más tarde infinito. Por ejemplo: 1/28

¿Conoces una mejor manera de hacer esto? ¿O un algoritmo?

Un algoritmo muy simple es este: implementar una división larga. Registre cada división intermedia que haga. Tan pronto como veas una división idéntica a la que has hecho antes, tienes lo que se repite.

Ejemplo: 7/13.

 1. 13 goes into 7 0 times with remainder 7; bring down a 0. 2. 13 goes into 70 5 times with remainder 5; bring down a 0. 3. 13 goes into 50 3 times with remainder 11; bring down a 0. 4. 13 goes into 110 8 times with remainder 6; bring down a 0. 5. 13 goes into 60 4 times with remainder 8; bring down a 0. 6. 13 goes into 80 6 times with remainder 2; bring down a 0. 7. 13 goes into 20 1 time with remainder 7; bring down a 0. 8. We have already seen 13/70 on line 2; so lines 2-7 have the repeating part 

El algoritmo nos da 538461 como la parte repetitiva. Mi calculadora dice 7/13 es 0.538461538. ¡Me parece bien! ¡Todo lo que queda son detalles de implementación, o para encontrar un mejor algoritmo!

Si tienes un numerator / denominator fracción reducida (positivo), la expansión decimal de la fracción termina si y solo si el denominator no tiene un factor primo distinto de 2 o 5. Si tiene otro factor primo, la expansión decimal será periódica. Sin embargo, los casos en que el denominador es divisible por al menos uno de 2 y 5 y donde no se da lugar a comportamientos ligeramente diferentes. Tenemos tres casos:

  1. denominator = 2^a * 5^b , luego la expansión decimal termina max {a, b} dígitos después del punto decimal.
  2. denominator = 2^a * 5^b * m donde m > 1 no es divisible por 2 o por 5, entonces la parte fraccional de las expansiones decimales consta de dos partes, el pre-período de longitud max {a, b} y el período, cuya longitud está determinada por m e independiente del numerador.
  3. denominator > 1 no es divisible por 2 o por 5, entonces la expansión decimal es puramente periódica, lo que significa que el período comienza inmediatamente después del punto decimal.

El tratamiento de los casos 1. y 2. tiene una parte común, deje c = max {a, b} , luego

 numerator / denominator = (numerator * 2^(ca) * 5^(cb)) / (10^c * m) 

donde m = 1 para el caso 1. Observe que uno de los factores 2^(ca) y 5^(cb) con el que multiplicamos el numerador es 1. Luego obtiene la expansión decimal expandiendo

 (numerator * 2^(ca) * 5^(cb)) / m 

y desplazando el punto decimal c hacia la izquierda. En el primer caso ( m = 1 ) esa parte es trivial.

El tratamiento de los casos 2. y 3. también tiene una parte común, el cálculo de una fracción

 n / m 

donde n no tienen un factor primo común ( m > 1 ). Podemos escribir n = q*m + r con 0 <= r < m (división con rest, r = n % m ), q es la parte integral de la fracción y bastante poco interesante.

Dado que la fracción se supone reducida, tenemos r > 0 , por lo que queremos encontrar la expansión de una fracción r / m donde 0 < r < m m no es divisible por 2 ni por 5. Como se mencionó anteriormente, dicha expansión es puramente periódico, por lo que encontrar el período significa encontrar la expansión completa.

Vamos a buscar el período heurísticamente. Entonces, k sea ​​la duración del período (más corto) p = d_1d1_2...d_k el período. Asi que

 r / m = 0.d_1d_2...d_kd_1d_2...d_kd_1... = (d_1d_2...d_k)/(10^k) + (d_1d_2...d_k)/(10^(2k)) + (d_1d_2...d_k)/(10^(3k)) + ... = p/(10^k) * (1 + 1/(10^k) + 1/(10^(2k)) + 1/(10^(3k)) + ...) 

El último término es una serie geométrica, 1 + q + q^2 + q^3 + ... que, para |q| < 1 |q| < 1 tiene la sum 1/(1-q) . En nuestro caso, 0 < q = 1/(10^k) < 1 , entonces la sum es 1 / (1 - 1/(10^k)) = 10^k / (10^k-1) . Por lo tanto, hemos visto eso

 r / m = p / (10^k-1) 

Como r y m no tienen un factor común, eso significa que hay una s con 10^k - 1 = s*m y p = s*r . Si conocemos k , la duración del período, podemos simplemente encontrar los dígitos del período calculando

 p = ((10^k - 1)/m) * r 

y relleno con ceros a la izquierda hasta que tengamos k dígitos. (Nota: es así de simple solo si k es suficientemente pequeño o está disponible un tipo de entero grande. Para calcular el período de, por ejemplo, 17/983 con tipos enteros de ancho fijo estándar, utilice la división larga como se explica en @ Patrick87).

Por lo tanto, queda por encontrar la duración del período. Podemos revertir el razonamiento anterior y encontrar que si m divide 10^u - 1 , entonces podemos escribir

 r / m = t/(10^u - 1) = t/(10^u) + t/(10^(2u)) + t/(10^(3u)) + ... = 0.t_1t_2...t_ut_1t_2...t_ut_1... 

y r/m tiene un período de longitud u . Entonces la duración del período más corto es el mínimo positivo u tal que m divide 10^u - 1 , o, dicho de otra manera, el menor positivo u tal que 10^u % m == 1 .

Podemos encontrarlo en O (m) vez con

 u = 0; a = 1; do { ++u; a = (10*a) % m; while(a != 1); 

Ahora, encontrar la longitud del período de esa manera no es más eficiente que encontrar los dígitos y la longitud del período junto con la división larga, y para m suficientemente pequeño, ese es el método más eficiente.

 int[] long_division(int numerator, int denominator) { if (numerator < 1 || numerator >= denominator) throw new IllegalArgumentException("Bad call"); // now we know 0 < numerator < denominator if (denominator % 2 == 0 || denominator % 5 == 0) throw new IllegalArgumentException("Bad denominator"); // now we know we get a purely periodic expansion int[] digits = new int[denominator]; int k = 0, n = numerator; do { n *= 10; digits[k++] = n / denominator; n = n % denominator; }while(n != numerator); int[] period = new int[k]; for(n = 0; n < k; ++n) { period[n] = digits[n]; } return period; } 

Eso funciona siempre que 10*(denominator - 1) no se desborde, por supuesto int podría ser un entero de 32 o 64 bits según sea necesario.

Pero para los denominadores grandes, eso es ineficiente, uno puede encontrar la duración del período y también el período más rápido al considerar la factorización prima del denominador. En cuanto a la duración del período,

  • Si el denominador es una potencia principal, m = p^k , la duración del período de r/m es un divisor de (p-1) * p^(k-1)
  • Si a y b son coprime y m = a * b , la duración del período de r/m es el múltiplo menos común de las duraciones del período de 1/a y 1/b .

Tomados en conjunto, la duración del período de r/m es un divisor de λ(m) , donde λ es la función Carmichael .

Para encontrar la longitud de período de r/m , encuentre la factorización prima de m y para todos los factores de potencia principales p^k , encuentre el período de 1/(p^k) - equivalentemente, el orden multiplicativo de 10 módulo p^k , que se sabe que es un divisor de (p-1) * p^(k-1) . Como tales números no tienen muchos divisores, eso se hace rápidamente. Luego encuentra el mínimo común múltiplo de todos estos.

Para el período en sí (los dígitos), si está disponible un tipo de entero grande y el período no es demasiado largo, la fórmula

 p = (10^k - 1)/m * r 

es una forma rápida de calcularlo. Si el período es demasiado largo o no hay ningún tipo de entero grande disponible, calcular los dígitos de manera eficiente es más desordenado y, por encima de mi cabeza, no recuerdo cómo se hace exactamente eso.

Una forma sería repetir la forma en que se hace la división larga a mano, y anotar el rest en cada etapa. Cuando el rest se repite, el rest del proceso debe repetirse también. Por ejemplo, los dígitos de 1.0 / 7 son 0.1 rest 3 luego 0.14 rest 2 luego 0.142 rest 6 luego 0.1428 rest 4 luego 0.14285 rest 5 luego 0.142857 rest 1 que es el 1 que comienza nuevamente y entonces obtienes 0.1428571 rest 3 y repite de nuevo desde allí.

El algoritmo de división larga es bastante bueno, así que no tengo nada que agregar allí.

Pero tenga en cuenta que su algoritmo IsRepeatingDecimal puede no funcionar y es ineficaz.

No funcionará si su fracción no es irreductible, es decir, si existe un número entero mayor que 1 que divide tanto su numerador como su denominador. Por ejemplo, si alimenta 7/14, su algoritmo devolverá verdadero cuando debería devolver falso.

Para reducir su fracción, encuentre el gcd entre el numerador y el denominador y divida ambos por este gcd.

Si supone que la fracción es irreductible, entonces su prueba

 if (Numerator % Denominator == 0) 

simplemente puede ser reemplazado con

 if (Denominator == 1) 

Pero eso sigue siendo innecesario, ya que si Denominator es 1, entonces su lista ‘primos’ va a estar vacía y su algoritmo volverá falso de todos modos.

Finalmente, llamar a MathAlgorithms.Primes (Denominador) va a ser costoso para grandes cantidades y se puede evitar. De hecho, todo lo que necesita hacer es dividir su denominador entre 5 (respectivamente 2) hasta que ya no sea divisible entre 5 (o 2). Si el resultado final es 1, devuelve falso, de lo contrario, devuelve verdadero.