Positional Number Systems

Positional Number Systems

By Xunxen | 7676 Reads |

0     0

Using non-standard positional number systems can be quite useful for programmers, as computers store information in binary, but there are other useful bases. In fact, the average person regularly uses 3 different bases. Decimal is probably the most commonly used base, so I don't imagine I need to explain it (though I will later, anyway). The other 2 are Unary and Sexagesimal. Unary is base-1. Whenever you use tally marks, count on your fingers, or even count physical objects, you are treating each element as 1 digit. This can have its uses but is highly inefficient, especially for computers: by the time you reach 11, you’ve already surpassed the limit for an unsigned 32-bit integer. Sexagesimal is base-60. Here’s where it’s used: 60 seconds in a minute, 60 minutes in an hour. Time is expressed as a 3 digit hexadecimal number representing seconds. If you’re using a base less than 10, generally numeric values starting at 0 are used. If your base is between 11 and 36 inclusive, after the number 9, letters are used, starting with a. If your base is greater than 36, digits are colon-delimited.

Decimal is base 10. What that means is that a given number is equal to the sum of each digit times a power of 10. For instance, 2503 =(210^3)+(510^2)+(010^1)+(310^0). Remember that anything to the 0 power is 1, so the farthest digit from the left is exactly equal to it’s value. This is true in ALL bases, not just decimal. Now just like any good mathematician or programmer, we don’t want an equation that will work on just one problem, we want a general, all-encompassing function. Here, we know that in base 10, we multiply the digits by powers of 10, so let’s generalize and say that in base-n, we multiply by powers of n. next, look at the equation. Notice anything about the powers? Starting from the right, the powers of n increase by 1 each digit, starting at zero.

Now we’ve got a simple, general conversion to decimal formula, but before we go any further, it helps to understand how counting works (bear with me here). When you count in decimal, you go from 1-9, then 10-19, 20-29, …, 90-99 then 100, etc. think of this like a sort of clock with 10 positions. when the ones hand gets all the way to 9, after 1 more change it arrives back at 0, and the tens hand increases by 1. When the tens hand gets to 9, the next time it moves, it arrives back at 0, and the 100’s hand increases by 1, etc. this works in all bases, except now you have to imagine there are n positions for every hand, where n is the base. so for instance, in base 3, when the smallest hand gets to 2 (I imagine most programmers will recognize 0 is 1 possible value, so digits may be 0, 1, or 2) the next location it moves to is 0, and the next hand up moves forward 1 position. Counting in base 3, then, would look like this: 0, 1, 2, 10, 11, 12, 20, 21, 22, now what? If you thought 30 was next, you’d be wrong. we’re counting in base-3, so the highest possible digit value is 2. the next number, then, is 100. Make sure to check each digit. If it will become equal to n in base-n, then you have to carry and reset the previous digits, just like in decimal. you can also this of it this way: powers of n in base-n will be written like powers of 10 in decimal, namely 1, 10, 100, 1000, etc. so essentially, all bases are base-10 because 4 in base-4 is 10, 9 in base-9 is 10, etc. (it almost seems like cheating. What’s 342 squared? oh, it’s 100 in base-342).

Okay, now that we’ve covered counting in base-n, we can move on to conversion to base-n. there are 2 methods to use here, though one is only really practical for converting to binary. The first way is easier, but requires a lot more work the higher n becomes. In this method you simply take the highest power of n that goes into the decimal number you want to convert, then based on what power you used, find what digit that value would be in. let’s use the number 8. in binary, we see that 8 is a power of 2. the 3rd power to be exact, so it would be a 1 in the fourth digit from the right (remembering that the farthest digit is to the 0 power), so 8 in binary is 1000. Now let’s convert the same number to ternary (base-3). Well 3^1 is the highest power of 3 that fits in 8, but now how do we get 8 if we can only add 2 more to the value? Binary is easy because there are 2 possible values to the digit, 0 or 1, so either it adds value or it doesn’t, but ternary has 3 possible values. remember the equation we had for decimal? it’s the same thing. we’re not just adding powers of n, were adding products of powers of n and the digit value. so 3^1 fits in 8, but (23^1) fits better. now we’re only 2 away from the value, so that 0-power digit is 2. 8 in ternary is 22. Notice how much smaller 22 is that 1000? The higher the base, the less digits are needed to represent the value, assuming the number is higher than the base. trick question: what’s 8 in base-9? Well since 8 is less than or equal to 9-1, it’s just 8. This is true for any number, x, in any base, n, where n>=x+1, with the stipulation that x in base-n will be a 1 digit number, or as an example, 22 in base 23 is 22. Here 22 is a 1 digit number with a value equal to 2223^0. Now for the other method. This method requires less work, but will only work for integers. simply take the number you want to convert, and repeatedly divide by the number of the base you want to convert to, recording the remainder of each operation, until you have nothing left. If you wrote them in exactly the order you got them in, write it backwards, and you have your number. Let’s convert 38 to base 6 (using integer arithmetic. Any fractional portion is dropped). 38 / 6 = 6 R2, 6 / 6 = 1 R0, 1 / 6 = 0 R1 so 37 in base 6 is 102. This works because the first thing you want is the division remainder of the number by the base you’re converting to, so essentially x/n^0 then you divide by n^1 and take the remainder again. These operations are the inverse of converting to decimal.

Conversions between non-decimal bases is possible (I think) but is easiest between bases that are powers of each other. to make it simpler, say you want to convert a number in hexadecimal (base-16, if you didn’t know) to binary. Well 16 is 2^4. we now know how many digits our binary number could have. yup, it’s that simple. in fact, it’s even simpler than that. each digit in hexadecimal translates directly to 4 bits (padded with 0’s, if necessary). If you want to convert easily to decimal from hex, just count from 0 to 15 in binary then next to it, write the numbers 0 to 9, then the letters a through f. Now as long as you pad 0’s you can just connect all these numbers together to get the binary representation. This is true for any base, as long as one is a power of another. So, say, 21 in base-3 to base-9, well 9=3^2, so 2 base-3 digits will be 1 base-9 digit. since we only have 2 base-3 digits, our number will be less than 9, and therefore less than 10, so we can just be lazy and convert to decimal (actually, that’s really all you ever have to do, because any group of digits will be less than the base you’re converting to if you’re going to a higher base. You could be converting from binary to quaternary (base-4) 2 binary digits will never be greater than 3, so go to decimal because it’ll be the same in quaternary) and we get 7. so 21 in ternary=7 in base-9. also, 2121=77, 21212121=7777. Just pretend you’re converting each digit to or from decimal and pad zeroes where necessary.

Now here’s something I’ve been wondering about recently, and haven’t been able to find any info on: rational bases. I’ve managed to work out all kinds of info on them myself. let me explain in decimal: everything I’ve explained is true to the left of the decimal point. after that, the powers of 10 decrease, so 1.05 = (110^0)+(010^-1)+(0*10^-2). Generalizing that, after the base-n point, exponents continue to decrease, so why can’t we convert 8 to base 1/2? the 0-power place would still equal it’s value, so 1 in base 1/2 should be 1. after that it gets fun. remember negative exponents? n^-1=1/n, therefore 8 should be 0.001 (1/2^-3=8). now of course, the only practical use for this would be representing really small numbers as integers (think 0.001 in base 1/10=1000) or representing large numbers as minuscule numbers. Base-1/n would be the same number as base-n reflected across the 0-power place. (1000 base-2, 0.001 base-1/2)

Another interesting concept I recently stumbled upon is negative bases. Remember how an even exponent always makes a positive number? that’s the basic concept, but it makes counting really weird. for instance, negadecimal is 1-9 ans usual, but now the 10’s place has a negative value… what to do… oh, what about 100-90? yup, so after 9 you go to 190… then after 199 you go to 180 and the pattern continues like so with odd-powered digits being negative in value. the point? how do you represent -100? Why, with the positive number 1900, of course. Yay for all positive numbers, now good luck doing math with that…

Okay, now onto interesting notes and ideas: remember how I said I said generally those digits are used? These values are arbitrary. no one’s stopping you from representing binary using A’s and S’s, or 9’s and 5’s (in fact, the 5 could represent 1). Why is this useful? How about we use base 26? let’s say a=0, b=1, c=2…z=25. Now type a message and convert to decimal. See? different bases ARE useful, and while this may not be the most complicated method of encryption, it could have uses, since most people don’t even realize they aren’t just using decimal… here's another example: remember that bit about converting between bases that are powers of each other? What if you want to compress a file quickly? why not convert to a higher base? then just convert back to decompress it. If the document is written in hex, why not change it to base-256? you'll cut the document size in half (theoretically) and still have all the same information in it. additionally, I mentioned Unary is inefficient. when you count on your fingers, they each have 2 possible positions that are easily distinguishable. take advantage of that. If you count in binary, even counting on 1 hand using only 4 fingers can get you to 31. Using 4 fingers on both hands, you can count to 255. if you use all 10 fingers, you can count to 1023 on just your fingers, and it only requires some simple multiplication to figure out values. One final tidbit that might be useful is determining if a number is even or odd in a given base. If the base is even, the least significant digit determines whether or not the number is even. If the base is odd the number of odd digits determines whether or not the number is even. so in an even base, an even 0-power digit makes the number even. In an odd base, an even number of odd digits makes the number even.

Before I summarize, I’d like to add one more piece of info that will be useful for determining how to store numbers in a given base if you’re writing a program: the number of digits x will have in base-n will be 1+logn(x) (with the given exception of conversions between non-decimal bases that are powers of each other). If you need an example, look at 8 in binary. log2(8)=3 and 8 in binary is 1000, 4 digits. This is because you’re reducing the number to 0 using integer arithmetic, which requires the denominator to be at least 1 higher than the numerator, but since we’re using powers, we need an exponent to put on n that will make n greater than x, so we use 1 more than the exponent that gives x. A number, x, in base-n will have 1+log10(x) digits, for essentially the same reason, but here, we treat the number as though it’s a decimal number.

Okay, so if you got completely lost on this article, at least feel free to use these formulas: to convert a number, x, to a base, n, you would take the summation of 10^i*[(x/n^i)%n] as i goes from 0 to 1+logn(x). to convert back to decimal, you would take the summation of n^i*[(x%10¹)/10^i] as i goes from 0 to 1+log10(x). Just remember that each iteration through this equation returns 1 digit and they’ll work to convert to any arbitrary base, so long as you use integers and integer arithmetic. If you want to convert rational numbers, do what I did and derive your own formulas.

Note: I came up with most of this information through experimentation. If anything in here is wrong, please let me know, so I can correct it.