Qual é o algoritmo mais eficiente para calcular o LCM de um intervalo de números?

9

Eu olhei em volta e encontrei outras perguntas que tinham respostas, mas nenhuma delas abordava o escopo dessa questão em particular, incluindo esta questão , e também este .

Eu tenho que calcular o LCM de grandes intervalos de números de uma maneira eficiente. Eu não olhei muito a fundo para essas outras perguntas porque elas não lidam com intervalos de números tão grandes quanto os que esse algoritmo deve processar.

O código que eu tenho agora pode calcular o LCM de cada número entre 1 e 350000 em aproximadamente 90 segundos. (O número resultante tem cerca de 76000 dígitos decimais). Espero, eventualmente, ser capaz de escalá-lo em intervalos que são milhões ou talvez até bilhões de elementos.

Provavelmente será paralelizado eventualmente. Com alguns algoritmos isso não será nada difícil, para outros será mais complicado (se, por exemplo, o algoritmo usar o LCM atualmente gerado para calcular a primalidade de outras partes de sua computação)

Aqui está:

public static BigInteger getLCMOfRange(BigInteger lower, BigInteger upper)
{
    BigInteger M = BigInteger.ONE;
    BigInteger t;

    // long l = System.currentTimeMillis();
    // System.out.println("Calculating LCM of numbers up to " + upper + "...");
    for (; lower.compareTo(upper) != 1; lower = lower.add(BigInteger.ONE))
    {
        t = M.gcd(lower);
        if (t.compareTo(lower) == 0)
            continue;
        M = M.multiply(lower).divide(t);
    }
    // System.out.println("Done.  Took " + (System.currentTimeMillis() - l) + " milliseconds.  LCM is " + M.bitCount()+ " bits long.");
    return M;
}

Observe que, diferentemente de um loop típico, essa função opera sobre [lower, upper] em vez de [lower, upper]. Esse comportamento é intencional.

Um pouco de matemática de apoio é que o LCM de alguns conjuntos de números produto do conjunto de fatores primos a partir do qual qualquer um dos números pode ser produzido sem exigir qualquer parte externa do conjunto. Se meu intervalo for [1,20], posso representar isso da seguinte maneira:

1: 1         6:  3*2      11: 11       16: 2^4
2: 2         7:  7        12: 3*2^2    17: 17
3: 3         8:  2^3      13: 13       18: 3^2*2
4: 2^2       9:  3^2      14: 7*2      19: 19
5: 5         10: 5*2      15: 5*3      20: 5*2^2

LCM{[1,20]}: 2^4*3^2*5*7*11*13*17*19 = 232792560

Existe alguma maneira mais eficiente de calcular um LCM em um intervalo tão grande?

Eu não me importo se o algoritmo que alguém sugere é muito pesado em memória, o desempenho em tempo é muito mais importante (e também mais caro) do que o desempenho da memória neste caso.

Esta não é uma questão de lição de casa.

Pergunta

Qual é a maneira mais eficiente de calcular o MMC de um grande número de números? Esse algoritmo precisa operar em intervalos proibitivos de números amplos e, portanto, deve ser cuidadosamente otimizado.

Adendo 1

Uma questão intimamente relacionada é: Qual é a maneira mais eficiente de calcular o logaritmo de um BigInteger (base outro BigInteger)? O valor resultante pode ser truncado para o inteiro mais próximo.

    
por Wug 15.08.2012 в 23:26
fonte

2 respostas

3

Este é o layout do algoritmo. Eu suponho que você sempre começa a partir de 1:

  1. Encontre números primos no intervalo. Você pode usar a peneira de Eratóstenes por 350000. Para um número maior de números, você precisará de peneira segmentada .

  2. Para cada número primo p, use a função logarítmica para encontrar o maior expoente e que p e esteja dentro do intervalo. Multiplique p e para o LCM. (Os detalhes da otimização dependem da sua implementação)

Por que isso está correto?

  • Para números no formato p e em que p é primo, e e > = 1, devido ao passo 2, foi incluído no LCM, portanto p e | LCM.
  • Outros números terão o formato N = p 1 e 1 p 2 e < sub> 2 ... p n e n (onde p i são números de primos distintos emparelhados e e i > = 1), que é maior ou igual a p i e i (para todos i de 1 an). Desde p i e i | LCM, devido ao argumento anterior, N | LCM.
por nhahtdh 16.08.2012 / 00:04
fonte
2

Esta é uma generalização da resposta de @nhahtdh

Primeiro passo, encontre todos os primos que são menores ou iguais ao limite superior.

Depois, pegue cada primo p e anote ambos os limites inferior e superior em uma notação base p. O dígito mais alto que é diferente nos dois números é o expoente de p que você precisa incluir no seu LCM. Se o limite inferior for 1, isso é trivialmente o mesmo que a outra resposta.

Observe que a complexidade desse algoritmo não depende do tamanho do intervalo, apenas da magnitude do limite superior.

    
por biziclop 16.08.2012 / 01:03
fonte