An algorithm for converting a base-10 number to a base-N number.

Question

Guys,

I am looking for a way to convert a base-10 number into a base-N number where N can be large. Specifically i am looking at converting to base-85 and back again. Does anyone know a simple algorithm to perform the conversion? Ideally it would provide something like:

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

Any ideas are appreciated!

Roja

Answer 1

The pseudocode for this is fairly straightforward. To base 85 from unsigned integers:

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

And to 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 2

Just a general pseudocode algorithm:

1. initialize empty list
2. take current number mod base, store result at front of list
3. divide current number by base and floor it (integer division does this perfectly)
4. if result is still greater than zero, repeat at #2

Answer 3

83992 / 85 = 988, reminder 12

988   / 85 = 11,  reminder 53

11   /  85 = 0,   reminder 11

write the reminder in reverse order: 11, 53, 12 to get your base-85 number.

To get it back:

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

Answer 4

Fixnum#to_s won't help you, as it only goes up to base 36.

I'm surprised that you're going up to base 85. Can you explain how radixs work?

Answer 5

The simplest algorithm that I can think of is (in pseudo-code):

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 6

Base 85 is particularly useful for ASCII encoding of binary data, which I presume is what you're using it for. (However, if this is why you should ask yourself whether it's really worth the extra hassle and whether Base 64 won't be good enough.)

If you're using this as an encoding scheme, your job is going to be to convert integers (4 bytes) into groups of 5 base85 numbers. (How you deal with things that are not multiples of 4 bytes is up to you--usually the end is padded with zeros. See the Wikipedia page on Base 85 for details.)

The basic algorithm is quite simple: take the remainder on division of 85 when packing into base 85, then divide and repeat, until you're done. To go back again, repeatedly add the value and multiply by 85 until you're done. I'm not terribly familiar with Ruby, so the code here is a C/C++/Javaish style, which hopefully you can interpret:

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

This is without worrying about overflow, without worrying about adding 33 to get into ASCII range, and without worrying about the convention that zero is encoded as z not !!!!!, and so on.

Answer 7

That was kind of an interesting question, so I went a little overboard:

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

This works for arbitrary bases. It only works for integers, although there is no reason why it couldn't be extended to work with any arbitrary number. Also, it ignores the sign of the number. Again, there is no reason why it must do that, but mainly I didn't want to have to come up with a convention for returning the sign in the return value.

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

I also extended the to_s method so that it works with bases greater than 36. If you want to use a base greater than 36, you have to pass in a mapping object which maps the "digits" to strings. (Well, actually, all that is required is that you provide an object that responds to [] and returns something which responds to to_s. So, a string is perfect, but e.g. an array of integers also works.)

It also accepts an optional separator, which is used to separate the digits.

For example, this allows you to format an IPv4 address by treating it as a base-256 number and using the identity for the mapping and '.' as the separator:

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

Here's an (incomplete) 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, '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