Binary String to Decimal String

Question

Good afternoon,

How would you go about converting to a decimal string a binary string with more characters than bits in a language's largest integer type? In other words, supposing that you have the string

111001101001110100100(...)1001001111011100100

and that you can't convert it to an integer first, how would you go about writing it in base 10?

Thank you very much.

Answer 1

Write your own arithmetic in base 10. Only addition is needed. Example implementation in Python:

from math import log, ceil

def add(a, b):
    """Add b to a in decimal representation."""
    carry = 0
    for i in range(len(b)):
        carry, a[i] = divmod(a[i] + b[i] + carry, 10)
    while carry:
        i += 1
        carry, a[i] = divmod(a[i] + carry, 10)

# an example string
s = bin(3 ** 120)[2:]

# reserve enough decimal digits
res = [0] * int(ceil(len(s) * log(2) / log(10)))

# convert
for c in s:
    add(res, res)
    if c == "1":
        add(res, [1])

#print output
print str.join("", map(str, reversed(res)))

This uses lists of intergers to represent numbers in base 10. The list items correspond to the digits of the base 10 number. The item at index 0 corresponds to the ones, the item at index 1 to the tens, and so on.

Answer 2

You can use an algorithm like:

// X is the input
while ( X != "0" )
  compute X' and R such that X = 10 * X' + R  (Euclidean division, see below)
  output R    // least significant decimal digit first
  X = X'

The Euclidean division of X by 10 is computed like this:

R = 0  // remainder in 0..9
X' = ""
for (b in bits of X)  // msb to lsb
  R = 2*R + b
  if R >= 10
    X' += "1"
    R -= 10
  else
    X' += "0"

Remove leading "0" from X'
The remainder is R in 0..9