qual é uma maneira eficiente de encontrar casas decimais repetidas

24

Eu estou tentando encontrar um algoritmo eficiente em Java para encontrar a parte decimal de repetição de dois números inteiros ae bonde a/b.

por exemplo. 5/7 = 0,714258 714258 ....

Atualmente, só conheço o método de divisão longa.

Jun Hao
fonte
2
Então você tem a = 5 eb = 7 e pode calcular a / b em ponto flutuante com bastante facilidade, mas o que você quer saber é que ele se repete após 6 casas decimais?
precisa

Respostas:

10

Acredito que existem duas abordagens gerais aqui, você pode essencialmente "força bruta" procurar a sequência mais longa de repetição ou pode resolvê-la como um problema da teoria dos números.

Já faz muito tempo que não encontrei esse problema, mas um caso especial (1 / n) é o problema nº 26 no Projeto Euler, portanto, você poderá encontrar mais informações pesquisando soluções eficientes para esse nome específico. Uma pesquisa nos leva ao site de Eli Bendersky, onde ele explica sua solução . Aqui está um pouco da teoria da página Decimal Expansions da Mathworld :

Qualquer fração não regular m/né periódica e possui um período lambda(n)independente de m, que tem no máximo n-1 dígitos. Se nfor relativamente primo a 10, o período lambda(n)de m/né um divisor de phi(n)e tem no máximo phi(n)dígitos, onde phiestá a função totiente. Acontece que essa lambda(n)é a ordem multiplicativa de 10 (mod n) (Glaisher 1878, Lehmer 1941). O número de dígitos na parte repetida da expansão decimal de um número racional também pode ser encontrado diretamente na ordem multiplicativa de seu denominador.

Minha teoria dos números está um pouco enferrujada no momento, então o melhor que posso fazer é levá-lo nessa direção.

Daniel B
fonte
8

Deixe n < d, e você está tentando descobrir a parte que se repete n/d. Let pSer o número de dígitos na parte de repetição: então n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). A parte entre colchetes é uma série geométrica, igual a 1/(10^p - 1).

Então n / d = R / (10^p - 1). Reorganize para obter R = n * (10^p - 1) / d. Para encontrar R, faça um loop pde 1 ao infinito e pare assim que ele se ddividir uniformemente n * (10^p - 1).

Aqui está uma implementação em 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

( kcontrola o comprimento da sequência repetida, para que você possa distinguir entre 1/9 e 1/99, por exemplo)

Observe que essa implementação (ironicamente) faz um loop para sempre se a expansão decimal for finita, mas termina se for infinita! Você pode verificar esse caso, porém, porque n/dsó terá uma representação decimal finita se todos os fatores primos dque não são 2 ou 5 também estiverem presentes n.

valtron
fonte
11
Esta resposta parece correta. O método é baseado na seguinte "regra": 0.123123... = 123/999 0.714258714258... = 714258/999999 (=5/7)etc.
VEM EM
4
Ele falha em casos como 1/6 ou 5/12: \
razpeitia 11/11/13
11
@razpeitia Eu fiz algo parecido, mas trabalhando em todos os casos (incluindo divisão inteira). Confira: codepad.org/hKboFPd2
Tigran Saluev
Eu fiz uma implementação javascript semelhante ao @ TigranSaluev de pelo github.com/Macil/cycle-division
macil
2

Divisão longa? : /

Transforme o resultado em uma sequência e aplique esse algoritmo a ela. Use BigDecimal se sua sequência não for longa o suficiente com tipos comuns.

Robert Harvey
fonte
4
"Transformar em uma sequência" pode exigir cálculos de precisão arbitrários e uma sequência muito longa para calcular duas cópias da parte repetida da sequência (e como você sabe quando parar de calcular? .121212312121231212123 ... seria um problema)
Sparr
@Sparr A duração da repetição é sempre menor que o denominador.
@ MichaelT Eu não estava ciente disso. Se verdadeira, a precisão não é precisamente "arbitrária", mas pode ser arbitrariamente alta, dependendo do denominador.
Sparr 28/03/2013
Eu não acho que o algoritmo ao qual você vincula funcionaria sem modificação. Inclui repetições que se sobrepõem e pesquisa por toda a cadeia (não apenas por correspondências consecutivas). Por exemplo, a substring repetida mais longa na "banana" é "ana".
Web_Designer 2/17/17