Algorytm przekształcania numeru base-10 na numer bazowy N

Question

Szukam sposobu na przekonwertowanie liczby base-10 na liczbę podstawową N, gdzie N może być duże. W szczególności szukam konwersji na base-85 iz powrotem. Czy ktoś zna prosty algorytm do przeprowadzenia konwersji? Najlepiej byłoby podać coś takiego:

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

Wszelkie pomysły są mile widziane!

Roja

Answer 1

To był rodzaj interesującej kwestii, więc poszedłem trochę za burtę:

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 

Działa to dla dowolnych podstawach. Działa tylko dla liczb całkowitych, chociaż nie ma powodu, dla którego nie mógłby być rozszerzony na pracę z dowolną liczbą. Ponadto ignoruje znak liczby. Ponownie, nie ma powodu, dla którego musi to robić, ale głównie nie chciałem wymyślać konwencji o zwrocie znaku w wartości zwracanej.

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 

ja również rozszerzyć metodę to_s tak, że działa z baz większych niż 36. Jeśli chcesz korzystać z bazy większa niż 36, trzeba przejść w obiekcie odwzorowania, która odwzorowuje „cyfry” na smyczki . (Cóż, w rzeczywistości wszystko, co jest wymagane, to dostarczenie obiektu, który odpowiada na [] i zwraca coś, co odpowiada na to_s. Tak więc łańcuch jest idealny, ale np. Działa również tablica liczb całkowitych.)

To także akceptuje opcjonalny separator, który służy do oddzielania cyfr.

Na przykład, umożliwia formatowanie adres IPv4, traktując je jako a-bazowej 256 numer i za pomocą tożsamości dla umiejscowienia i '.' jako separator:

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

oto (niekompletny) testsuite :

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

pseudokod tego jest dość proste. Oparcie 85 z liczb całkowitych bez znaku:

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

oraz oparcie 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

Wystarczy ogólny algorytm pseudokod:

1. zainicjować pustą listę
2. podjęcia aktualny numer mod bazę, zapisz wynik na początku listy
3. podziel bieżącą liczbę według bazy i podaj ją (inte Podział ger robi to doskonale)
4. jeśli wynik jest jeszcze większa od zera, należy powtórzyć na # 2

Answer 4

83992/85 = 988, reminder 12 

988 /85 = 11, reminder 53 

11 /85 = 0, reminder 11 

napisać przypomnienia w odwrotnej kolejności: 11, 53, 12, aby uzyskać numer base-85.

ją odzyskać:

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

Answer 5

Fixnum#to_s nie pomoże, jak to idzie tylko do base 36.

Jestem zaskoczony, że idziesz do bazy 85. Czy możesz wyjaśnić, jak działają radix?

Answer 6

Najprostszy algorytm, który mogę myśleć to (w pseudo-kod):

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

bazowa 85 jest szczególnie przydatny do kodowania ASCII danych binarnych, które jak mniemam jest to, co używasz go do . (Jeśli jednak powinieneś zapytać siebie, czy naprawdę warto dodatkowych kłopotów i czy Base 64 nie będzie wystarczająco dobry.)

Jeśli używasz tego jako schemat kodowania, twoja praca będzie konwertować liczby całkowite (4 bajty) na grupy po 5 liczb podstawowych. (Sposób radzenia sobie z rzeczami, które nie są wielokrotnościami 4 bajtów, zależy tylko od Ciebie - zwykle koniec jest wypełniony zerami.) Zobacz stronę Wikipedii na Base 85, aby uzyskać szczegółowe informacje.)

Podstawowy algorytm jest dość prosty: weź pozostała część podziału 85 przy pakowaniu do bazy 85, a następnie dzielić i powtarzać, aż skończysz. Aby wrócić, wielokrotnie dodawaj wartość i mnoż ją przez 85, aż skończysz.Nie jestem nieludzko zaznajomieni z Ruby, więc kod tutaj jest C/C++/Javaish styl, który mam nadzieję, że można interpretować:

// 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]; 
} 

to bez obawy o przepełnienie, bez martwienia się o dodanie 33 dostać się do Zakres ASCII i bez obawy o konwencję, że zero jest kodowane jako z, a nie !!!!! itd.

Answer 8

bo czuję rekurencji jest niedostatecznie reprezentowane w odpowiedziach mogę podać następujące brulion

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