converting a decimal into binary in the most optimal way possible

Question

What is the most optimal way to convert a decimal number into its binary form ,i.e with the best time complexity?

Normally to convert a decimal number into binary,we keep on dividing the number by 2 and storing its remainders.But this would take really long time if the number in decimal form is very large.The time complexity in this case would turn out to be O(log n).

So i want to know if there is any approach other than this that can do my job with better time comlexity?

Prostatectomy

Define "very large". Chances are you've nothing to worry about. – Tied

O(log n) is very efficient. – Suave

Also define representations. Decimal is string of [0-9], BCD or int? Binary is string of [01], int array of ints? – Zuber

numbers as large as 10^18 – Prostatectomy

how about this: instead of divisions by 2, you would do an AND operation if the first bit is a 0 or 1 and then make a bitshift to the right, until you did it for all the bits? you could of course develop an algorithm to find the bit at the "highest" position to minimize the necessary repetitions. – Bluestocking

You can't do any better than O(log n). The output will be O(log n) bits long, and regardless of how you get them, you will at least have to output every bit. – Timberwork

10^18 fits in uint64_t, and most modern systems have hardware multiplier, so you don't need to worry about time unless you're doing like millions (or more) of conversions in the program's life time and it costs you so much time. Simply multiply the digits by 10 – Chare

The time complexity for this naive algorithm is more like O((log n)^2), since dividing by 2 is log n, and you need to do that log n times. – Kenakenaf

Answer 1

The problem is essentially that of evaluating a polynomial using binary integer arithmetic, so the result is in binary. Suppose

p(x) = a₀xⁿ + a₁xⁿ⁻¹ + ⋯ + aₙ₋₁x + aₙ

Now if a₀,a₁,a₂,⋯,aₙ are the decimal digits of the number (each implicitly represented by binary numbers in the range 0 through 9) and we evaluate p at x=10 (implicitly in binary) then the result is the binary number that the decimal digit sequence represents.

The best way to evaluate a polynomial at a single point given also the coefficients as input is Horner's Rule. This amounts to rewriting p(x) in a way easy to evaluate as follows.

p(x) = ((⋯((a₀x + a₁)x + a₂)x + ⋯ )x + aₙ₋₁)x + aₙ

This gives the following algorithm. Here the array a[] contains the digits of the decimal number, left to right, each represented as a small integer in the range 0 through 9. Pseudocode for an array indexed from 0:

    toNumber(a[])
        const x = 10
        total = a[0]
        for i = 1 to a.length - 1 do
            total *= x    //multiply the total by x=10
            total += a[i]  //add on the next digit
        return total

Running this code on a machine where numbers are represented in binary gives a binary result. Since that's what we have on this planet, this gives you what you want.

If you want to get the actual bits, now you can use efficient binary operations to get them from the binary number you have constructed, for example, mask and shift.

The complexity of this is linear in the number of digits, because arithmetic operations on machine integers are constant time, and it does two operations per digit (apart from the first). This is a tiny amount of work, so this is supremely fast.

If you need very large numbers, bigger that 64 bits, just use some kind of large integer. Implemented properly this will keep the cost of arithmetic down.

To avoid as much large integer arithmetic as possible if your large integer implementation needs it, break the array of digits into slices of 19 digits, with the leftmost slice potentially having fewer. 19 is the maximum number of digits that can be converted into an (unsigned) 64-bit integer.

Convert each block as above into binary without using large integers and make a new array of those 64-bit values in left to right order. These are now the coefficients of a polynomial to be evaluated at x=10¹⁹. The same algorithm as above can be used only with large integer arithmetic operations, with 10 replaced by 10¹⁹ which should be evaluated with large integer arithmetic in advance of its use.

Arachnid