Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I'm looking for an advanced algorithm to create a converter between different bases. The algorithm should be able to convert long numbers(for example with 10000 characters). So the most common algorithm is too inefficient ($O(n^2)$ time complexity).

Example:

Convert $111111111111111111000000000011111111111_2$ to base $10$

Convert $123456789123456789123456789123456789_{10}$ to base $26$

Also I'm curious if is possible to convert directly between unrelated bases. (not like this A->10 10->B (A,B, 10 represent base))

share|improve this question
Sure, the number 10 plays absolutely no special role so it can be avoided. The only special feature of the base 10 is that we've been trained to use it (and we have 10 fingers and superstring theory's spacetime has 10 dimensions). However, computers may avoid it. Any algorithm that converts from/to base 10 is easily generalized to any base so the intermediate base-10 result may be avoided. However, it may sometimes be useful to do these two steps - instead of using "many different" algorithms at the same moment. – Luboš Motl Jun 11 '11 at 12:13
1  
Actually for a computer it might be useful to have base 2 and not base 10 as the intermediate step. – trutheality Jun 11 '11 at 13:10
Also I'm curious if is possible to convert directly between unrelated bases ... if you can do arithmetic in that other base, go for it! – GEdgar Jun 11 '11 at 17:01
1  
Unless the bases are specially related (as powers of a common base), I don't see any reason to expect any serial algorithm faster (by more than a constant factor) than extracting "places" in the result by repeated integer divisions/residues on output. Note that your examples suggest only integer parts are considered; fractional parts (beyond the radix point) would entail additional complexity. – hardmath Jun 11 '11 at 17:12

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.