Conversión de base numérica como operación de secuencia

Question

Hay una forma en el espacio de trabajo constante para realizar conversiones arbitrarias básicas y de tamaño arbitrario. Es decir, para convertir una secuencia de n números en el rango [1,m] a una secuencia de ceiling(n*log(m)/log(p)) números en el rango [1,p] usando un mapeo de 1-a-1 que (preferiblemente pero no necesariamente) preservadores lexigraphical orden y da resultados secuenciales?

Estoy particularmente interesado en soluciones que son viables como una función de tubería, e.i. son capaces de manejar un conjunto de datos más grande que el que se puede almacenar en la RAM.

He encontrado una serie de soluciones que requieren "espacio de trabajo" proporcional al tamaño de la entrada, pero ninguna que pueda escaparse con un "espacio de trabajo" constante.

---

¿Cae la diferencia secuencial? Es decir: permiten lexicográfico entradas secuenciales que dan lugar a las salidas no lexicográfico secuenciales:

F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3) 
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5) 

---

algunas reflexiones:

podría funcionar esto?

StreamBase _n -> convert (n, lcm(n,p)) -> convert (lcm(n,p), p) -> StreamBase _p

(donde lcm es mínimo común múltiplo)

Answer 1

No creo que sea posible en el caso general. Si m es una potencia de p (o viceversa), o si ambas son potencias de una base común, puede hacerlo, ya que cada grupo de registro _m (p) es entonces independiente. Sin embargo, en el caso general, supongamos que está convirtiendo el número a1a2a3...an. El número equivalente de la base de p es

sum(ai*mi-1 para i en 1..n)

Si hemos procesado los primeros i dígitos, entonces tenemos la suma parcial º i. Para calcular el i+1 'suma º parcial, tenemos que añadir ai+1* mi.En el caso general, este número va a tener dígitos que no sean cero en la mayoría de los lugares, así que tendremos que modificar todos los dígitos que hemos procesado hasta el momento. En otras palabras, tendremos que procesar todos de los dígitos de entrada antes de que sepamos cuáles serán los dígitos finales de salida.

En el caso especial donde m son los dos poderes de una base común, o lo que es equivalente, si registro _m (p) es un número racional, entonces mi sólo tendrá un par de dígitos distintos de cero en la base p cerca del frente, por lo que podemos producir con seguridad la mayoría de los dígitos que hemos calculado hasta ahora.

Answer 2

Creo que hay una forma de hacer la conversión de radix de manera orientada a flujo en orden lexicográfico. Sin embargo, lo que se me ocurrió no es suficiente para realmente hacerlo, y tiene un par de suposiciones:

1. La longitud de los números de posición ya se conoce.
2. Los números que se describen son enteros. No he considerado lo que sucede con los índices matemático y productivo.

Tenemos una secuencia de valores un de longitud p, en donde cada valor está en el rango [0, m -1]. Queremos una secuencia de valores b de longitud q en el rango [0, n -1]. Podemos calcular el k º dígitos de nuestra secuencia de salida b de un de la siguiente manera:

b _k = baja [suma (a _i * m ⁱ para i en 0 a p-1)/n ^k] n mod

le permite reorganizar que suma en dos partes, partiéndolo en un punto arbitrario z

b _k = piso [(suma (a _i * m ⁱ para i en z a p-1) + suma (a _i * m ⁱ para i en 0 para z-1))/n ^k] mod n

Supongamos que aún no conocemos los valores de a entre [0, z-1] y no podemos calcular el segundo término de suma. Nos quedamos con tener que lidiar con los rangos. Pero eso todavía nos da información sobre b _k.

El valor mínimo b _k puede haber es:

b _k> = piso [suma (a _i * m ⁱ para i en z a p-1)/n ^k] n mod

y el valor máximo b _k puede haber es:

b _k < = piso [(suma (a _i * m ⁱ para i en z a p-1) + m ^z - 1)/n ^k] mod n

debemos ser capaces de hacer un proceso como este:

1. iniciación del z sea p. Vamos a contar hacia atrás desde p ya que recibimos cada carácter de a.
2. Inicializar k en el índice del valor más significativo en b. Si mi cerebro aún está funcionando, ceil [log _n (m ^p)].
3. Lee un valor de a. Decremento z.
4. Calcule el valor mínimo y máximo para b _k.
5. Si el mínimo y el máximo son iguales, salida b _k, y disminución k. 4. Goto (Puede ser posible que ya tenemos suficientes valores para varios valores consecutivos de _{b k})
6. Si z! = 0, entonces esperamos más valores de una . Ir a 3.
7. Afortunadamente, en este punto hemos terminado.

no hemos considerado la forma de calcular de manera eficiente los valores de rango hasta ahora, pero estoy razonablemente seguro de que el cálculo de la suma de los caracteres entrantes de una se puede hacer mucho más razonable que almacenar todos los a. Sin embargo, sin hacer las matemáticas, ¡no haré ningún reclamo duro al respecto!

Answer 3

Sí, es posible

para cada carácter I (s) que se lee en, va a escribir caracteres O (s) basado en techo (Largo * log (A)/log (Out)) .

asignar suficiente espacio

Set x to 1 
Loop over digits from end to beginning # Horner's method 
    Set a to x * digit 
    Set t to O - 1 
    Loop while a > 0 and t >= 0 
     Set a to a + out digit 
     Set out digit at position t to a mod to base 
    Set a to a/to base 
Set x to x * from base 
Return converted digit(s) 

Así, por base 16 al 2 (lo cual es fácil), el uso de "192FE", leemos '1' y la convierten, a continuación, repetir el '9', luego '2 'y así sucesivamente dándonos' 0001 ',' 1001 ',' 0010 ',' 1111 'y' 1110 '. Tenga en cuenta que para las bases que no son potencias comunes, como la base 17 a la base 2 significaría leer 1 caracteres y escribir 5.