how to determine base of a number?

Question

Given a integer number and its reresentation in some arbitrary number system. The purpose is to find the base of the number system. For example, number is 10 and representation is 000010, then the base should be 10. Another example: number 21 representation is 0010101 then base is 2. One more example is: number is 6 and representation os 10100 then base is sqrt(2). Does anyone have any idea how to solve such problem?

Answer 1

An algorithm like this should find the base if it is an integer, and should at least narrow down the choices for a non-integer base:

• Let N be your integer and R be its representation in the mystery base.
• Find the largest digit in R and call it r.
  • You know that your base is at least r + 1.
• For base == (r+1, r+2, ...), let I represent R interpreted in base base
  • If I equals N, then base is your mystery base.
  • If I is less than N, try the next base.
  • If I is greater than N, then your base is somewhere between base - 1 and base.

It's a brute-force method, but it should work. You may also be able to speed it up a bit by incrementing base by more than one if I is significantly smaller than N.

Something else that might help speed things up, particularly in the case of a non-integer base: Remember that as several people have mentioned, a number in an arbitrary base can be expanded as a polynomial like

x = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base + a[0]

When evaluating potential bases, you don't need to convert the entire number. Start by converting only the largest term, a[n]*base^n. If this is larger than x, then you already know your base is too big. Otherwise, add one term at a time (moving from most-significant to least-significant). That way, you don't waste time computing terms after you know your base is wrong.

Also, there is another quick way to eliminate a potential base. Notice that you can re-arrange the above polynomial expression and get

(x - a[0]) = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base

or

(x - a[0]) = (a[n]*base^(n-1) + a[n-1]*base^(n-2) + ... + a[2]*base + a[1])*base

You know the values of x and a[0] (the "ones" digit, you can interpret it regardless of base). What this gives you the extra condition that (x - a[0]) must be evenly divisible by base (since all your a[] values are integers). If you calculate (x - a[0]) % base and get a non-zero result, then base cannot be the correct base.

Answer 2

For integers only, it's not that difficult (we can enumerate).

Let's look at 21 and its representation 10101.

1 * base^4 <= 21 < (1+1) * base^4

Let's generate the numbers for some bases:

base   low   high
2      16    32
3      81    162

More generally, we have N represented as ∑ a_i * baseⁱ. Considering I the maximum power for which a_I is non null we have:

a[I] * base^I <= N < (a[I] + 1) * base^I  # does not matter if not representable

# Isolate base term
N / (a[I] + 1) < base^I <= N / a[I]

# Ith root
Ithroot( N / (a[I] + 1) ) < base <= Ithroot( N / a[I] )

# Or as a range
base in ] Ithroot(N / (a[I] + 1)), Ithroot( N / a[I] ) ]

In the case of an integer base, or if you have a list of known possible bases, I doubt they'll be many possibilities, so we can just try them out.

Note that it may be faster to actually take the Ithroot of N / (a[I] + 1) and iterate from here instead of computing the second one (which should be close enough)... but I'd need math review on that gut feeling.

If you really don't have any idea (trying to find a floating base)... well it's a bit more difficult I guess, but you can always refine the inequality (including one or two more terms) following the same property.

Answer 3

Several of the other posts suggest that the solution might be found by finding the roots of the polynomial the number represents. These will, of course, generally work, though they will have a tendency to produce negative and complex bases as well as positive integers.

Another approach would be to cast this as an integer programming problem and solve using branch-and-bound.

But I suspect that the suggestion of guessing-and-testing will be quicker than any of the cleverer proposals.

Answer 4

I'm thinking you will need try and check different bases. To be efficient, your starting base could be max(digit) + 1 as you know it won't be less than that. If that's too small double until you exceed, and then use binary search to narrow it down. This way your algorithm should run in O(log n) for normal situations.

Answer 5

I do not think that an answer can be given for every case. And I actually have a reason to think so! =)

Given a number x, with representation a_6 a_5 a_4 a_3 a_2 a_1 in base b, finding the base means solving

a_6 b^5 + a_5 b^4 + a_4 b^3 + a_3 b^2 + a_2 b^1 + a_1 = x.

This cannot be done generally, as shown by Abel and Ruffini. You might be luckier with shorter numbers, but if more than four digits are involved, the formulas are increasingly ugly.

There are quite a lot good approximation algorithms, though. See here.

Answer 6

This should give you a starting point:

Create an equation from the number and representation, number 42 and represenation "0010203" becomes:

1 * base ^ 4 + 2 * base ^ 2 + 3 = 42

Now you solve the equation to get the value of base.

Answer 7

         ___
         \
number = /__ ( digit[i] * base ^ i )

You know number, you know all digit[i], you just have to find out base.

Whether solving this equation is simple or complex is left as an exercise.

Answer 8

Im not sure if this is efficiently solvable. I would just try to pick a random base, see if given the base the result is smaller, larger or equal to the number. In case its smaller, pick a larger base, in case its larger pick a smaller base, otherwise you have the correct base.