какой эффективный способ найти повторяющиеся десятичные

24

Я пытаюсь найти эффективный алгоритм в Java, чтобы найти повторяющуюся десятичную часть двух целых чисел aи bгде a/b.

например. 5/7 = 0,714258 714258 ....

В настоящее время я знаю только метод длинного деления.

Июнь хао
источник
2
Итак, у вас есть a = 5 и b = 7, и вы можете достаточно легко вычислить a / b в плавающей запятой, но что вы хотите знать, это то, что оно повторяется после 6 десятичных знаков?
Спарр

Ответы:

10

Я полагаю, что здесь есть два основных подхода: вы можете «грубой силой» искать самую длинную повторяющуюся строку или решить ее как проблему теории чисел.

Прошло много времени с тех пор, как я сталкивался с этой проблемой, но особый случай (1 / n) - это проблема № 26 в Project Euler, поэтому вы можете найти больше информации, найдя эффективные решения для этого конкретного имени. Один поиск приводит нас к веб-сайту Эли Бендерски, где он объясняет свое решение . Вот некоторые из теории на странице десятичных расширений Mathworld :

Любая нерегулярная дробь m/nявляется периодической и имеет период, не lambda(n)зависящий от m, длиной не более n-1 цифры. Если nвзаимно простое с 10, то период lambda(n)из m/nявляется делителем phi(n)и имеет в большинстве phi(n)цифр, где phiэто функция totient. Оказывается, что lambda(n)это мультипликативный порядок 10 (мод n) (Glaisher 1878, Лехмер 1941). Количество цифр в повторяющейся части десятичного разложения рационального числа также можно найти непосредственно по мультипликативному порядку его знаменателя.

Моя теория чисел в настоящее время немного заржавела, поэтому лучшее, что я могу сделать, это указать вам в этом направлении.

Даниэль Б
источник
8

Давай n < d, а ты пытаешься выяснить повторяющуюся часть n/d. Позвольте pбыть количество цифр в повторяющейся части: затем n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). Часть в скобках представляет собой геометрический ряд, равный 1/(10^p - 1).

Так n / d = R / (10^p - 1). Переставь, чтобы получить R = n * (10^p - 1) / d. Чтобы найти R, сделайте цикл pот 1 до бесконечности и остановитесь, как только dделится равномерно n * (10^p - 1).

Вот реализация в Python:

def f(n, d):
    x = n * 9
    z = x
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1
    return k, z / d

( kотслеживает длину повторяющейся последовательности, чтобы вы могли различать, например, от 1/9 до 1/99)

Обратите внимание, что эта реализация (по иронии судьбы) зацикливается навсегда, если десятичное расширение конечно, но завершается, если оно бесконечно! Вы можете проверить этот случай, хотя, потому что n/dбудет иметь конечное десятичное представление, только если все основные факторы dэтого не 2 или 5 присутствуют в n.

VALTRON
источник
1
Этот ответ кажется правильным. Метод основан на следующем «правиле»: 0.123123... = 123/999 0.714258714258... = 714258/999999 (=5/7)и т. Д.
ПОСЛЕ
4
Это терпит неудачу случаи как 1/6 или 5/12: \
razpeitia
1
@razpeitia Я сделал что-то похожее, но работаю во всех случаях (включая целочисленное деление). Проверьте: codepad.org/hKboFPd2
Тигран Салуев
Я сделал реализацию javascript, похожую на @ TigranSaluev's, на github.com/Macil/cycle-division
Macil,
2

Длинное деление? : /

Превратите результат в строку, а затем примените этот алгоритм к нему. Используйте BigDecimal, если ваша строка недостаточно длинна для обычных типов.

Роберт Харви
источник
4
«Превратить его в строку» может потребовать вычислений произвольной точности и очень длинной строки для вычисления двух копий повторяющейся части строки (и как узнать, когда прекратить вычисление? .121212312121231212123 ... будет проблемой)
Спарр
@Sparr Длина повторения всегда меньше знаменателя.
@MichaelT Я не знал об этом. Если это правда, точность не является точно «произвольной», но может быть сколь угодно высокой в ​​зависимости от знаменателя.
Спарр
@Sparr math.stackexchange.com/questions/298844/... хотя я нахожу everything2.com/title/recurring+decimal более читаемым.
Я не думаю, что алгоритм, на который вы ссылаетесь, будет работать без изменений. Он включает в себя повторы, которые перекрываются, и он ищет всю строку (не только для последовательных совпадений). Например, самая длинная повторяющаяся подстрока в «банане» - это «ана».
Web_Designer