Я ищу способ преобразования числа base-10 в базовое число N, где N может быть большим. В частности, я смотрю на преобразование в base-85 и обратно. Кто-нибудь знает простой алгоритм для преобразования? В идеале это обеспечило бы что-то вроде:
to_radix(83992, 85) -> [11, 53, 12]
Любые идеи оценены!
Рой
Это был интересный вопрос, поэтому я немного переборщил:
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, обрабатывая его как номер базы 256 и используя идентификатор для отображения и '.' в качестве разделителя:
2_078_934_278.to_s(256, Array.new(256) {|i| i }, '.') # => '123.234.5.6'
Здесь (неполный) testuite:
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
Псевдокод для этого достаточно прост. Чтобы заложить 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
Просто общий алгоритм псевдокода:
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
Fixnum#to_s вам не поможет, поскольку он подходит только к base 36.
Я удивлен, что вы подходите к базе 85. Можете ли вы объяснить, как работают radixs?
Самый простой алгоритм, о котором я могу думать (в псевдокоде):
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
База 85 особенно полезна для кодирования ASCII двоичных данных, и я полагаю, это то, для чего вы ее используете. (Однако, если именно поэтому вы должны спросить себя, действительно ли это стоит лишних хлопот и будет ли Base 64 не будет достаточно.)
Если вы используете это как схему кодирования, ваша задача состоит в том, чтобы преобразовать целые числа (4 байта) в группы из 5 базовых чисел. (Как вы относитесь к вещам, которые не являются кратными 4 байтам, зависит от вас - обычно конец дополняется нулями. Подробности см. на странице Википедии на базе 85.)
Базовый алгоритм довольно прост: возьмите остаток на деление 85 при упаковке в базу 85, затем разделите и повторите, пока вы не закончите. Чтобы вернуться назад, повторно добавляйте значение и умножайте его на 85, пока не закончите. Я не очень хорошо знаком с Ruby, поэтому здесь код 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 not !!!!! и т.д.
потому что я чувствую, что рекурсия недопредставлена в ответах, я даю следующий черновик
def to_radix(int, radix)
int == 0 ? [] : (to_radix(int / radix, radix) + [int % radix])
end