¿Comparando dos productos de listas de enteros?

10

Supongamos que tengo dos listas de enteros positivos de la personalidad limitada, y tomo el producto de todos los elementos de cada lista. ¿Cuál es la mejor manera de determinar qué producto es más grande?

Por supuesto, simplemente puedo calcular cada producto, pero espero que haya un enfoque más eficiente, ya que el número de dígitos en los productos aumentará linealmente con el número de términos, de modo que todo el cálculo sea cuadrático.

Si estuviera agregando en lugar de multiplicar, podría usar una "estrategia de cierre" de agregar incrementalmente entradas de la primera lista y restar de la segunda, evitando la necesidad de calcular las sumas generales (grandes). Las técnicas análogas para productos serían sumar los logaritmos de las entradas, pero el problema ahora es que calcular los registros requiere el uso de aritmética inexacta. ¿A menos que haya alguna forma de demostrar que el error numérico es irrelevante?

usuario168715
fuente
Si conocemos el valor entero máximo y eso es independiente de n (es decir, una constante k), entonces podemos hacer una tabla de búsqueda de los factores de todos los números del 1 al k. Ahora creo que si escribe todo en base [producto de factores] se vuelve lineal ya que puede calcular los productos en tiempo lineal con esa base y luego comparar cada dígito (comenzando con el dígito de orden más alto) a su vez hasta que uno sea mayor que el otro. Los detalles son un poco complicados, pero creo que debería funcionar si k es una constante.
Phylliida
Prefiero decir que la técnica análoga para productos es mantener un número racional igual a los primeros elementos de la primera lista dividido por los primeros elementos de la segunda (más manejo de s). Pero eso no es realmente útil porque si todos los números son coprimos, calculará ambos productos. El | Además, no estoy seguro de que el algoritmo ingenuo sea cuadrático. Calcular un producto de n enteros de tamaño m puede tomar hasta C ( m , m ) + C ( m , 2 m ) + . . . + C ( m , ( n0 0nortemetro donde C ( x , y ) es el costo de multiplicar un númeroentero de x bits con un númeroentero de y bits. A menos que considere que los productos también se ajustan al formatoC(metro,metro)+C(metro,2metro)+...+C(metro,(norte-1)metro)C(X,y)Xy
xavierm02
1
Puede haber alguna forma de extender el método en math.stackexchange.com/a/1081989/10385
xavierm02
Una mejora en el enfoque ingenuo: cuente el número de ocurrencias de cada factor (en tiempo lineal), y solo calcule el producto al final, utilizando un algoritmo de alimentación eficiente. Esto funciona en el tiempo , que es O ( nO(METRO(norte)) utilizando el método asintóticamente más rápido actual. O(norteIniciar sesiónnorte2O(Iniciar sesiónnorte))
Emil Jeřábek
2
Pensaré en la precisión necesaria para los registros. En realidad, puede ser más eficiente.
Emil Jeřábek

Respuestas:

6

(Entiendo la descripción del problema para que los números de entrada estén delimitados por una constante, por lo que no rastrearé la dependencia del límite).

El problema se puede resolver en tiempo lineal y espacio logarítmico utilizando sumas de logaritmos. Con más detalle, el algoritmo es el siguiente:

  1. Usando contadores binarios, cuente el número de ocurrencias de cada posible número de entrada en ambas listas.

Esto lleva tiempo , y los contadores usan el espacio O ( log n ) , ya que cada contador está limitado por un valor n .O(norte)O(Iniciar sesiónnorte)norte

Supongamos que son los números primos debajo del límite O ( 1 ) . Mediante la distribución de cada contador para un número una a los factores primos de un (con multiplicidad apropiado), y restando los recuentos de una lista de la otra lista, se obtiene la siguiente en el tiempo O ( log n ) :pag1,...,pagkO(1)unaunaO(Iniciar sesiónnorte)

  1. Calcule los números enteros con O ( log n ) bits de manera que el problema sea equivalente a determinar el signo de Λ : = k i = 1 β i log p i .β1,...,βkO(Iniciar sesiónnorte)Λ: =yo=1kβyoIniciar sesiónpagyo

  2. Si , responda que los productos son iguales.β1==βk=0 0

De lo contrario . Según el teorema de Baker , podemos reducir el límite | Λ | > 2 - C log n para una constante determinada C . Por lo tanto, lo siguiente calcula correctamente el signo de Λ :Λ0 0

El |ΛEl |>2-CIniciar sesiónnorte
CΛ
  1. Emite el signo de , donde π i es una aproximación de log p i a m : = C log n + k + 1 bits de precisión.yo=1kβyoπyoπyoIniciar sesiónpagyometro: =CIniciar sesiónnorte+k+1

METRO(metro)metroMETRO(metro)=O(metroIniciar sesiónmetro2O(Iniciar sesiónmetro))O(metro2)Iniciar sesiónpagyometroO(METRO(metro)Iniciar sesiónmetro)yoβyoπyoO(METRO(metro))O(METRO(metro)Iniciar sesiónmetro)O(Iniciar sesiónnortepagoly(Iniciar sesiónIniciar sesiónnorte))

O(norte)

Emil Jeřábek
fuente
¡Gracias! Tendré que analizar los detalles más tarde, ¡pero esto parece muy prometedor!
user168715