Un algoritmo para convertir un número de base 10 en un número de base-N

Question

Estoy buscando una manera de convertir un número de base 10 en un número de base N donde N puede ser grande. Específicamente estoy buscando convertir a base-85 y viceversa. ¿Alguien sabe un algoritmo simple para realizar la conversión? Lo ideal sería proporcionar algo como:

to_radix(83992, 85) -> [11, 53, 12] 

¡Se agradecen todas las ideas!

Roja

Answer 1

Eso era una especie de una pregunta interesante, así que fui un poco por la borda:

class Integer 
    def to_base(base=10) 
    return [0] if zero? 
    raise ArgumentError, 'base must be greater than zero' unless base > 0 
    num = abs 
    return [1] * num if base == 1 
    [].tap do |digits| 
     while num > 0 
     digits.unshift num % base 
     num /= base 
     end 
    end 
    end 
end 

Esto funciona para bases arbitrarias. Solo funciona para enteros, aunque no hay ninguna razón por la cual no se pueda extender para trabajar con cualquier número arbitrario. Además, ignora el signo del número. Una vez más, no hay ninguna razón por la cual debe hacer eso, pero principalmente no quería tener que presentar una convención para devolver el signo en el valor de retorno.

class Integer 
    old_to_s = instance_method(:to_s) 
    define_method :to_s do |base=10, mapping=nil, sep=''| 
    return old_to_s.bind(self).(base) unless mapping || base > 36 
    mapping ||= 'abcdefghijklmnopqrstuvwxyz' 
    return to_base(base).map {|digit| mapping[digit].to_s }.join(sep) 
    end 
end 

[Fixnum, Bignum].each do |klass| 
    old_to_s = klass.instance_method(:to_s) 
    klass.send :define_method, :to_s do |base=10, mapping=nil, sep=''| 
    return old_to_s.bind(self).(base) unless mapping || base > 36 
    return super(base, mapping, sep) if mapping 
    return super(base) 
    end 
end 

También extendieron el método to_s para que funcione con bases mayores de 36. Si desea utilizar una base mayor que 36, usted tiene que pasar en un objeto de asignación que asigna los "dígitos" para cuerdas . (Bueno, en realidad, todo lo que se requiere es que proporcione un objeto que responda al [] y devuelva algo que responda a to_s. Por lo tanto, una cadena es perfecta, pero también funciona una matriz de enteros)

También acepta un separador opcional, que se usa para separar los dígitos.

Por ejemplo, esto permite dar formato a una dirección IPv4 tratándola como base 256 el número y el uso de la identidad para el mapeo y '.' como separador:

2_078_934_278.to_s(256, Array.new(256) {|i| i }, '.') # => '123.234.5.6' 

He aquí un banco de pruebas (incompleto) :

require 'test/unit' 
class TestBaseConversion < Test::Unit::TestCase 
    def test_that_83992_in_base_85_is_11_53_12 
    assert_equal [11, 53, 12], 83992.to_base(85) 
    end 
    def test_that_83992_in_base_37_is_1_24_13_2 
    assert_equal [1, 24, 13, 2], 83992.to_base(37) 
    end 
    def test_that_84026_in_base_37_is_1_24_13_36 
    assert_equal [1, 24, 13, 36], 84026.to_base(37) 
    end 
    def test_that_0_in_any_base_is_0 
    100.times do |base| 
     assert_equal [0], 0.to_base(base) 
     assert_equal [0], 0.to_base(1 << base) 
     assert_equal [0], 0.to_base(base << base) 
    end 
    end 
    def test_that_84026_in_base_37_prints_1od_ 
    assert_equal '1od_', 84026.to_s(37, 'abcdefghijklmnopqrstuvwxyz_') 
    end 
    def test_that_ip_address_formatting_works 
    addr = 2_078_934_278 
    assert_equal '123.234.5.6', addr.to_s(256, (0..255).to_a, '.') 
    assert_equal '123.234.5.6', addr.to_s(256, Array.new(256) {|i| i}, '.') 
    end 
    def test_that_old_to_s_still_works 
    assert_equal '84026', 84026.to_s 
    assert_equal '1su2', 84026.to_s(36) 
    end 
end 

Answer 2

El pseudocódigo para esto es bastante sencillo. Para basar el 85 de enteros sin signo:

digits := ''; 
while (number > 0) 
    digit := number % 85 
    digits := base85Digit(digit) + digits 
    number /= 85 // integer division so the remainder is rounded off 
end while 

Y a la base 10:

mult := 1 
result := 0 
for each digit in digits // starting from the rightmost working left 
    result += base10(digit) * mult 
    mult *= 85 
end for 

Answer 3

Sólo un algoritmo de pseudocódigo en general:

1. inicializar lista vacía
2. toman de base mod número actual, almacenar resultado en el frente de la lista
3. dividir el número actual por base y plantarlo (inte división ger hace esto a la perfección)
4. si el resultado es aún mayor que cero, repetir en el # 2

Answer 4

83992/85 = 988, reminder 12 

988 /85 = 11, reminder 53 

11 /85 = 0, reminder 11 

escribir el recordatorio en el orden inverso: 11, 53, 12 para obtener su número de base-85.

Para recuperarlo:

11 * 85^2 + 53 * 85^1 + 12 * 85^0 = 83992 

Answer 5

Fixnum#to_s no le ayudará, ya que sólo llega hasta base 36.

Me sorprende que vayas a la base 85. ¿Puedes explicar cómo funcionan las radix?

Answer 6

El algoritmo más simple que puedo pensar es (en pseudo-código):

N = base-10 number 
1) N mod 85 = 1st number 
2) tempVal = floor(N/85) 
3) if(tempVal > 0 && tempVal < 85) then 
    tempVal= 2nd number 
else 
    2nd number = (tempVal mod 85), then goto step (2), replacing N with N1 

Answer 7

Base 85 es particularmente útil para la codificación ASCII de los datos binarios, que supongo que es lo que se está utilizando para . (Sin embargo, si es por eso que debe preguntarse si realmente vale la pena la molestia adicional y si Base 64 no será lo suficientemente bueno).

Si está utilizando esto como un esquema de codificación, su trabajo se va a debe convertir enteros (4 bytes) en grupos de 5 números base85. (La manera de tratar con cosas que no son múltiplos de 4 bytes depende de usted - por lo general al final se rellena con ceros Ver la página de Wikipedia sobre la base 85 para más detalles.).

El algoritmo básico es bastante simple: tomar el resto en la división de 85 cuando empaques en la base 85, luego divídelo y repite, hasta que termines. Para volver, agrega el valor repetidamente y multiplica por 85 hasta que termines.No estoy terriblemente familiar con Ruby, por lo que el código que aquí hay una/C++/estilo Javaish C, que se espera se puede interpretar:

// To base 85 
unsigned int n = // your number 
byte b85[5]; // What you want to fill 
for (int i=0 ; i<5 ; i++) { 
    b85[4-i] = (n%85); // Fill backwards to get most significant value at front 
    n = n/85; 
} 

// From base 85 
n = 0; 
for (int i=0 ; i< 5 ; i++) { 
    n = n*85 + b85[i]; 
} 

Ésta es sin preocuparse por desbordamiento, sin preocuparse por la adición de 33 para entrar en Rango ASCII, y sin preocuparse por la convención de que el cero está codificado como z, no !!!!!, y así sucesivamente.

Answer 8

porque siento recursividad es insuficientemente representados en las respuestas que dan la siguiente borrador

def to_radix(int, radix) 
    int == 0 ? [] : (to_radix(int/radix, radix) + [int % radix]) 
end