¿Algoritmos basados ​​en sistemas de base numérica? [cerrado]

Recientemente me di cuenta de que existen muchos algoritmos basados ​​en parte o en su totalidad en usos inteligentes de números en bases creativas. Por ejemplo:

• Los montones binomiales se basan en números binarios, y los montones binomiales sesgados más complejos se basan en números binarios sesgados.
• Algunos algoritmos para generar permutaciones ordenadas lexicográficamente se basan en el sistema numérico factorádico.
• Los intentos se pueden considerar como árboles que miran un dígito de la cadena a la vez, para obtener una base adecuada.
• Los árboles de codificación de Huffman están diseñados para que cada borde del árbol codifique un cero o uno en alguna representación binaria.
• La codificación de Fibonacci se utiliza en la búsqueda de Fibonacci y para invertir ciertos tipos de logaritmos.

Mi pregunta es: ¿qué otros algoritmos existen que utilizan un sistema numérico inteligente como un paso clave de su intuición o prueba? . Estoy pensando en organizar una charla sobre el tema, así que cuantos más ejemplos tenga, mejor.

Chris Okasaki tiene un capítulo muy bueno en su libro Estructuras de datos puramente funcionales que analiza las "Representaciones numéricas": esencialmente, tome alguna representación de un número y conviértala en una estructura de datos. Para darle un toque, aquí están las secciones de ese capítulo:

1. Sistemas de números posicionales
2. Números binarios (listas binarias de acceso aleatorio, representaciones sin cero, representaciones perezosas, representaciones segmentadas)
3. Números binarios sesgados (Listas de acceso aleatorio binarias sesgadas, montones binomiales sesgados)
4. Números trinarios y cuaternarios

Algunos de los mejores trucos, destilados:

• Distinga entre representaciones densas y escasas de números (por lo general, esto se ve en matrices o gráficos, ¡pero también es aplicable a los números!)
• Los sistemas de números redundantes (sistemas que tienen más de una representación de un número) son útiles.
• Si organiza el primer dígito para que sea distinto de cero o utiliza una representación sin cero, recuperar el encabezado de la estructura de datos puede resultar eficaz.
• Evite tomar prestados en cascada (de tomar la cola de la lista) y llevar (de consumir a la lista) segmentando la estructura de datos

Aquí también está la lista de referencia para ese capítulo:

• Guibas, McCreight, Plass y Roberts: una nueva representación para listas lineales.
• Myers: una pila aplicativa de acceso aleatorio
• Carlsson, Munro, Poblete: Una cola binomial implícita con tiempo de inserción constante.
• Kaplan, Tarjan: listas puramente funcionales con catenation mediante ralentización recursiva.

"Los números ternarios se pueden usar para transmitir estructuras auto-similares como un triángulo de Sierpinski o un conjunto de Cantor convenientemente". fuente

"Los números cuaternarios se utilizan en la representación de curvas de Hilbert 2D". fuente

"El sistema numérico quater-imaginario fue propuesto por primera vez por Donald Knuth en 1955, en una presentación a una búsqueda de talentos científicos en la escuela secundaria. Es un sistema numérico posicional no estándar que utiliza el número imaginario 2i como base. para representar cada número complejo usando solo los dígitos 0, 1, 2 y 3. " fuente

"Los números romanos son un sistema biquinario". fuente

"Senary puede considerarse útil en el estudio de números primos, ya que todos los primos, cuando se expresan en base seis, distintos de 2 y 3 tienen 1 o 5 como dígito final". fuente

"Sexagesimal (base 60) es un sistema numérico con sesenta como base. Se originó con los antiguos sumerios en el tercer milenio antes de Cristo, se transmitió a los antiguos babilonios y todavía se utiliza, en una forma modificada, para medir tiempo, ángulos y las coordenadas geográficas que son ángulos ". fuente

etc ...

Esta lista es un buen punto de partida.

Leí su pregunta el otro día y hoy me enfrenté a un problema: ¿Cómo puedo generar todas las particiones de un conjunto? La solución que se me ocurrió y que utilicé (tal vez debido a leer su pregunta) fue esta:

Para un conjunto con (n) elementos, donde necesito (p) particiones, cuente todos los (n) números de dígitos en la base (p).

Cada número corresponde a una partición. Cada dígito corresponde a un elemento en el conjunto, y el valor del dígito le dice en qué partición colocar el elemento.

No es sorprendente, pero es genial. Está completo, no genera redundancia y utiliza bases arbitrarias. La base que utilice depende del problema de particionamiento específico.

Recientemente encontré un algoritmo genial para generar subconjuntos en orden lexicográfico basado en las representaciones binarias de los números entre 0 y 2 ⁿ - 1. Utiliza los bits de los números tanto para determinar qué elementos deben elegirse para el conjunto como para reordenar localmente los conjuntos generados para ponerlos en orden lexicográfico. Si tiene curiosidad, tengo un artículo publicado aquí .

Además, muchos algoritmos se basan en el escalado (como una versión de polinomio débil del algoritmo de flujo máximo de Ford-Fulkerson), que utiliza la representación binaria de los números en el problema de entrada para refinar progresivamente una aproximación aproximada en una solución completa.

No es exactamente un sistema de base inteligente, sino un uso inteligente del sistema de base: las secuencias de Van der Corput son secuencias de baja discrepancia formadas invirtiendo la representación de números en base n. Se utilizan para construir secuencias Halton bidimensionales que se parecen a esto .

Recuerdo vagamente algo sobre los sistemas de base doble para acelerar la multiplicación de matrices.

El sistema de base doble es un sistema redundante que utiliza dos bases para un número.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

Redundante significa que un número se puede especificar de muchas formas.

Puede buscar el artículo "Algoritmo híbrido para el cálculo del polinomio matricial" de Vassil Dimitrov, Todor Cooklev.

Tratando de dar la mejor descripción breve que pueda.

Intentaban calcular un polinomio matricial G(N,A) = I + A + ... + A^{N-1}.

Suponiendo que N es compuesto G(N,A) = G(J,A) * G(K, A^J), si aplicamos J = 2, obtenemos:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

además,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

Como es "obvio" (en broma) que algunas de estas ecuaciones son rápidas en el primer sistema y otras mejores en el segundo, es una buena idea elegir la mejor de las que dependen N. Pero esto requeriría una operación de módulo rápida para 2 y 3. Aquí está la razón por la que entra la base doble: básicamente puede hacer la operación de módulo rápidamente para ambos, lo que le brinda un sistema combinado:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

Mire el artículo para una mejor explicación, ya que no soy un experto en esta área.

RadixSort puede utilizar varias bases numéricas. http://en.wikipedia.org/wiki/Radix_sort Implementación bastante interesante de un bucketSort.

aquí hay una buena publicación sobre el uso de números ternarios para resolver el problema de las "monedas falsas" (donde debe detectar una sola moneda falsificada en una bolsa de monedas normales, usando un saldo el menor número de veces posible)

Las cadenas de hash (por ejemplo, en el algoritmo de Rabin-Karp ) a menudo evalúan la cadena como un número base-b que consta de n dígitos (donde n es la longitud de la cadena y b es una base elegida que es suficientemente grande). Por ejemplo, la cadena "ABCD" se puede codificar como:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

Sustituyendo los valores ASCII por caracteres y tomando b como 256, esto se convierte en,

65*256^3+66*256^2+67*256^1+68*256^0

Sin embargo, en la mayoría de las aplicaciones prácticas, el valor resultante se toma como módulo de un número de tamaño razonable para mantener el resultado lo suficientemente pequeño.

La exponenciación al elevar al cuadrado se basa en la representación binaria del exponente.

En Hackers Delight(un libro que todo programador debería saber en mis ojos) hay un capítulo completo sobre bases inusuales, como -2 como base (sí, bases negativas derechas) o -1 + i (i como unidad imaginaria sqrt (-1)) como base. También me gustó calcular cuál es la mejor base (en términos de diseño de hardware, para todos los que no quieran leerlo: la solución de la ecuación es e, así que puedes ir con 2 o 3, 3 sería un poco mejor (factor 1.056 veces mejor que 2) - pero es técnico más práctico).

Otras cosas que me vienen a la mente son el contador gris (usted cuando cuenta en este sistema solo cambios de 1 bit, a menudo usa esta propiedad en el diseño de hardware para reducir los problemas de metaestabilidad) o la generalización de la codificación de Huffmann ya mencionada: la codificación aritmética.

La criptografía hace un uso extensivo de anillos enteros (aritmáticos modulares) y también de campos finitos, cuyas operaciones se basan intuitivamente en el comportamiento de los polinomios con coeficientes enteros.

Realmente me gusta este para convertir números binarios en códigos Gray: http://www.matrixlab-examples.com/gray-code.html

Gran pregunta. La lista es muy larga. Decir la hora es una instancia simple de bases mixtas (días | horas | minutos | segundos | am / pm)

He creado un marco n-tuple de enumeración de metabase si está interesado en conocerlo. Es un azúcar sintáctico muy dulce para los sistemas de numeración de bases. Aún no se ha lanzado. Envía mi nombre de usuario por correo electrónico (en gmail).

Uno de mis favoritos con base 2 es la codificación aritmética . Es inusual porque el corazón del algoritmo usa representaciones de números entre 0 y 1 en binario.

Puede ser AKS es el caso.