jaki jest skuteczny sposób na znalezienie powtarzającego się miejsca po przecinku

Próbuję znaleźć skuteczny algorytm w Javie, aby znaleźć powtarzającą się część dziesiętną dwóch liczb całkowitych ai bgdzie a/b.

na przykład. 5/7 = 0,714258 714258 ....

Obecnie znam tylko metodę długiego podziału.

Uważam, że istnieją tutaj dwa ogólne podejścia, możesz zasadniczo „brutalną siłą” szukać najdłuższego powtarzającego się łańcucha lub możesz rozwiązać go jako problem teorii liczb.

Dawno nie natknąłem się na ten problem, ale szczególny przypadek (1 / n) to problem nr 26 w Project Euler, więc możesz znaleźć więcej informacji, szukając skutecznych rozwiązań dla tej konkretnej nazwy. Jedno wyszukiwanie prowadzi nas do strony Eli Bendersky'ego, gdzie wyjaśnia swoje rozwiązanie . Oto niektóre teorie ze strony dziesiętnych rozszerzeń Mathworld :

Każda nieregularna część m/njest okresowa i ma okres lambda(n)niezależny m, który ma co najwyżej n-1 cyfry. Jeśli njest stosunkowo prime do 10, następnie okres lambda(n)od m/njest dzielnikiem phi(n)i ma co najwyżej phi(n)cyfr, gdzie phijest funkcja totient. Okazuje się, że lambda(n)jest to multiplikatywna kolejność 10 (mod n) (Glaisher 1878, Lehmer 1941). Liczbę cyfr w powtarzalnej części rozwinięcia dziesiętnego liczby wymiernej można również znaleźć bezpośrednio z multiplikatywnej kolejności jej mianownika.

Moja teoria liczb jest w tej chwili trochę zardzewiała, więc najlepsze, co mogę zrobić, to skierować cię w tym kierunku.

Pozwól n < d, a ty próbujesz wymyślić powtarzającą się część n/d. Niech pbędzie liczbą cyfr w powtarzającej się części: wtedy n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). Część w nawiasach jest serią geometryczną równą 1/(10^p - 1).

Tak n / d = R / (10^p - 1). Zmień kolejność, aby uzyskać R = n * (10^p - 1) / d. Aby znaleźć R, zapętlić pod 1 do nieskończoności i zatrzymać, gdy tylko drównomiernie się dzieli n * (10^p - 1).

Oto implementacja w Pythonie:

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śledzi długość powtarzającej się sekwencji, dzięki czemu można na przykład odróżnić od 1/9 do 1/99)

Zauważ, że ta implementacja (jak na ironię) zapętla się na zawsze, jeśli rozwinięcie dziesiętne jest skończone, ale kończy się, jeśli jest nieskończone! Możesz jednak sprawdzić ten przypadek, ponieważ n/dbędzie miał skończoną reprezentację dziesiętną tylko wtedy, gdy wszystkie czynniki pierwsze, dktóre nie są 2 lub 5, są również obecne n.

Dzielenie liczb wielocyfrowych? : /

Zamień wynik w ciąg, a następnie zastosuj do niego ten algorytm . Użyj BigDecimal, jeśli ciąg nie jest wystarczająco długi dla zwykłych typów.