haskell - suma - sustraccion de numeros enteros

¿Cómo se pueden representar los números naturales para ofrecer una suma de tiempo constante?

Question

La respuesta de Cirdec a una pregunta no relacionada en gran medida me hizo preguntarme cuál es la mejor forma de representar los números naturales con suma y resta constante, y probando cero.

Por qué la aritmética de Peano no es lo suficientemente buena:

Supongamos que usamos

data Nat = Z | S Nat

Entonces podemos escribir

Z + n = n
S m + n = S(m+n)

Podemos calcular m+n en O (1) tiempo colocando mr debits (para alguna constante r ), uno en cada constructor S añadido a n . Para obtener O (1) isZero , debemos asegurarnos de tener como máximo p debits por constructor S , para una p constante. Esto funciona muy bien si calculamos a + (b + (c+...)) , pero se desmorona si calculamos ((...+b)+c)+d . El problema es que los débitos se acumulan en la parte delantera.

Una opción

La salida más fácil es usar listas que puedan ser caneadas, como las que Okasaki describe, directamente. Hay dos problemas:

1. O (n) el espacio no es realmente ideal.

2. No está del todo claro (al menos para mí) que la complejidad de las colas bootstrapped sea necesaria cuando no nos importa ordenar de la misma forma que lo haríamos con las listas.

Answer 1

Por lo que yo sé, Idris (un lenguaje puramente funcional funcionalmente dependiente que está muy cerca de Haskell) trata esto de una manera bastante directa. El compilador conoce las Nat y Fin ( Nat límite superior) y las reemplaza con operaciones y tipos enteros de máquina siempre que sea posible, por lo que el código resultante es bastante efectivo. Sin embargo, eso no es cierto para los tipos personalizados (incluso los isomórficos) ni para la etapa de compilación (había algunos ejemplos de código que usaban Nat para la comprobación de tipos que daban como resultado un crecimiento exponencial en tiempo de compilación; puedo proporcionarlos si fuera necesario).

En el caso de Haskell, creo que se puede implementar una extensión de compilación similar. Otra posibilidad es crear macros TH que transformen el código. Por supuesto, ambas opciones no son fáciles.

Answer 2

Sabemos que hay dos soluciones "extremas" para la adición eficiente de números naturales:

1. Memoria eficiente, la representación binaria estándar de números naturales que usa la memoria O (log n) y requiere O (log n) tiempo para la suma. (Ver también el capítulo "Representaciones binarias" en el libro de Okasaki .)

2. CPU eficiente que usa solo O (1) tiempo. (Consulte el capítulo "Abstracción estructural" en el libro). Sin embargo, la solución usa memoria O (n) ya que representaríamos el número natural n como una lista de n copias de () .

   No he hecho los cálculos reales, pero creo que para la adición numérica de O (1) no necesitaremos toda la potencia de las colas FIFO de O (1) , sería suficiente para arrancar la lista estándar [] (LIFO) del mismo modo. Si estás interesado, podría tratar de explicar eso.

El problema con la solución eficiente de la CPU es que necesitamos agregar algo de redundancia a la representación de la memoria para que podamos ahorrar suficiente tiempo de CPU. En algunos casos, la adición de una redundancia de este tipo se puede lograr sin comprometer el tamaño de la memoria (como para la operación de incremento / decremento O (1) ). Y si permitimos formas de árbol arbitrarias, como en la solución eficiente de CPU con listas bootstrapped, simplemente hay demasiadas formas de árbol para distinguirlas en la memoria O (log n) .

Entonces, la pregunta es: ¿podemos encontrar la cantidad justa de redundancia para que la cantidad de memoria sub-lineal sea suficiente y con la que podamos lograr O (1) además? Creo que la respuesta es no :

Tengamos un algoritmo de representación + que tenga O (1) suma de tiempo. Tengamos entonces un número de la magnitud de m- bits, que calculamos como una suma de 2 ^ k números, cada uno de ellos de la magnitud de (mk) -bit. Para representar cada uno de esos sumandos necesitamos (independientemente de la representación) un mínimo de (mk) bits de memoria, por lo que al comienzo, comenzamos con (al menos) (mk) 2 ^ k bits de memoria. Ahora, en cada una de esas adiciones de 2 ^ k , podemos preformar una cantidad constante de operaciones, por lo que podemos procesar (e idealmente eliminar) un total de C 2 ^ k bits. Por lo tanto, al final, el límite inferior para el número de bits que necesitamos para representar el resultado es (mkC) 2 ^ k bits. Como k puede elegirse arbitrariamente, nuestro adversario puede establecer k = mC-1 , lo que significa que la suma total se representará con al menos 2 ^ (mC-1) = 2 ^ m / 2 ^ (C + 1) ∈ O ( 2 ^ m) bits. ¡Entonces un número natural n siempre necesitará O (n) bits de memoria!

Answer 3

Según tengo entendido, en la terminología básica de programación informática, el problema subyacente es que desea concatenar listas en tiempo constante. Las listas no tienen trucos como referencias avanzadas, por lo que no puede saltar al final en O (1) vez, por ejemplo.

Puede usar anillos en su lugar, que puede combinar en O (1) vez, independientemente de si se usa a+(b+(c+...)) o ((...+c)+b)+a lógica. Los nodos en los anillos no necesitan estar doblemente vinculados, solo un enlace al siguiente nodo.

La resta es la eliminación de cualquier nodo, O (1), y la prueba de cero (o uno) es trivial. Sin embargo, la prueba para n > 1 es O (n).

Si desea reducir el espacio, en cada operación puede fusionar los nodos en los puntos de inserción o eliminación y ponderar los restantes más arriba. Cuantas más operaciones hagas, más compacta será la representación. Creo que el peor de los casos seguirá siendo O (n), sin embargo.