An Algorithm for Converting a Base-10 Number to a Base-N Number

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

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

Does an algorithm exist that converts a (base 10) number to into another number for any base in constant time?

You could separate the problem in smaller concerns by writing a function that returns the sum of digits in a given base and another one that returns a number expressed in a given base (base 2 to 36 in my example below):

def digitSum(N,b=10):
    return N if N<b else N%b+digitSum(N//b,b)

digits = "0123456789abcdefghijklmnopqrstuvwxyz"
def asBase(N,b):
    return "" if N==0 else asBase(N//b,b)+digits[N%b]

def lowestBase(N,a,b):
    return asBase(N, min(range(a,b+1),key=lambda c:digitSum(N,c)) )

output:

print(lowestBase(216,2,7))
1000     # base 6

print(lowestBase(216,2,5))
11011000 # base 2

Note that both digitSum and asBase could be written as iterative instead of recursive if you're manipulating numbers that are greater than base^1000 and don't want to deal with recursion depth limits

Here's a procedural version of digitSum (to avoid recursion limits):

def digitSum(N,b=10):
    result = 0
    while N:
        result += N%b
        N //=b
    return result

and returning only the base (not the encoded number):

def lowestBase(N,a,b):
    return min(range(a,b+1),key=lambda c:digitSum(N,c))

# in which case you don't need the asBase() function at all.

With those changes results for a range of bases from 2 to 1000 are returned in less than 60 milliseconds:

lowestBase(10**250+1,2,1000)  --> 10 in 57 ms

lowestBase(10**1000-1,2,1000) --> 3 in 47 ms

I don't know how large is "very large" but it is still sub-second for millions of bases (yet for a relatively smaller number):

lowestBase(10**10-1,2,1000000) --> 99999 in 0.47 second

lowestBase(10**25-7,2,1000000) --> 2 in 0.85 second

[EDIT] optimization

By providing a maximum sum to the digitSum() function, you can make it stop counting as soon as it goes beyond that maximum. This will allow the lowestBase() function to obtain potential improvements more efficiently based on its current best (minimal sum so far). Going through the bases backwards also gives a better chance of hitting small digit sums faster (thus leveraging the maxSum parameter of digitSum()):

def digitSum(N,b=10,maxSum=None):
    result = 0
    while N:
        result += N%b
        if maxSum and result>=maxSum:break
        N //= b
    return result

def lowestBase(N,a,b):
    minBase = a
    minSum  = digitSum(N,a)
    for base in range(b,a,-1):
        if N%base >= minSum: continue # last digit already too large
        baseSum = digitSum(N,base,minSum)
        if baseSum < minSum:
            minBase,minSum = base,baseSum
            if minSum == 1: break
    return minBase

This should yield a significant performance improvement in most cases.

How to convert a decimal base (10) to a negabinary base (-2)?

The algorithm is described in http://en.wikipedia.org/wiki/Negative_base#Calculation. Basically, you just pick the remainder as the positive base case and make sure the remainder is nonnegative and minimal.

 7 = -3*-2 + 1  (least significant digit)
-3 =  2*-2 + 1
 2 = -1*-2 + 0
-1 =  1*-2 + 1
 1 =  0*-2 + 1  (most significant digit)

Is there a way to convert a base 2^64 number to its base10 value in string form or display it in standard out in C or C++ without using big num libs?

Repeatedly "mod 10" the array to find the next least significant decimal digit, then "divide by 10". Repeat as needed.

Avoid unsigned long to encode 64-bit values as it may be only 32-bit.

---

If code can encode the number not using the widest type and use uin32_t, then doing the repeated "mod 10" of the array is not so hard.

Below illustrative code still needs to reverse the string - something left for OP. Potential other warts too - hence the advantage of using big number libraries for this sort of thing.

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

// Form reverse decimal string
void convert(char dec[], size_t n, uint32_t b32[]) {
  // TBD code to handle 0

  while (n > 0 && b32[0] == 0) {
    b32++;
    n--;
  }
  while (n > 0) {
    unsigned char rem = 0;
    // Divide by 10.
    for (size_t i = 0; i < n; i++) {
      uint64_t sum = rem * (1ULL << 32) + b32[i];
      b32[i] = (uint32_t) (sum / 10u);
      rem = (unsigned char) (sum % 10u);
    }
    *dec++ = (char) (rem + '0');
    if (b32[0] == 0) {
      b32++;
      n--;
    }
  }
  *dec = 0;
}

Sample

int main() {
  // unsigned long big_num[3] = [77478, 656713, 872];
  uint32_t big_num[6] = {0, 77478, 0, 656713, 0, 872};
  size_t n = sizeof big_num / sizeof big_num[0];
  char s[sizeof big_num * 10 + 1];
  convert(s, n, big_num);
  printf("<%s>\n", s);
  // <84078575285567457445592348207400342279346362>
  //  26364397224300470284329554475476558257587048
}

---

Related Topics