![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Base conversion mysteries explained!!1!
When I was a kid, I learned -- probably in The Gentle Art of Mathematics or some such book -- how to convert numerals from one base to another. Divide n by newbase, record the remainder, replace n by the quotient, repeat until quotient = 0, then write the remainders in reverse order.
This manifestly worked, if you did it, but always felt backwards to me, doubly so -- once for the reverse order thing, and once for the fact that you're only using remainders, not quotients, or so it seemed. Plus, though it gave the right answer, I didn't have much sense of why it worked.
Well, I was thinking about it early this morning in lieu of sleeping again, as I do, and came up with a method[1] that's slow but does both use quotients and yield the digits in MSB (most significant 'bit' first, descending significance). And then I thought about the old remainder method again, and it made more sense[2], and I also realized a key mismatch: the whole cycle of dividing by newbase calls up long division, may even involve long division if newbase is multiple digits in oldbase, and long division gives its answer in MSB. The remainder method chews up the number LSB, and gives the newbase numeral's digits LSB, so it's not backwards at all by its own lights, but it is LSB instead of MSB. Works fine if you write the units first and work to the left.
[1] Trial and error: multiply by increasing powers of newbase until the quotient is zero; backoff to the preceding power, and the resulting quotient is the first digit (MSB) of your answer. Repeat for the remainder. So (base 10 to base 10, for simplicity), n=742: find that 742//1000 = 0, 742//100 = 7, so 7, then repeat for 42. A subtlety is that numeral-based long division may not work, e.g. if you're converting a binary numeral to base ten and dividing by '1010': binary quotients are only 0 or 1. You'd have to go back to basics, division as "how many times can I subtract b from a?"
[2] 10 to 10 again: n=742, divide by 10 and get 2, that's your units; now shift right (or use the quotient) to get 74, divide by 10, get 4, which is your tens digit, and so on. Thinking about the relation between dividing by 2, and shifting the binary representation of a number to the right, made it all clear.
Dunno if I'm making it clear. I think the core insight for me is simply "base conversion felt backwards because you felt it should go in the same order as long division, but it doesn't and is doing something else. Also "put the remainders aside and write in reverse order" is less clear than "write the remainders as you find them, but right to left."
This manifestly worked, if you did it, but always felt backwards to me, doubly so -- once for the reverse order thing, and once for the fact that you're only using remainders, not quotients, or so it seemed. Plus, though it gave the right answer, I didn't have much sense of why it worked.
Well, I was thinking about it early this morning in lieu of sleeping again, as I do, and came up with a method[1] that's slow but does both use quotients and yield the digits in MSB (most significant 'bit' first, descending significance). And then I thought about the old remainder method again, and it made more sense[2], and I also realized a key mismatch: the whole cycle of dividing by newbase calls up long division, may even involve long division if newbase is multiple digits in oldbase, and long division gives its answer in MSB. The remainder method chews up the number LSB, and gives the newbase numeral's digits LSB, so it's not backwards at all by its own lights, but it is LSB instead of MSB. Works fine if you write the units first and work to the left.
[1] Trial and error: multiply by increasing powers of newbase until the quotient is zero; backoff to the preceding power, and the resulting quotient is the first digit (MSB) of your answer. Repeat for the remainder. So (base 10 to base 10, for simplicity), n=742: find that 742//1000 = 0, 742//100 = 7, so 7, then repeat for 42. A subtlety is that numeral-based long division may not work, e.g. if you're converting a binary numeral to base ten and dividing by '1010': binary quotients are only 0 or 1. You'd have to go back to basics, division as "how many times can I subtract b from a?"
[2] 10 to 10 again: n=742, divide by 10 and get 2, that's your units; now shift right (or use the quotient) to get 74, divide by 10, get 4, which is your tens digit, and so on. Thinking about the relation between dividing by 2, and shifting the binary representation of a number to the right, made it all clear.
Dunno if I'm making it clear. I think the core insight for me is simply "base conversion felt backwards because you felt it should go in the same order as long division, but it doesn't and is doing something else. Also "put the remainders aside and write in reverse order" is less clear than "write the remainders as you find them, but right to left."