Comparer deux produits de listes d'entiers?

Supposons que j'ai deux listes d'entiers positifs de manitude bornée et que je prenne le produit de tous les éléments de chaque liste. Quelle est la meilleure façon de déterminer quel produit est plus grand?

Bien sûr, je peux simplement calculer chaque produit, mais j'espère qu'il existe une approche plus efficace, car le nombre de chiffres dans les produits augmentera linéairement avec le nombre de termes, de sorte que l'ensemble du calcul est quadratique.

Si j'ajoutais au lieu de multiplier, je pourrais utiliser une "stratégie de fermeture éclair" consistant à ajouter progressivement des entrées de la première liste et à soustraire de la seconde, en contournant la nécessité de calculer les (grandes) sommes globales. Les techniques analogues pour les produits seraient de résumer les logarithmes des entrées, mais le problème est maintenant que le calcul des journaux nécessite l'utilisation d'une arithmétique inexacte. À moins qu'il n'y ait un moyen de prouver que l'erreur numérique n'est pas pertinente?

time-complexity nt.number-theory user168715
la source

Si nous connaissons la valeur entière maximale et qui est indépendante de n (c'est-à-dire une constante k), nous pouvons alors faire une table de correspondance des facteurs de tous les nombres de 1 à k. Maintenant, je pense que si vous écrivez tout dans la base [produit des facteurs], cela devient linéaire puisque vous pouvez calculer les produits en temps linéaire avec cette base, puis comparer chaque chiffre (en commençant par le chiffre le plus élevé) tour à tour jusqu'à ce que l'un soit supérieur à l'autre. Les détails y sont un peu délicats mais je pense que cela devrait fonctionner si k est une constante.

Phylliida

Je dirais plutôt que la technique analogue pour les produits est de garder un nombre rationnel égal aux premiers éléments de la première liste divisé par les premiers éléments de la seconde (plus la manipulation de

s). Mais ce n'est pas vraiment utile car si tous les nombres sont coprimes, il calculera les deux produits. | De plus, je ne suis pas sûr que l'algorithme naïf soit quadratique. Le calcul d'un produit de

nombres entiers de taille

peut prendre jusqu'à

0

$0$

n

$n$

m

$m$

où

est le coût demultiplicationun

des nombres entiers de avec

-bits integers.Unless vous considérez que les produits correspondent également au format

C (m, m) + C (m, 2 m) + . . . + C (m, (n - 1) m)

$C(m,m)+C(m,2m)+...+C(m,(n-1)m)$

C (x, y)

$C(x,y)$

x

$x$

y

$y$

xavierm02

Il peut y avoir un moyen d'étendre la méthode à math.stackexchange.com/a/1081989/10385

xavierm02

Une amélioration de l'approche naïve: compter le nombre d'occurrences de chaque facteur (en temps linéaire), et ne calculer le produit qu'à la fin, en utilisant un algorithme de mise sous tension efficace. Cela fonctionne dans le temps

, qui est

O (M (n))

$O(M(n))$

utilisant la méthode asymptotiquement la plus rapide actuelle.

O (n \log n 2^{O (\log^{*} n)})

$O(n\,\log n\,2^{O(\log^*n)})$

Emil Jeřábek

Je vais réfléchir à la précision nécessaire pour les journaux. Cela peut en fait être plus efficace.

Emil Jeřábek

(Je comprends la description du problème afin que les nombres en entrée soient limités par une constante, donc je ne suivrai pas la dépendance à la limite.)

Le problème peut être résolu dans le temps linéaire et l'espace logarithmique en utilisant des sommes de logarithmes. Plus en détail, l'algorithme est le suivant:

À l'aide de compteurs binaires, comptez le nombre d'occurrences de chaque numéro d'entrée possible dans les deux listes.

Cela prend du temps et les compteurs utilisent l'espace , car chaque compteur est limité par en valeur. $O(n)$ $O(\log n)$ $n$

Soit les nombres premiers sous la limite . En distribuant chaque compteur d'un nombre aux facteurs premiers de (avec la multiplicité appropriée), et en soustrayant les nombres pour une liste de l'autre liste, nous obtenons ce qui suit dans le temps : $p_1,\dots,p_k$ $O(1)$ $a$ $a$ $O(\log n)$

Calculez les entiers avec bits de sorte que le problème équivaut à déterminer le signe de . $\beta_1,\dots,\beta_k$ $O(\log n)$ $\Lambda:=\sum_{i=1}^k\beta_i\log p_i$

Si , répondez que les produits sont égaux. $\beta_1=\dots=\beta_k=0$

Sinon . Par le théorème de Baker , nous pouvons réduire la borne pour une certaine constante . Ainsi, ce qui suit calcule correctement le signe de : $\Lambda\ne0$

| Λ | > 2^{- C \log n}

$|\Lambda|>2^{-C\log n}$

C

$C$

Λ

$\Lambda$

Afficher le signe de , où est une approximation de à bits de précision. $\sum_{i=1}^k\beta_i\pi_i$ $\pi_i$ $\log p_i$ $m:=C\log n+k+1$

$M(m)$ $m$ $M(m)=O(m\,\log m\,2^{O(\log^* m)})$ $O(m^2)$ $\log p_i$ $m$ $O(M(m)\log m)$ $\sum_i\beta_i\pi_i$ $O(M(m))$ $O(M(m)\log m)\subseteq O(\log n\,\mathrm{poly}(\log\log n))$

$O(n)$

Emil Jeřábek
la source

Merci! Je devrai travailler sur les détails plus tard, mais cela semble très prometteur!

user168715

Comparer deux produits de listes d'entiers?

Réponses: