una por pasar otra numero hexadecimal convertir convertidor conversion como cambiar algoritmo algorithm math data-structures numbers number-systems

algorithm - por - convertir de una base a otra



Algoritmos basados en sistemas de base numérica? (16)

"Los números ternarios se pueden usar para transmitir estructuras similares a uno, como un triángulo de Sierpinski o un conjunto de Cantor convenientemente". source

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

"El sistema numérico cuáquero-imaginario fue propuesto por primera vez por Donald Knuth en 1955, en una sumisió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 su base. para representar cada número complejo usando solo los dígitos 0, 1, 2 y 3. " source

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

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

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

etc ...

Esta lista es un buen punto de partida.

Recientemente noté que existen muchos algoritmos basados ​​en parte o en su totalidad en los usos inteligentes de los números en las 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 lexicográficamente ordenadas se basan en el sistema numérico factoraldic.
  • Se puede pensar en los intentos como árboles que miran un dígito de la cuerda a la vez, para una base apropiada.
  • Los árboles de codificación de Huffman están diseñados para tener cada borde en el árbol que codifica un cero o uno en alguna representación binaria.
  • La codificación de Fibonacci se usa en la búsqueda de Fibonacci y para invertir ciertos tipos de logaritmos.

Mi pregunta es: ¿qué otros algoritmos hay por ahí que usan un sistema numérico inteligente como paso clave de su intuición o prueba? . Estoy pensando en armar una charla sobre el tema, para que cuantos más ejemplos saque, mejor.

Chris Okasaki tiene un capítulo muy bueno en su libro Estructuras de Datos Puramente Funcionales que discute las "Representaciones Numéricas": esencialmente, toma alguna representación de un número y conviértelo en una estructura de datos. Para dar un sabor, aquí están las secciones de ese capítulo:

  1. Sistemas de número posicional
  2. Números binarios (listas binarias de acceso aleatorio, representaciones sin cero, representaciones flojas, representaciones segmentadas)
  3. Gráficos 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 dispersas de números (por lo general, se ve esto en matrices o gráficos, ¡pero también se aplica 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 use una representación sin cero, recuperar el encabezado de la estructura de datos puede ser eficiente.
  • Evite los préstamos en cascada (de tomar la cola de la lista) y lleva (de consing en la lista) mediante la segmentación de la estructura de datos

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

  • Guibas, McCreight, Plass y Roberts: una nueva representación de 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 a través de ralentización recursiva.

En Hackers Delight (un libro que todo programador debe saber a 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 agrada el cálculo de 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 más práctico técnicamente).

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

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

He creado una enumeración metabase de n-tuple framework si estás interesado en conocerla. Es un azúcar sintáctico muy dulce para los sistemas de numeración de bases. No ha sido lanzado todavía. Enviar mi nombre de usuario por correo electrónico (en gmail).

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

Las cadenas hash (por ejemplo, en el algoritmo 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 yb es una base elegida que es lo suficientemente grande). Por ejemplo, la cadena "ABCD" puede ser hash como:

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

Sustituyendo valores ASCII por caracteres y tomando b como 256, 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 en módulo de un número razonablemente pequeño para mantener el resultado lo suficientemente pequeño.

Leí tu pregunta el otro día y hoy tuve un problema: ¿cómo puedo generar todas las particiones de un conjunto? La solución que se me ocurrió y que utilicé (quizás debido a la lectura de su pregunta) fue esta:

Para un conjunto con (n) elementos, donde necesito (p) particiones, cuente a través de todos (n) 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 está limpio. Está completo, no causa redundancia y utiliza bases arbitrarias. La base que usa depende del problema de particionamiento específico.

No es exactamente un sistema base inteligente, sino un uso inteligente del sistema base: las secuencias de Van der Corput son secuencias de baja discrepancia formadas al invertir la representación en base-n de los números. Se usan para construir las secuencias Halton 2-d que se ven así.

Puede ser AKS es el caso.

Recientemente me encontré con un algoritmo genial para generar subconjuntos en orden lexicográfico basado en las representaciones binarias de los números entre 0 y 2 n - 1. Utiliza los bits de los números para determinar qué elementos se deben elegir para el conjunto y reordenar localmente los conjuntos generados para ponerlos en orden lexicográfico. Si eres curioso, tengo un escrito publicado here .

Además, muchos algoritmos se basan en la escala (como una versión débilmente polinómica 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.

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

El sistema base doble es un sistema redundante que usa 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 maneras.

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

Tratando de dar la mejor breve visión general que puedo.

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

Supoosing N es compuesto G(N,A) = G(J,A) * G(K, A^J) , si aplicamos para 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 algunas mejores en el segundo, por lo que es una buena idea elegir las mejores de las que dependen de N Pero esto requeriría una operación de módulo rápida para ambos, 2 y 3. Aquí viene la razón por la que entra la doble base: básicamente, puedes hacer la operación de módulo rápidamente para ambos, dándote 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

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

Uno de mis favoritos que usa la 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.

Aquí hay una buena publicación sobre el uso de números ternarios para resolver el problema de la "moneda falsificada" (donde tienes que detectar una sola moneda falsificada en una bolsa de monedas regulares, usando un saldo las veces que sea posible)