Алгоритм обнаружения повторяющихся десятичных знаков?

Question

Есть ли алгоритм для выяснения следующих вещей?

1. Если результат деления является повторяющимся десятичным числом (в двоичном виде). ​​
2. Если оно повторяется, с какой цифры (представленной как степень 2) начинается повторение?
3. Какие цифры повторяются?

Некоторые примеры:

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

Есть ли способ сделать это? Эффективность - большая проблема. Описание алгоритма предпочтительнее кода, но я приму ответ, который смогу получить.

Стоит также отметить, что база не имеет большого значения; Я могу преобразовать алгоритм в двоичный файл (или, если он, скажем, в базе 256, использовать для простоты char s, я мог бы просто использовать это) Я говорю это потому, что если вы объясняете, вам может быть проще объяснить в базе 10:).

Answer 1

1. если делитель не является степенью 2 (обычно содержит простые факторы, не разделяемые с базой представления)
2. длина цикла повторения будет зависеть от наибольшего простого множителя дивиденда (но не связана с длиной представления этого фактора - см. 1/7 в десятичном виде), но длина первого цикла может отличаться от повторения единица измерения (например, 11/28 = 1/4 + 1/7 в десятичном виде). ​​
3. фактический цикл будет зависеть от числителя.

Answer 2

Я могу дать подсказку - повторяющиеся десятичные дроби в десятичной базе являются дробными со знаменателем, имеющим по крайней мере один простой множитель, кроме двух и пяти. Если знаменатель не содержит двух или пяти простых множителей, они всегда могут быть представлены знаменателем всех девяток. Тогда знаменатель - это повторяющаяся часть, а число девяток - это длина повторяющейся части.

3     _
- = 0.3
9

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

Если в знаменателе есть простые множители два или пять, повторяющаяся часть начинается не с первой позиции.

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

Но я не могу вспомнить, как получить неповторяющуюся часть и ее длину.

Кажется, это хорошо подходит для второй базы. Только дробь со степенью два знаменателя являются неповторяющимися. Это легко проверить, утверждая, что в знаменателе установлен только один бит.

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

Все дроби с нечетными знаменателями должны повторяться, и шаблон и его длину можно получить, выразив дробь со знаменателем в виде 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

Что касается основы десять, я не могу сказать, как обращаться со знаменателями, содержащими, но не являющимися степенью двойки - например, 12 = 3 * 2^2.

Answer 3

Прежде всего, один из ваших примеров неверен. Повторяющаяся часть 1/5 является 0011, а не 1100, и начинается в самом начале дробной части.

Повторяющаяся десятичная дробь - это что-то вроде:

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

, в котором n и d - это то, что вы хотите.

Например,

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

может быть представлен формулой с

a = 1, b = 10<sub>(dec)</sub>, c = 0, d = 0.0011<sub>(bin)</sub>, n = 1, k = 4; <br /> (1 - 2<sup>-k</sup>) = 0.1111

Следовательно, 1/10 = 0.1 * 0.0011/0.1111. Ключевая часть повторяющегося десятичного представления генерируется делением на (2<sup>n</sup> - 1) или его кратным 2. Таким образом, вы можете найти способ выразить свой знаменатель как таковой (например, построить таблицы констант) или выполнить деление большого числа что относительно медленно) и найти петлю. Нет быстрого способа сделать это.

Answer 4

Проверьте десятичное расширение , а именно о периоде дроби.

Answer 5

Вы можете сделать длинное деление , отметив остатки. Структура остатков даст вам структуру любого рационального десятичного числа :

1. последний остаток равен нулю: это десятичная дробь без повторяющейся части
2. первый и последний остаток равны: десятичная дробь повторяется сразу после точки
3. расстояние между первым и первым остатком, равное последнему, является неповторяющимися цифрами, остаток является повторяющейся частью

Как правило, расстояния дают количество цифр для каждой части.

Вы можете увидеть этот алгоритм, закодированный в C ++ в методе decompose() здесь .

Попробуйте 228142/62265, он имеет период 1776 цифр!

Answer 6

Чтобы найти повторяющийся шаблон, просто следите за значениями, которые вы используете вдоль линии:

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

Когда вы достигнете того же значения, что и во втором бите, процесс просто повторяется с этой точки, производя один и тот же битовый шаблон снова и снова. У вас есть шаблон «0011», повторяющийся со второго бита (первый после десятичного разделителя).

Если вы хотите, чтобы паттерн начинался с «1», вы можете просто вращать его, пока он не будет соответствовать этому условию:

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

Edit:
Пример в 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.");
   }
}

Вызывается с вашими примерами и выводит:

.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.