Comparando dois produtos de listas de números inteiros?

10

Suponha que eu tenha duas listas de números inteiros positivos de manitude limitada e que eu pegue o produto de todos os elementos de cada lista. Qual é a melhor maneira de determinar qual produto é maior?

É claro que posso simplesmente calcular cada produto, mas espero que exista uma abordagem mais eficiente, pois o número de dígitos nos produtos aumentará linearmente com o número de termos, para que todo o cálculo seja quadrático.

Se eu estivesse adicionando em vez de multiplicar, poderia usar uma "estratégia de zíper" para adicionar incrementalmente entradas da primeira lista e subtrair da segunda, contornando a necessidade de calcular as somas globais (grandes). As técnicas análogas aos produtos seriam somar os logaritmos das entradas, mas o problema agora é que a computação dos logs requer o uso de aritmética inexata. A menos que haja alguma maneira de provar que o erro numérico é irrelevante?

user168715
fonte
Se conhecermos o valor inteiro máximo e que é independente de n (ou seja, uma constante k), podemos fazer uma tabela de pesquisa dos fatores de todos os números de 1 a k. Agora, acho que se você escrever tudo na base [produto dos fatores], isso se tornará linear, pois você poderá calcular os produtos em tempo linear com essa base e comparar cada dígito (começando com o dígito de ordem mais alto) até que um seja maior que o outro. Os detalhes são um pouco complicados, mas acho que deve funcionar se k for uma constante.
Phylliida 29/05
Eu prefiro dizer que a técnica análoga para os produtos é manter um número racional igual ao primeiro elementos da primeira lista divididos por os primeiros elementos da segunda (além de manuseio s). Mas isso não é realmente útil, porque se todos os números forem coprime, ele calculará os dois produtos. | Também não tenho certeza de que o algoritmo ingênuo seja quadrático. A computação de um produto de n números inteiros de tamanho m pode levar até C ( m , m ) + C ( m , 2 m ) + . . . + C ( m , ( n0nm , onde C ( x , y ) é o custo da multiplicação de um x -bits inteiros com um y -bits integers.Unless você considerar que os produtos também se encaixam no formatoC(m,m)+C(m,2m)+...+C(m,(n1)m)C(x,y)xy
xavierm02
11
Pode haver alguma maneira de estender o método em math.stackexchange.com/a/1081989/10385
xavierm02
Uma melhoria na abordagem ingênua: conte o número de ocorrências de cada fator (em tempo linear) e calcule apenas o produto no final, usando um algoritmo de alimentação eficiente. Isso funciona no tempo , que é O ( nO(M(n)) usando o atual método assintoticamente mais rápido. O(nlogn2O(logn))
Emil Jeřábek
2
Vou pensar na precisão necessária para os logs. Pode ser realmente mais eficiente.
Emil Jeřábek

Respostas:

6

(Entendo a descrição do problema para que os números de entrada sejam delimitados por uma constante, para não rastrear a dependência do limite.)

O problema é solucionável no tempo linear e no espaço logarítmico usando somas de logaritmos. Mais detalhadamente, o algoritmo é o seguinte:

  1. Usando contadores binários, conte os números de ocorrências de cada número de entrada possível nas duas listas.

Isso leva tempo e os contadores usam o espaço O ( log n ) , pois cada contador é delimitado por n em valor.O(n)O(logn)n

p1,,pkO(1)aaO(logn)

  1. β1,,βkO(logn)Λ:=i=1kβilogpi

  2. β1==βk=0

Λ0

|Λ|>2Clogn
CΛ
  1. i=1kβiπiπilogpim:=Clogn+k+1

M(m)mM(m)=O(mlogm2O(logm))O(m2)logpimO(M(m)logm)iβiπiO(M(m))O(M(m)logm)O(lognpoly(loglogn))

O(n)

Emil Jeřábek
fonte
Obrigado! Vou ter que trabalhar com os detalhes mais tarde, mas isso parece muito promissor!
User168715