I know that this can a silly question. But I can not find the answer.
When converting number bases (from decimal to any other number bases), we divide the decimal number by that base, and write down the remainder. Now, to find the converted number, we write the remainders in reverse order. Why do we do that? I mean why it does not work when we write in normal order?
[Math] Converting from decimal to any number base.
educationnumber-systems
Related Solutions
Remember the meaning of base 10 notation; when you write a number as $$d_nd_{n-1}\cdots d_2d_1d_0$$ where $d_i$ is the $i$th digit (from right to left), what you are saying is that the number is equal to: $$ d_0\times 10^0 + d_1\times 10^1 + d_2\times 10^2 + \cdots + d_n\times 10^n.$$ So, for example, $5381$ represents the number $$1\times 10^0 + 8\times 10^1 + 3\times 10^2 + 5\times 10^3 = 1 + 80 + 300 + 5000.$$
Writing a number in binary (base 2) is meant to represent the number in exactly the same way, but with powers of $2$ in stead of powers of 10: the expression $$e_k\cdots e_3e_2e_1e_0{}_{[2]}$$ represents the number $$n=e_0\times 2^0 + e_1\times 2^1 + e_2\times 2^2 + e_3\times 2^3 + \cdots + e_k\times 2^k.$$
Since every summand except the first one is a multiple of $2$, we can write: $$\begin{align*} n&=e_0\times 2^0 + e_1\times 2^1 + \cdots + e_k\times 2^k\\ &=e_0 + \left(e_1\times 2\right) + \left(e_2\times 4\right) + \cdots \left(e_k\times 2^{k}\right)\\ &= e_0 + \left( 2 \times e_1\right) + \left( 2\times (e_2\times 2)\right) + \cdots + \left(2\times(e_k\times 2^{k-1})\right)\\ &= e_0 + 2\Bigl(e_1 + (e_2\times 2) + \cdots + (e_k\times 2^{k-1})\Bigr). \end{align*}$$ That means that when you divide $n$ by $2$ you get a remainder of $e_0$ (the right-most digit of the base 2 expression of $n$), and a quotient of $$q_1=e_1\times 2^0 + e_2\times 2^1 + \cdots + e_k\times 2^{k-1}.$$ Now you can determine the next binary digit of $n$ by repeating the process with $q_1$: we write $$q_1 = e_1 + 2\Bigl(e_2 + e_3\times 2 + \cdots + e_k\times 2^{k-2}\Bigr),$$ so the remainder of dividing $q_1$ by $2$ is the penultimate digit of the binary expression of $n$, and the quotient is $q_3$, with $$q_3 = e_2 + e_3\times 2 + \cdots + e_k\times 2^{k-2}.$$
Lather, rinse, and repeat until the remainder quotient is $0$.
An unfortunate truth about converting a number from base $a$ to base $b$ is that unless there are integers $m > 0$ and $n > 0$ such that $a^m = b^n$, you need to use an arbitrarily large amount of memory in order to convert arbitrarily large numbers from base $a$ to base $b$ -- not necessarily all the digits all the time, but a lot of the digits a lot of the time. When $a^m = b^n$ (such as the conversion between $a=2^8$ and $b=2^5,$ which was mentioned in the question, where $a^5 = b^8$), you are able to "chunk" the input string of digits into groups of $m$ digits that can be converted into groups of $n$ digits, one group at a time with no kind of "carry" or interaction between the groups other than simply concatenating the digits to the output, exactly as described in the question; but that is a special case.
Suppose there are no such numbers $m$ and $n$. There are various ways this can happen, classified by the prime factorizations of $a$ and $b$:
- At least one of the bases $a$ or $b$ has a prime factor the other does not have, for example base $8 = 2^3$ and base $10 = 2\cdot5$.
- The bases $a$ and $b$ have the same prime factors, but not in the same ratio of powers, for example base $10 = 2\cdot5$ and base $20 = 2^2\cdot5$, or base $60 = 2^2\cdot3\cdot5$ and base $90 = 2\cdot3^2\cdot5$.
Note that in the case where $a$ and $b$ are both powers of the same prime, there is always a way to read and convert one block of digits at a time, provided that you either start with the least significant digit or you know how many digits each number contains.
In the case where $b$ has a prime factor that $a$ does not have, there is no power of $a$ that will ever be divisible by $b$, so if we take an arbitrarily large $m$, we can make $a^m$ have as many significant digits in base $b$ as we want. So when converting an arbitrarily large number from base $a$ to base $b$, there is no limit on the size of the block of digits of the output that could be affected by whether some high-place-value digit of input happens to be $0$ or $1$. Conversely, when converting from base $b$ to base $a$, there is no limit on the size of the block of digits of the input that we would have to examine in order to know for sure what the value of some high-place-value digit of the output is. So both conversion directions take unbounded memory if one base has a factor the other does not have.
In the case where the two bases have the same prime factors, but the powers of the prime factors are not in the same ratio, for any large-enough integer $m$, $a^m$ will be divisible by $b^n$ for some integer $n > 0$. But the quotient $a^m/b^n$will always contain some number of "uncancelled" prime factors, and we can show that the number of these factors grows without bound as $m$ grows arbitrarily large.
At this point I want to introduce some mathematical notation: for $p$ a prime, $\nu_p(x)$ is the number of factors of $p$ in a prime factorization of $x$; for example, $\nu_2(60) = 2$ because $60 = 2^2\cdot3\cdot5$.
Now for each prime factor $p$ of $a$ and $b$, evaluate $\nu_p(a)/\nu_p(b)$; let $q$ be the prime factor of $a$ and $b$ that minimizes this ratio, $r$ the prime factor that maximizes it. Then $\nu_q(a^{\nu_q(b)}) = \nu_q(b^{\nu_q(a)})$; in fact, $a^{\nu_q(b)}$ is divisible by $b^{\nu_q(a)}$, because for every other prime factor $p$, $\nu_p(a^{\nu_q(b)}) \geq \nu_p(b^{\nu_q(a)})$. But the quotient $a^{\nu_q(b)}/b^{\nu_q(a)}$ is not divisible by $b$; it has at least one prime factor of $r$ and no prime factor $q$. That is, $a^{\nu_q(b)}$ has at least one "uncancelled" factor of $r$ when we take the greatest power of $b$ that divides $a^{\nu_q(b)}$.
If we next consider $a^{2\nu_q(b)}$, the highest power of $b$ that divides it is $b^{2\nu_q(a)}$, and after that division there are at least two "uncancelled" factors of $r$. In general, $a^{k\nu_q(b)}$ has at least $k$ "uncancelled" factors of $r$; to write $a^{k\nu_q(b)}$ in base $b$, we would have to write some multiple of $r^k$ not divisible by $b$ followed by some zeros. This base-$b$ numeral could have as many significant digits as we want, depending on how large $k$ is. So once again, an arbitrarily large number of digits of the base-$b$ output can depend on the value of a single high-place-value digit of the base-$a$ input, and there is no bound on how much memory we might require to convert an arbitrarily large number.
The conversions where we can convert blocks of digits one at a time in bounded memory are just the ones where the two bases have exactly the same prime factors, and the powers of those prime factors are in the same proportions. This implies both bases are powers of the same integer. For example, every three digits in base $36 = 2^2\cdot3^2 = 6^2$ can be converted to two digits of base $216 = 2^3\cdot3^3 = 6^3$.
Note that base-85 encoding of a string of (for example) $1024$ binary digits does not produce a number written in base $85$. Instead, it produces something like a mixed-radix number, but with more complex rules for "carryover" than more well-known mixed-radix systems (such as the time of day) typically have. Reading from right to left, the place values of a base-85 encoding of a $1024$-bit integer would be $1$, $85$, $85^2$, $85^3$, $85^4$, $2^{32}$, $85\cdot2^{32}$, $85^2\cdot2^{32}$, $85^3\cdot2^{32}$, $85^4\cdot2^{32}$, $2^{64}$, $85\cdot2^{64}$, and so forth. You might say that the so-called "base-85" encoding really encodes a string of bits as a base-$2^{32}$ numeral, except that rather than define a sequence of $2^{32}$ unique glyphs for the digits $0$ to $2^{32}-1$, we write each base-$2^{32}$ digit as a five-digit base-$85$ integer in that range, left-padded with zeros as needed.
By the way, for a conversion from base $a$ to base $b$ where the bases are not powers of the same integer and therefore there is no simple $n$-digit-to-$m$-digit conversion, it is still not ever necessary to use a division algorithm. You just have to work out how to multiple a base-$b$ number by $a$ in base $b$. For example, $723_{10}$ to base $16$:
First represent base $a=10$ in base $b=16$. In base $16$, the number $10_{10}$ is written $\mathrm a_{16}$.
Take the leftmost digit, $7.$ The intermediate result is $7_{16}.$
Multiply by $\mathrm a_{16}$. Result: $7_{16} \times \mathrm a_{16} = 46_{16}.$
Add the next digit from the input, $2.$ Result: $48_{16}.$
Multiply by $\mathrm a_{16}$. Result: $40_{16} \times\mathrm a_{16} + 8_{16} \times\mathrm a_{16} = 280_{16} + 50_{16} = 2\mathrm{d}0_{16}.$
Add the next digit from the input, $3.$ Result: $2\mathrm{d}3_{16}.$
Since that is the last digit of input, the final result is $2\mathrm{d}3_{16}.$
When base $b$ is smaller than base $a,$ the individual digits of the base-$a$ number will sometimes come out to multiple digits in base $b,$ but the idea is the same; just add them to the intermediate results.
Best Answer
One thing that we must be very clear about: if you have a certain number, it is the same number no matter what base you write it in. If you have $x$ and divide it by $b$ using integer arithmetic only, with integer quotient $q$ and remainder $r$, you will have the same four numbers no matter whether $x$, $b$, $q$, and $r$ are written in base ten, in base two, or in base seven.
Now you are probably aware that if you write a number in decimal notation and you want to divide it by ten, you can simply remove the rightmost digit of the number, and what is left is the quotient; whereas the original rightmost digit (the one that is removed) is the remainder.
This trick works in other bases as well, as long as you divide by the same number that forms the base of your numeric representation. Take the base-eight number $346215_{\text{eight}}$, for example; if we perform integer division of this number by eight, the quotient is $34621_{\text{eight}}$ and the remainder is $5$.
But the remainder of $x$ divided by $b$ is simply a property of those numbers, regardless of the base in which they might happen to be written.
In other words, given any number $x$, the rightmost digit of $x$ (written in base $b$) is the remainder $r$ that you get when you divide $x$ by $b$ using integers only. For example, suppose we start with the number $x = 117901_{\text{ten}}$ (written in base ten), and we divide by $8$, using integers only. The quotient is $q = 14737_{\text{ten}}$ and the remainder is $r = 5$. Therefore, even if we had written $x$ originally in base eight instead, after dividing by eight the remainder would still be $r = 5$.
Further, because of the method explained above for division by eight of a number written in base eight, the last digit of $x$ in base eight is also the remainder after division by eight, that is, the last digit is $5$.
And that is why we always obtain the last digit of the number by taking the remainder after division. It's because that's how division by $b$ works in base $b$.