Converting Large Decimal Numbers to Octal and Binary

Question

I have large numbers that I need to convert to Octal and Binary systems. Examples of numbers that I am working with are $10^{10}$, $10^{20}$, $10^{30}$ ... (powers of 10) and numbers that are multiplied by $10^n$ for example $123.175*10^{31}$ and so on. Is there an efficient way (NOT Successive division) to do such a task?

Answer 1

Once you have the octal representation of a number, it's easy to convert to binary, because each of the $8$ possible octal digits can be mapped to a string of $3$ binary digits. To convert the result of a calculation into the octal system, I instead suggest to convert the numbers before the calculation and calculate in the octal system. You will need some procedure to multiply (large) octal numbers, but you only need to convert small decimal numbers (like $123.175$ or $10$) to the octal system. To get the octal representation of $10^{31}$, convert $10$ to the octal system and note that $$10^{31} = 10^{1+2+4+8+16} = 10^{1}\cdot10^{2}\cdot10^{4}\cdot10^{8}\cdot10^{16}$$ Also: $$10^2 = 10 \cdot 10, \quad 10^4 = 10^2 \cdot 10^2, \quad 10^8 = 10^4 \cdot 10^4 \quad\text{and}\quad 10^{16} = 10^8 \cdot 10^8$$ Splitting the powers of $10$ this way, you can reduce the number of multiplications. Of course, you will need a method to calculate the binary representation of the exponent... :-)

Answer 2

It's not successive division that you have to do in this case, but successive multiplication, which is somewhat simpler. For example, to evaluate $123.175\times 10^{31}$ in binary, start with $123175$ and multiply it by $10$ $28$ times. Using a computer, so the answer will already be in binary :-)

You can make this faster if you want by multiplying by larger powers of $10$ at each step. The best power of $10$ to use depends on your machine architecture.

For numbers this small, this is the fastest solution. For much larger numbers, you will want to use Fast Fourier Transforms, but that is another chapter.