Algoritmo para detectar decimales repetidos?

Question

¿Hay un algoritmo para averiguar las siguientes cosas?

1. Si el resultado de una división es un decimal que se repite (en binario).
2. Si se repite, ¿a qué dígito (representado como potencia de 2) comienza la repetición?
3. ¿Qué dígitos se repiten?

Algunos ejemplos:

1/2 = 1/10 = 0.1 // 1 = false, 2 = N/A, 3 = N/A, 4 = N/A 
1/3 = 1/11 = 0.010101... // 1 = true, 2 = -2, 3 = 10 
2/3 = 10/11 = 0.101010... // 1 = true, 2 = -1, 3 = 10 
4/3 = 100/11 = 1.010101... // 1 = true, 2 = 0, 3 = 10 
1/5 = 1/101 = 0.001100110011... // 1 = true, 2 = -3, 3 = 1100 

¿Hay una manera de hacer esto? La eficiencia es una gran preocupación. Una descripción del algoritmo sería preferible al código, pero tomaré la respuesta que pueda obtener.

También vale la pena señalar que la base no es un gran problema; Puedo convertir el algoritmo en binario (o si está en, por ejemplo, base 256 para usar char s por facilidad, podría usarlo). Digo esto porque si estás explicando podría ser más fácil para ti explicar en la base 10 :).

Answer 1

Para encontrar el patrón de repetición, simplemente no perder de vista los valores que utiliza a lo largo de la línea:

1/5 = 1/101: 

1 < 101 => 0 
(decimal separator here) 
10 < 101 => 0 
100 < 101 => 0 
1000 >= 101 => 1 

    1000 - 101 = 11 

110 >= 101 => 1 

    110 - 101 = 1 

10 -> match 

Al llegar al mismo valor que el que tenía en el segundo bit, el proceso simplemente se repetirá a partir de ese punto produciendo el mismo patrón de bits una y otra vez. Tiene el patrón "0011" repitiendo desde el segundo bit (primero después del separador decimal).

Si desea que el patrón se inicia con un "1", que sólo puede girar hasta que coincida con esa condición:

"0011" from the second bit 
"0110" from the third bit 
"1100" from the fourth bit 

Editar:
Ejemplo en C#:

void FindPattern(int n1, int n2) { 
    int digit = -1; 
    while (n1 >= n2) { 
     n2 <<= 1; 
     digit++; 
    } 
    Dictionary<int, int> states = new Dictionary<int, int>(); 
    bool found = false; 
    while (n1 > 0 || digit >= 0) { 
     if (digit == -1) Console.Write('.'); 
     n1 <<= 1; 
     if (states.ContainsKey(n1)) { 
     Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty); 
     Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit); 
     found = true; 
     break; 
     } 
     states.Add(n1, digit); 
     if (n1 < n2) { 
     Console.Write('0'); 
     } else { 
     Console.Write('1'); 
     n1 -= n2; 
     } 
     digit--; 
    } 
    if (!found) { 
     Console.WriteLine(); 
     Console.WriteLine("No repeat."); 
    } 
} 

Llamado con los ejemplos que salidas:

.1 
No repeat. 
.01 
Repeat from digit -1 length 2. 
.10 
Repeat from digit -1 length 2. 
1.0 
Repeat from digit 0 length 2. 
.0011 
Repeat from digit -1 length 4. 

Answer 2

1. si el divisor no es una potencia de 2 (en general, contiene factores primos no compartidas con la base de la representación)
2. repetición de la duración del ciclo será impulsado por el factor primo más grande del dividendo (pero no conectado con la longitud de la representación de ese factor - vea 1/7 en decimal), pero la longitud del primer ciclo puede diferir de la unidad de repetición (ej. 11/28 = 1/4 + 1/7 en decimal).
3. el ciclo real dependerá del numerador.

Answer 3

Consulte decimal expansion, y específicamente sobre el período de una fracción.

Answer 4

Puedo dar una pista: los decimales de repetición en la base diez son todos fracciones con el denominador que tiene al menos un factor primo distinto de dos y cinco. Si el denominador no contiene factores primos dos o cinco, siempre se pueden representar con un denominador de todos los nueves. Entonces el nominador es la parte que se repite y el número de nueves es la longitud de la parte que se repite.

3  _ 
- = 0.3 
9 

1 142857  ______ 
- = ------ = 0.142857 
7 999999 

Si hay dos factores primos o cinco en el denominador, la parte de repetición no comienza en la primera posición.

17 17  ______ 
-- = ----- = 0.4857142 
35 5 * 7 

Pero no recuerdo cómo derivar la parte que no se repite y su longitud.

Esto parece traducirse bien a la base dos. Solo la fracción con una potencia de dos denominador no se repite. Esto se puede verificar fácilmente al afirmar que solo se establece un bit en el denominador.

1/2 = 1/10 = 0.1 
1/4 = 1/100 = 0.01 
3/4 = 11/100 = 0.11 
5/8 = 101/1000 = 0.101 

Todo fracción con denominadores impares debería repetirse y el patrón y su longitud se puede obtener mediante la expresión de la fracción con un denominador en forma 2^n-1.

             __ 
1/3   = 1/(2^2-1) =  1/11  = 0.01 
                __ 
2/3   = 2/(2^2-1) =  10/11  = 0.10 
         __ 
4/3 => 1 + 1/3 => 1.01 
         __ 
10/3 => 3 + 1/3 => 11.01 
                ____ 
1/5 = 3/15 = 3/(2^4-1) =  11/1111  = 0.0011 
                ________ 
11/17 = 165/255 = 11/(2^8-1) = 10100101/11111111 = 0.10100101 

En cuanto a la base diez, no puedo decirle cómo manejar denominadores contienen, pero no ser una potencia de dos - por ejemplo, 12 = 3 * 2^2.

Answer 5

En primer lugar, uno de sus ejemplos es incorrecto. La parte repetitiva de 1/5 es 0011 en lugar de 1100, y comienza al principio de la parte fraccionaria.

Un decimal periódico es algo así como:

a/b = c + d(2-n + 2-n-k + 2-n-2k + ...)
    = c + 2-n * d/(1 - 2-k)

en el que n y d son lo que desea.

Por ejemplo,

1/10(dec) = 1/1010(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011

se puede representar por la fórmula con

a = 1, b = 10(dec), c = 0, d = 0.0011(bin), n = 1, k = 4;
(1 - 2-k) = 0.1111

Por lo tanto, 1/10 = 0.1 * 0.0011/0.1111. La parte clave de una representación decimal repetitiva se genera dividiendo por (2n - 1) o su múltiplo de 2. Así que puede encontrar la manera de expresar su denominador como tal (como construir tablas constantes), o hacer una división de números grandes (que es relativamente lento) y encuentra el ciclo. No hay una manera rápida de hacer esto.

Answer 6

Usted ca n haga un long division, anotando los restos. La estructura de los restos le dará la estructura de cualquier decimal racional:

1. el último resto es cero: es un número decimal sin ninguna parte que se repite
2. el primero y el último resto son iguales: la decimal está repitiendo derecha después del punto
3. la distancia entre el primero y el primer resto igual a la última son los dígitos que no se repite, el resto es la parte que se repite

En general las distancias wi Te daré la cantidad de dígitos para cada parte.

Se puede ver este algoritmo codificado en C++ en el método decompose()here.

Try228142/62265, que tiene un período de dígitos!