4 ms·
That's, essentially, the algorithm for computing the representation of a number in a given base: divide by the base and write down the remainders. To build up
by romwell 9y ago
That's, essentially, the algorithm for computing the representation of a number in a given base: divide by the base and write down the remainders.
To build up intuition on how this works, do it with base 10.
What are the digits of the number 8675309 ? Just remainders after repeatedly dividing by 10.
Now when it's almost obvious it works for base 10, you realize there's no reason it wouldn't work the same way for other bases. Hence the algorithm.
- tgb 9y agoYou're of course completely correct, but I feel like that misses the point. The great thing about this algorithm is not that it works - there are plenty of ways to figure out the binary representation of a number. Rather, it's that it only needs operations that are easy to perform and requires little state to remember. I'd much rather divide by two and round down than subtract the largest power of two that's less than my number from it. And I don't have to remember which power of N I last worked to know how many zeros I need to add before using the next power of 2 that fits in my number.