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 , y donde y , podemos encontrar una estructura de datos / algoritmo que puede realizar sumas, multiplicaciones y se compara con \ entre e en tiempo yespacio?
fuente
Respuestas:
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
fuente