Алгоритм преобразования числа base-10 в число base-N - PullRequest
10 голосов
/ 24 мая 2010

Я ищу способ преобразования числа base-10 в число base-N, где N может быть большим. В частности, я смотрю на преобразование в базу-85 и обратно. Кто-нибудь знает простой алгоритм для выполнения преобразования? В идеале это будет что-то вроде:

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

Любые идеи приветствуются!

Roja

Ответы [ 8 ]

20 голосов
/ 24 мая 2010

Это был довольно интересный вопрос, поэтому я немного переборщил:

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

Это работает для произвольных оснований.Он работает только для целых чисел, хотя нет никаких причин, почему он не может быть расширен для работы с любым произвольным числом.Кроме того, он игнорирует знак числа.Опять же, нет никаких причин, по которым должен делать это, но в основном я не хотел придумывать соглашение о возвращении знака в возвращаемом значении.

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 ||= '0123456789abcdefghijklmnopqrstuvwxyz'
    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

Я также расширил метод to_s, чтобы он работал с базами больше 36. Если вы хотите использовать базу больше 36, вы должны передать объект отображения, который отображает «цифры» в строки.(Ну, на самом деле, все, что требуется, это предоставить объект, который отвечает на [] и возвращает что-то, что отвечает на to_s. Итак, строка идеальна, но, например, массив целых чисел также работает.)

Он также принимает необязательный разделитель, который используется для разделения цифр.

Например, это позволяет форматировать адрес IPv4, обрабатывая его как число base-256 и используя идентификатор дляотображение и '.' в качестве разделителя:

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

Вот (неполный) набор тестов:

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, '0123456789abcdefghijklmnopqrstuvwxyz_')
  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
3 голосов
/ 24 мая 2010

Псевдокод для этого довольно прост. Для основания 85 из целых чисел без знака:

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

И к базе 10:

mult := 1
result := 0
for each digit in digits // starting from the rightmost working left
  result += base10(digit) * mult
  mult *= 85
end for
1 голос
/ 24 мая 2010

Просто общий алгоритм псевдокода:

  1. инициализация пустого списка
  2. принятие текущего номера модовой базы, сохранение результата перед списком
  3. деление текущего номера на базуи напишите это (целочисленное деление делает это отлично)
  4. , если результат все еще больше нуля, повторите в # 2
0 голосов
/ 08 августа 2013

потому что я чувствую, что рекурсия недостаточно представлена ​​в ответах, я даю следующий черновик

def to_radix(int, radix)
  int == 0 ? [] : (to_radix(int / radix, radix) + [int % radix])
end
0 голосов
/ 24 мая 2010

База 85 особенно полезна для ASCII-кодирования двоичных данных, и я полагаю, для чего вы ее используете.(Однако, если именно поэтому вы должны спросить себя, действительно ли это стоит дополнительных хлопот и не будет ли Base 64 достаточно хорошей.)

Если вы используете это как схему кодирования, ваша задачабудет преобразовывать целые числа (4 байта) в группы из 5 чисел base85.(То, как вы справляетесь с вещами, не кратными 4 байтам, зависит от вас - обычно конец заполнен нулями. Подробнее см. На странице Википедии на Base 85).

Основной алгоритм довольно прост: возьмите остаток от деления 85 при упаковке в основание 85, затем разделите и повторяйте, пока не закончите.Чтобы вернуться снова, несколько раз добавьте значение и умножьте на 85, пока не закончите.Я не очень хорошо знаком с Ruby, поэтому здесь приведен код в стиле C / C ++ / Javaish, который, надеюсь, вы сможете интерпретировать:

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

Это не беспокоясь о переполнении, не беспокоясь о добавлении 33 впопасть в диапазон ASCII, и, не беспокоясь о соглашении, ноль кодируется как z, а не !!!!! и т. д.

0 голосов
/ 24 мая 2010

Самый простой алгоритм, который я могу придумать, (в псевдокоде):

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
0 голосов
/ 24 мая 2010

Fixnum#to_s вам не поможет, так как он поднимается только до базы 36 .

Я удивлен, что вы идете на базу 85. Можете ли вы объяснитькак работает основание?

0 голосов
/ 24 мая 2010
83992 / 85 = 988, reminder 12

988   / 85 = 11,  reminder 53

11   /  85 = 0,   reminder 11

напишите напоминание в обратном порядке: 11, 53, 12, чтобы получить ваш номер базы-85.

Чтобы вернуть его:

11 * 85^2 + 53 * 85^1 + 12 * 85^0 = 83992
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...