¿Qué tan cerca podemos llegar a multiplicar, sumar y comparar lineal (en enteros)?

21

Según el artículo de KW Regan "Connect the Stars" , menciona al final que todavía es un problema abierto encontrar una representación de enteros de tal manera que las operaciones de suma, multiplicación y comparación sean computables en tiempo lineal:

¿Existe una representación de enteros para que la suma, la multiplicación y la comparación sean factibles en tiempo lineal? Básicamente, ¿hay un anillo lineal ordenado discretamente?

(1) ¿Qué tan cerca podemos llegar a la multiplicación y suma lineal del tiempo, sin comparaciones? Aquí supongo que los tamaños del problema pueden variar, por lo que es posible que necesitemos una estructura de datos / algoritmo que permita cambiar los tamaños de los enteros.

(2) Para el problema completo, podemos suponer que encontraremos un esquema óptimo para multiplicar, sumar y comparar en los enteros. ¿Qué tan cerca podemos llegar la más lenta de estas tres operaciones (en el peor de los casos) hacia el tiempo lineal? Y en esa nota, ¿qué tan rápido serían las otras operaciones?

DECLARACIÓN DE PROBLEMA FORMAL

Como Emil Jeřábek menciona, nos gustaría descartar casos triviales y concentrarnos en el peor de los casos para esta pregunta.

Así que nos preguntamos, para los enteros no negativos x , y donde y , podemos encontrar una estructura de datos / algoritmo que puede realizar sumas, multiplicaciones y se compara con \ entre e eny0x<n0y<nxy tiempo yespacio?O(nlog(n))O(log2(n))

Matt Groff
fuente
1
Mencionaré que es posible crear un esquema que realice estas operaciones en el tiempo en enteros no negativos, donde n es el tamaño de bits del entero más grande (suponiendo que sepamos n antes de tiempo). Me pregunto si podemos hacerlo mejor, y hacerlo a tiempo proporcional al número entero actual que se está calculando. Θ(n)nn
Matt Groff el
55
@TysonWilliams: ¡Sí! ¡Binario!
Jeffε
2
En lugar de obtener tiempo lineal para todas estas operaciones, ¿hay una representación de enteros para que todas estas operaciones tengan tiempo ? O(nlogn)
Emil Jeřábek apoya a Monica el
44
En realidad, hay una respuesta positiva trivial: representar enteros en binario con bits de relleno. ¿No debería la declaración incluir alguna condición en el sentido de que la representación debería tener una longitud lineal en la longitud de la representación binaria? norte2
Emil Jeřábek apoya a Monica el
55
@ EmilJeřábek: Supongo que quiere que la representación de cualquier número entero use f ( n ) bits, para alguna función f ( n ) = Θ ( log n ) . norteF(norte)F(norte)=Θ(Iniciar sesiónnorte)
Jeff el

Respuestas:

14

Probablemente no sea la mejor respuesta, pero quizás este sea un punto de partida útil. Si deseamos representar un número entero no negativo, podemos almacenarlo como un conjunto de números primos secuenciales modulares de residuos a partir de 2. En esta forma, la comparación es potencialmente difícil, pero la multiplicación y la suma se pueden hacer con bastante rapidez. El producto de los primeros primos se aproxima por p n # = exp ( ( 1 + o ( 1 ) ) n log n ) . Por lo tanto, para representar un entero N, se requieren módulos de los primeros n primos, dondenorte

pagsnorte# #=Exp((1+o(1))norteIniciar sesiónnorte).
nortenorte . Como podemos representar cualquier N < p n # usando el módulo de residuos los primeros n residuos primos, podemos tomar n log n log ( N ) . La suma y la multiplicación se pueden hacer directamente entre pares de residuos. Hay n de estos pares, con el primo máximo alrededor de n log ( n ) . Por lo tanto, la adición debe estar ennorte<Exp((1+o(1))norteIniciar sesiónnorte)norte<pagsnorte# #nortenorteIniciar sesiónnorteIniciar sesión(norte)nortenorteIniciar sesión(norte) , mientras que la multiplicación a través de Schonhage-Strassen debe estar en O ( n log log ( N ) log log log log ( N ) log log log ( N ) ) . Como n log n log N , entonces una aproximación aproximada da n en O ( log N / log log N )O(norteIniciar sesiónIniciar sesión(norte))O(norteIniciar sesiónIniciar sesión(norte)Iniciar sesiónIniciar sesiónIniciar sesiónIniciar sesión(norte)Iniciar sesiónIniciar sesiónIniciar sesión(norte))norteIniciar sesiónnorteIniciar sesiónnortenorteO(Iniciar sesiónnorte/ /Iniciar sesiónIniciar sesiónnorte). Esto daría la complejidad de la suma y la multiplicación como aproximadamente y O ( log N log log log N log log log log N ) .O(Iniciar sesiónnorte)O(Iniciar sesiónnorteIniciar sesiónIniciar sesiónIniciar sesiónnorteIniciar sesiónIniciar sesiónIniciar sesiónIniciar sesiónnorte)
Joe Fitzsimons
fuente
1
véase también el teorema del resto chino
vzn
1
@vzn: Sí, iba a mencionar eso para las comparaciones, pero luego se me ocurrió que podría haber una operación de comparación más rápida a través de una representación mixta de radix.
Joe Fitzsimons