À quelle distance pouvons-nous arriver à multiplier, ajouter et comparer linéairement (sur des entiers)?

Selon l'article de KW Regan "Connect the Stars" , il mentionne à la fin qu'il est toujours difficile de trouver une représentation des nombres entiers de sorte que les opérations d'addition, de multiplication et de comparaison sont calculables en temps linéaire:

Existe-t-il une représentation d'entiers de sorte que l'addition, la multiplication et la comparaison sont toutes réalisables en temps linéaire? Fondamentalement, existe-t-il un anneau linéaire ordonné discrètement?

(1) Dans quelle mesure pouvons-nous nous rapprocher de la multiplication et de l'addition linéaires du temps, sans comparaison? Ici, je suppose que les tailles de problème peuvent varier, de sorte que nous pouvons avoir besoin d'une structure / algorithme de données qui permet de changer les tailles entières.

(2) Pour le problème complet, nous pouvons supposer que nous trouverons un schéma optimal pour multiplier, additionner et comparer sur les entiers. À quelle distance pouvons-nous obtenir le plus lent de ces trois opérations (dans le pire des cas) vers le temps linéaire? Et sur cette note, quelle serait la vitesse des autres opérations?

DÉCLARATION FORMELLE DU PROBLÈME

Comme Emil Jeřábek le mentionne, nous aimerions exclure les cas insignifiants et nous concentrer sur le pire des cas pour cette question.

Nous demandons donc, pour les entiers non négatifs et où et , pouvons-nous trouver une structure / algorithme de données qui peut effectuer l'addition, la multiplication et la comparaison avec \ entre et dans temps et espace? $\forall x$ $\forall y$ $0 \le x < n$ $0 \le y < n$ $x$ $y$ $O(n \log{(n)})$ $O(\log^2{(n)})$

ds.algorithms ds.data-structures worst-case Matt Groff
la source

Je mentionnerai qu'il est possible de créer un schéma qui effectue ces opérations dans le temps sur des entiers non négatifs, où est la taille du plus grand entier (en supposant que nous connaissons avance). Je me demande si nous pouvons faire mieux, et cela en temps proportionnel aux nombres entiers en cours de calcul.

Θ (n)

$\Theta(n)$

n

$n$

n

$n$

Matt Groff

@TysonWilliams: Oui! Binaire!

Jeffε

Au lieu d'obtenir un temps linéaire pour toutes ces opérations, y a-t-il une représentation d'entiers pour que toutes ces opérations aient le temps

O (n \log n)

$O(n\log n)$

Emil Jeřábek soutient Monica

En fait, il y a une réponse positive triviale: représenter des entiers en binaire avec

bits de remplissage. La déclaration ne devrait-elle pas inclure une condition selon laquelle la représentation devrait avoir une longueur linéaire dans la longueur de la représentation binaire?

n^{2}

$n^2$

Emil Jeřábek soutient Monica

@ EmilJeřábek: Je suppose qu'il veut que la représentation de tout entier

utilise

bits, pour une fonction

n

$n$

f (n)

$f(n)$

f (n) = Θ (\log n)

$f(n)=\Theta(\log n)$

Jeffε

Probablement pas la meilleure réponse, mais c'est peut-être un point de départ utile. Si nous souhaitons représenter un entier non négatif, nous pouvons le stocker comme un ensemble de résidus nombres premiers séquentiels modulo à partir de 2. Dans cette forme, la comparaison est potentiellement difficile, mais la multiplication et l'addition peuvent être effectuées assez rapidement. Le produit des premiers nombres premiers est approximé par Par conséquent, pour représenter un entier vous avez besoin de résidus modulo les premiers nombres premiers, où $n$

p_{n} # = \exp ((1 + o (1)) n Journal n) .

$p_n\# =\exp((1+\mathcal{o}(1) )n\log n).$

N

$N$

n

$n$

. Puisque nous pouvons représenter tout

utilisant les résidus modulo les

premiers résidus premiers, nous pouvons prendre

. L'addition et la multiplication peuvent se faire directement entre des paires de résidus. Il existe

telles paires, le nombre maximal maximal se situant autour de

. Ainsi, l'addition devrait

N < \exp ((1 + o (1)) n \log n)

$N<\exp((1+\mathcal{o}(1) )n\log n)$

N < p_{n} #

$N<p_n\#$

n

$n$

n \log n \propto \log (N)

$n \log n \propto \log(N)$

n

$n$

n \log (n)

$n\log(n)$

, tandis que la multiplication via Schonhage-Strassen doit être dans

. Puisque

, alors une approximation grossière donne

dans

O (n \log \log (N))

$O(n\log\log(N))$

O (n \log \log (N) \log \log \log \log (N) \log \log \log (N))

$O(n\log\log(N)\log\log\log\log(N)\log\log\log(N))$

n \log n \propto \log N

$n \log n \propto \log N$

n

$n$

O (\log N / \log \log N)

$O(\log N/\log\log N)$ . Cela donnerait la complexité de l'addition et de la multiplication comme approximativement

O (\log N)

$O(\log N)$

O (\log N \log \log \log N \log \log \log \log N)

$O(\log N \log\log\log N \log\log\log\log N)$

Joe Fitzsimons
la source

voir aussi le théorème du reste chinois

vzn

@vzn: Oui, j'allais le mentionner pour les comparaisons, mais il m'est alors venu à l'esprit qu'il pourrait y avoir une opération de comparaison plus rapide via une représentation mixte de radix.

Joe Fitzsimons

À quelle distance pouvons-nous arriver à multiplier, ajouter et comparer linéairement (sur des entiers)?

Réponses: